Petersen-gráf

A Wikipédiából, a szabad enciklopédiából
Petersen-gráf
Petersen graph blue.svg
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
Kromatikus szám 3
Élkromatikus szám 4
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 | forrásszöveg szerkesztése]

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


Petersen motivációja[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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

Színezhetőség[szerkesztés | forrásszöveg szerkesztése]

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.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  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.