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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Petersen_graph.svg/220px-Petersen_graph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Petersen_graph%2C_two_crossings.svg/220px-Petersen_graph%2C_two_crossings.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0b/Petersen_graph_3.svg/220px-Petersen_graph_3.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Petersen_graph%2C_unit_distance.svg/220px-Petersen_graph%2C_unit_distance.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Petersen_graph_2.svg/220px-Petersen_graph_2.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/220px-Petersen_graph_3-coloring.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/85/PetersenBarveniHran.svg/220px-PetersenBarveniHran.svg.png)
Vlastnosti
editovat- 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
editovat- Obrázky, zvuky či videa k tématu Petersenův graf na Wikimedia Commons