Pojdi na vsebino

Petersenov graf

Iz Wikipedije, proste enciklopedije
Petersenov graf
Najbolj znana predstavitev Petersenovega grafa s petkotnikom in petimi prečkami.
ImeJulius Petersen
Točke10
Povezave15
Polmer2
Premer2
Notranji obseg5
Avtomorfizem120 (S5)
Kromatično število3
Kromatični indeks4
Ulomljeni kromatični indeks3
Rod1
Značilnostisimetričen
3-regularen
(kubičen)
krepkoregularen
razdaljnoprehoden
snark
z enotsko razdaljo
hipohamiltonov
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 hipohamiltonov. To je posledica dejstva, da je Petersenov graf točkovnoprehoden.

Petersenov gráf [pétersenov ~] je v teoriji grafov pomemben graf z 10 točkami in 15 povezavami. Ima mnogo zanimivih značilnosti in se velikokrat rabi kot uporabni primer in protiprimer pri mnogih problemih v teoriji grafov. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga je vpeljal leta 1892 in objavil leta 1898. Leta 1898 je pokazal, da je graf najmanjši kubični graf brez mostov in brez 3-povezavnega barvanja.[1]

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 najmanjši hipohamiltonov graf,
  • je največji kubični graf s premerom 2.

Posplošeni Petersenov graf

[uredi | uredi kodo]

Družina Petersenovih grafov

[uredi | uredi kodo]

Zunanje povezave

[uredi | uredi kodo]
  • Weisstein, Eric Wolfgang. MathWorld https://mathworld.wolfram.com/. {{navedi splet}}: Manjkajoč ali prazen |title= (pomoč)

Sklici

[uredi | uredi kodo]