Petersenův graf

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ší bezmostý 3-regulární graf, jehož hrany nelze obarvit třemi barvami.

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

Vlastnosti

• je souvislý
• je symetrický
• není rovinný, ale je toroidní
• je 3-regulární, tj. každý vrchol má stupeň 3
• neobsahuje Hamiltonovskou kružnici, pouze Hamiltonovskou cestu
• chromatické číslo je rovné 3 (jsou potřeba 3 barvy k obarvení vrcholů, aby žádné dva sousední neměly stejnou barvu)
• chromatický index je rovný 4 (jsou potřeba 4 barvy k obarvení hran, aby žádné dvě sousedící neměly stejnou barvu)
• nejkratší kružnice má délku 5
• každý diagram Petersenova grafu obsahuje alespoň 2 křížení hran
• je 3-degenerovaný

Externí odkazy

• Obrázky, zvuky či videa k tématu Petersenův graf na Wikimedia Commons