Petersen-gráf

A Wikipédiából, a szabad enciklopédiából
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 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]

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