Hledat:

Invia.cz Pojeďte do Egypta Kanárské ostrovy Dovolená - Turecko Dominikánská republika Madeira Last minute
 

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ým 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 Hamiltonovský 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: „https://cs.wikipedia.org/w/index.php?title=Petersenův_graf&oldid=14240457
Stránka byla naposledy upravena 27. 10. 2016 v 13:17. 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