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.[1] Hoci je graf pomenovaný po Petersenovi, prvýkrát bol publikovaný o 12 rokov skôr v roku 1886.[2]
Vlastnosti[upraviť | upraviť zdroj]
- 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[upraviť | upraviť zdroj]
- ↑ The Petersen graph
- ↑ A memoir on the theory of mathematical form, Philosophical Transactions of the Royal Society of London, volume 177 s.1–70 r. 1886.
Externé odkazy[upraviť | upraviť zdroj]
Tento článok je čiastočný alebo úplný preklad článku Petersen Graph na anglickej Wikipédii (číslo revízie nebolo určené).
|
Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš. |