Petersen-gráf

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
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:

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