Petersen-gráf

Sablon:Gráf infobox A Petersen-gráf egy nevezetes speciális gráf. Nagyon gyakran bukkan fel a gráfelméletben különféle állítások ellenpéldájaként. 10 csúcsa és 15 éle van. Bár a névadó Julius Petersen, aki 1898-ban konstruálta meg, ezt a gráfot már 12 évvel Petersen munkája előtt 1886-ban felfedezték.

A gráf konstrukciója

Legyen P egy öt elemű halmaz. Ennek a P halmaznak a kételemű részhalmazait feleltetjük meg a gráf csúcsainak. Él akkor van két csúcs között, ha a csúcsoknak megfelelő halmazok diszjunktak. Formálisan:

$V=\{\{x,y\}\in (\genfrac{}{}{0ex}{}{P}{2})\}$

$E=\{\{u,v\}\in (\genfrac{}{}{0ex}{}{V}{2}):u\cap v=\mathrm{\varnothing }\}$

Az n elemű alaphalmazon hasonlóan konstruált gráfokat Kneser-gráfoknak nevezzük.

Ez a gráf is izomorf a Petersen-gráffal.

Petersen-gráf konstrukciója

• 
  A Petersen-gráf keresztezési száma 2.
• 
  A Petersen-gráf lerajzolható a síkban úgy, hogy minden él hossza egység hosszúságú.
• 
  A Petersen-gráf egy másik rajzolási módja. Ez hármas szimmetriát mutat, szemben a fenti rajzzal, amely ötös szimmetriával rendelkezik.

Petersen motivációja

A négyszín-tétel egy ekvivalens alakja, hogy tetszőleges kétszeresen élösszefüggő, 3-reguláris síkgráf élhalmaza három teljes párosításra bontható. Petersen a fenti példával megmutatta, hogy a síkbarajzolhatóság feltétele nem hagyható el. Bebizonyította viszont azt a gyengébb állítást, hogy minden kétszeresen élösszefüggő, 3-reguláris síkgráfban van teljes párosítás.

Hamilton-út és Hamilton-kör

A Petersen-gráf csúcstranzitív, van benne Hamilton-út, de nincs Hamilton-kör.

Színezhetőség

A Petersen-gráf kromatikus száma 3

A Petersen-gráf 3 színnel színezhető, de kettővel nem (mivel van benne páratlan kör), tehát kromatikus száma 3.

Tulajdonságai

A Petersen-gráf:

• 3-szorosan összefüggő, így 3-szorosan élösszefüggő és hídmentes is.
• függetlenségi száma 4 és 3 részes (lásd gráfelméleti fogalomtár)
• 3-reguláris gráf, dominálási száma 3, van teljes párosítása és 2-faktor.
• 6 különböző teljes teljes párosítása van.
• a legkisebb olyan 3-reguláris gráf, aminek derékbősége 5. (Az egyedi $(3,5)$-cage. Sőt, mivel mindössze 10 csúcsa van, az egyedi $(3,5)$-Moore-gráf.)
• Sugara 2, átmérője 2. A legnagyobb 2 átmérőjű 3-reguláris gráf.
• gráfspektruma −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• 2000 feszítőfája van, a legtöbb a 10-csúcsú 3-reguláris gráfok között.
• Kromatikus polinomja $t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352).$
• Karakterisztikus polinomja $(t-1{)}^5(t+2{)}^4(t-3)$, ezért egész spektrumú gráf – olyan gráf, melynek spektruma csak egész számokból áll.