Petersenův graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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]