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á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ójaSzerkeszté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 motivációjaSzerkeszté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örSzerkesztés

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

SzínezhetőségSzerkeszté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ágaiSzerkeszté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ásokSzerkeszté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