Petersen-gráf

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.

Petersen-gráf
A Petersen-gráf tipikus rajzolási módja
Névadó	Julius Petersen
Csúcsok száma	10
Élek száma	15
Sugár	2
Átmérő	2
Derékbőség	5
Kromatikus szám	3
Élkromatikus szám	4
Génusz	1
Egyéb	3-reguláris

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=\left\{\{x,y\}\in {{P} \choose {2}}\right\}$

$E=\left\{\{u,v\}\in {{V} \choose {2}}:u\cap v=\emptyset \right\}$

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)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).$
• 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.