Petersenov graf

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
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

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]


Referencie[upraviť | upraviť zdroj]

  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é 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é).