Petersen-gráf

matematikai fogalom a gráfelméletben

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.[1]

Petersen-gráf
A Petersen-gráf tipikus rajzolási módja
A Petersen-gráf tipikus rajzolási módja

NévadóJulius Petersen
Csúcsok száma10
Élek száma15
Sugár2
Átmérő2
Derékbőség5
Kromatikus szám3
Élkromatikus szám4
Génusz1
Egyéb3-reguláris

A gráf konstrukciója

szerkesztés

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:

 

 

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


Petersen motivációja

szerkesztés

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

szerkesztés

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

Színezhetőség

szerkesztés
 
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

szerkesztés

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  -cage. Sőt, mivel mindössze 10 csúcsa van, az egyedi  -Moore-gráf.)[2]
  • Sugara 2, átmérője 2. A legnagyobb 2 átmérőjű 3-reguláris gráf.[3]
  • 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.[4]
  • Kromatikus polinomja  [5]
  • Karakterisztikus polinomja  , ezért egész spektrumú gráf – olyan gráf, melynek spektruma csak egész számokból áll.

Hivatkozások

szerkesztés
  1. A. B. Kempe (1886). „A memoir on the theory of mathematical form”. Philosophical Transactions of the Royal Society of London 177, 1–70. o.  
  2. Hoffman, Alan J. & Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, doi:10.1147/rd.45.0497, <http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf>.
  3. Ez következik abból a tényből, hogy Moore-gráf, mivel bármely Moore-gráf a legnagyobb lehetséges reguláris gráf adott fokszámmal és átmérővel(Hoffman & Singleton 1960).
  4. (Jakobson & Rivin 1999); (Valdes 1991). The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders.
  5. Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8