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.The Petersen graph Hoci je graf pomenovaný po Petersenovi, prvýkrát bol publikovaný o 12 rokov skôr v roku 1886.A memoir on the theory of mathematical form, Philosophical Transactions of the Royal Society of London, volume 177 s.1–70 r. 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

Kategória:Teória grafov