hu.wikipedia.org

Petersen-gráf – Wikipédia

A Wikipédiából, a szabad enciklopédiából

Petersen-gráf

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]

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.

A Petersen-gráf keresztezési száma 2.
A Petersen-gráf lerajzolható a síkban úgy, hogy minden él hossza egység hosszúságú.
A Petersen-gráf egy másik rajzolási módja. Ez hármas szimmetriát mutat, szemben a fenti rajzzal, amely ötös szimmetriával rendelkezik.

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.

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

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.

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 $(3,5)$ -cage. Sőt, mivel mindössze 10 csúcsa van, az egyedi $(3,5)$ -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 $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).$ ^[5]
Karakterisztikus polinomja $(t-1)^{5}(t+2)^{4}(t-3)$ , ezért egész spektrumú gráf – olyan gráf, melynek spektruma csak egész számokból áll.

↑ A. B. Kempe (1886). „A memoir on the theory of mathematical form”. Philosophical Transactions of the Royal Society of London 177, 1–70. o.
↑ 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>.
↑ 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).
↑ (Jakobson & Rivin 1999); (Valdes 1991). The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders.
↑ Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8