Petersenův graf

Technology

12 hours ago

Author

Petersenův graf - nejčastější zobrazení Petersenův graf s pouze dvěma kříženími hran 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 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ší bezmostý 3-regulární graf, jehož hrany nelze obarvit třemi barvami.

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ý