„Petersen-gráf” változatai közötti eltérés
[ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Xia (vitalap | szerkesztései) a infobox jav. |
Xia (vitalap | szerkesztései) képek rendezése |
||
12. sor:
| egyéb = [[reguláris gráf|3-reguláris]]
}}
[[Kép:Petersen graph, two crossings.svg|thumb|right|A Petersen gráf [[keresztezési szám]]a 2.]]▼
[[Kép:Petersen graph, unit distance.svg|thumb|right|A Petersen gráf lerajzolható a síkban úgy, hogy minden él hossza egység hosszúságú.]]▼
[[Kép:Petersen graph 2.svg|thumb|right|A Petersen gráf egy másik rajzolási módja. Ez hármas szimmmetriát mutat, szemben a fenti rajzzal, amely ötös szimmetriával rendelkezik.]]▼
A '''Petersen-gráf''' egy nagyon híres, speciális gráf. Nagyon gyakran bukkan fel a [[gráfelmélet]]ben ellenpéldaké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.<ref>{{cite journal|author=A. B. Kempe|title=A memoir on the theory of mathematical form|journal=Philosophical Transactions of the Royal Society of London|volume=177|pages=1–70|year=1886}}</ref>
26 ⟶ 24 sor:
Ez a konstrukció természetesen nem csak 5, hanem más számosságok esetén is működik. Átalános esetben az ilymódon konstruált gráfokat [[Kneser-gráf]]oknak nevezzük, tehát a Petersen-gráf egy speciális [[Kneser-gráf]]: <math>KG(5,2)\ </math>.
[[Kép:Petersen-gráf konstrukció.jpg|400px|középre|Petersen-gráf konstrukciója]]▼
[[Kép:izomorfvele.jpg|bélyegkép|jobbra|Ez a gráf is [[gráfizomorfizmus|izomorf]] a Petersen-gráffal.]]
▲[[Kép:Petersen-gráf konstrukció.jpg|400px|középre|Petersen-gráf konstrukciója]]
<gallery>
▲
▲
</gallery>
== Petersen motivációja ==
A [[négyszín-sejtés]] egy ekvivalens alakja, hogy tetszőleges kétszeresen élösszefüggő, 3-reguláris [[síkba rajzolható gráf|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.
|