Petersenov graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Petersenov graf
Petersen1 tiny.svg
Najbolj znana predstavitev Petersenovega grafa s petkotnikom in petimi prečkami.
Ime Julius Petersen
Točke 10
Povezave 15
Polmer 2
Premer 2
Notranji obseg 5
Avtomorfizem 120 (S5)
Kromatično število 3
Kromatični indeks 4
Ulomljeni kromatični indeks 3
Značilnosti kubičen
krepko regularen
razdaljno-prehoden
snark
z enotsko razdaljo
Petersenov graf. Najbolj znana predstavitev s petimi križajočimi povezavami. Predstavitev Petersenovega grafa je neskončno mnogo.
Petersenov graf z le dvema križajočima povezavama.
Petersenov graf s tremi križajočimi povezavami. Primer lepo kaže kako je ta Petersenov graf izomorfen prvemu in vsem ostalim. Izgleda precej drugače, vendar je z očmi teorije grafov enak drugim.
Petersenov graf s povezavami dolžine 1 (graf z enotsko razdaljo).
Petersenov graf, ki kaže, da je graf hipohamiltonski. To je posledica dejstva, da je Petersenov graf prehoden po točkah.

Petersenov gráf [pétersenov ~] je v teoriji grafov pomemben graf z 10 točkami (vozlišči) in 15 povezavami. Ima mnogo zanimivih značilnosti. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga je vpeljal leta 1892 in objavil leta 1898.

Značilnosti[uredi | uredi kodo]

Osnovne značilnosti[uredi | uredi kodo]

Petersenov graf

Druge značilnosti[uredi | uredi kodo]

Petersenov graf

Največji in najmanjši[uredi | uredi kodo]

Petersenov graf

  • je najmanjši snark,
  • je najmanjši kubični graf brez mostov in brez Hamiltonovega cikla,
  • je največji kubični graf s premerom 2,
  • je najmanjši hipohamiltonski graf.

Posplošeni Petersenov graf[uredi | uredi kodo]

Družina Petersenovih grafov[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]