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]

Petersenov graf sa najčastejšie kreslí ako päťuholník s pentagramom vo vnútri
Petersenov graf s dvoma prekríženiami
Petersenov graf s rovnako dlhými hranami
Trojfarebné zafarbenie vrcholov Petersenovho grafu


VlastnostiUpraviť

ReferencieUpraviť

  1. The Petersen graph
  2. A memoir on the theory of mathematical form, Philosophical Transactions of the Royal Society of London, volume 177 s.1–70 r. 1886.

Externé odkazyUpraviť

Tento článok je čiastočný alebo úplný preklad článku Petersen Graph na anglickej Wikipédii (číslo revízie nebolo určené).