Petersenov graf

Petersenov graf je neorientovaný graf s 10 vrcholmi a 15 hranami. Je to malý graf, ktorý slúži ako užitočný príklad pre mnohé problémy teórie grafov. Petersenov graf je  pomenovaný podľa Juliusa Petersena, ktorý ho zostrojil v roku 1898 ako najmenší kubický graf bez mostov s chromatickým indexom 4. Hoci je graf pomenovaný po Petersenovi, prvýkrát bol publikovaný o 12 rokov skôr v roku 1886.

Vlastnosti
 je súvislý
 je symetrický
 nie je rovinný
 je 3-regulárny, každý vrchol má stupeň 3
 neobsahuje Hamiltonovskú kružnicu, iba Hamiltonovskú cestu
 chromatické číslo je 3 (treba 3 farby na zafarbenie vrcholov, aby žiadne dva susediace  nemali rovnakú farbu)
 chromatický index je 4 (treba 4 farby k zafarbeniu hrán, aby žiadne dve susediace nemali rovnakú farbu)
 najkratšia kružnica má dĺžku 5
 každý diagram Petersenovho grafu obsahuje aspoň 2 kríženia hrán

Referencie

Externé odkazy

Teória grafov