Petersenův graf - Encyklopedie - Portál divoch.net

Hledat:

Invia.cz Last minute Tunisko Dovolená v Chorvatsku Pojeďte do Egypta Bulharsko Last minute Kréta
 

Petersenův graf

Petersenův graf – nejčastější zobrazení
Petersenův graf s pouze dvěma kříženími hran
Diagram se třemi kříženími je stejně jako všechny ostatní diagramy izomorfní s Petersenový grafem
Petersenův graf s jednotkové délky
Diagram ukazující, že Petersenův graf je hypohamiltonovský, tj. zrušením libovolného vrcholu vznikne Hamiltnovský graf
Obarvení vrcholů třemi barvami
Přestože maximální stupeň vrcholu je roven 3, k obarvení hran jsou potřeba čtyři barvy. Grafy s touto vlastností se řadí do třídy 2

Petersenův graf je 3-regulární (kubický) graf s 10 vrcholy s řadou zajímavých vlastností. Pojmenovaný je po dánském matematikovi Juliu Petersenovi, který ho roku 1898 zkonstruoval coby nejmenší 3-regulární graf, jehož hrany nelze obarvit třemi barvami.

Vlastnosti[editovat | editovat zdroj]

 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/w/index.php?title=Petersenův_graf&oldid=9948573
Stránka byla naposledy upravena 17. 3. 2013 v 06:05. Editovat celý článek Petersenův graf.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy