Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m dp/+ktgr |
m dp/+/-ktgr |
||
Vrstica 13: | Vrstica 13: | ||
| chromatic_index = 4 |
| chromatic_index = 4 |
||
| fractional_chromatic_index = 3 |
| fractional_chromatic_index = 3 |
||
| properties = [[kubični graf|kubičen]]<br />[[krepko regularni graf|krepko regularen]]<br />[[po razdalji prehodni graf| |
| properties = [[kubični graf|kubičen]] <br /> [[krepko regularni graf|krepko regularen]] <br /> [[po razdalji prehodni graf|po razdalji prehoden]] <br /> [[snark]] |
||
}} |
}} |
||
[[Slika:Petersen graph.svg|thumb|right|Petersenov graf. Najbolj znana predstavitev s petimi križajočimi povezavami. Predstavitev Petersenovega grafa je neskončno mnogo.]] |
[[Slika:Petersen graph.svg|thumb|right|Petersenov graf. Najbolj znana predstavitev s petimi križajočimi povezavami. Predstavitev Petersenovega grafa je neskončno mnogo.]] |
||
Vrstica 21: | Vrstica 21: | ||
[[Slika:Petersen graph 2.svg|thumb|right|Petersenov graf, ki kaže, da je graf hipohamiltonski. To je posledica dejstva, da je Petersenov graf prehoden po točkah.]] |
[[Slika:Petersen graph 2.svg|thumb|right|Petersenov graf, ki kaže, da je graf hipohamiltonski. To je posledica dejstva, da je Petersenov graf prehoden po točkah.]] |
||
'''Petersenov graf''' je v [[teorija grafov|teoriji grafov]] pomemben [[graf (matematika)|graf]] |
'''Petersenov graf''' je v [[teorija grafov|teoriji grafov]] pomemben [[graf (matematika)|graf]] z [[10 (število)|10]] [[točka (teorija grafov)|točkami]] (vozlišči) in [[15 (število)|15]] [[povezava (teorija grafov)|povezavami]]. Ima mnogo zanimivih značilnosti. Imenuje se po danskem matematiku [[Julius Peter Christian Petersen|Juliusu Petersenu]], ki ga je vpeljal leta [[1892]] in objavil leta [[1898]]. |
||
== |
== Značilnosti == |
||
=== Osnovne |
=== Osnovne značilnosti === |
||
Petersenov graf |
Petersenov graf |
||
Vrstica 31: | Vrstica 31: | ||
* ima [[kromatično število]] 3 in [[kromatični indeks]] 4 in je zato [[snark]]. |
* ima [[kromatično število]] 3 in [[kromatični indeks]] 4 in je zato [[snark]]. |
||
=== Druge |
=== Druge značilnosti === |
||
Petersenov graf |
Petersenov graf |
||
Vrstica 46: | Vrstica 46: | ||
Petersenov graf |
Petersenov graf |
||
* je najmanjši snark, |
* je najmanjši snark, |
||
* je najmanjši kubični graf brez |
* je najmanjši kubični graf brez [[most (teorija grafov)|most]]ov in brez Hamiltonovega cikla, |
||
* je največji kubični graf s premerom 2, |
* je največji kubični graf s premerom 2, |
||
* je najmanjši hipohamiltonski graf. |
* je najmanjši hipohamiltonski graf. |
||
Vrstica 60: | Vrstica 60: | ||
{{math-stub}} |
{{math-stub}} |
||
⚫ | |||
[[Kategorija:Posamezni grafi]] |
[[Kategorija:Posamezni grafi]] |
||
⚫ | |||
[[Kategorija:Julius Peter Christian Petersen]] |
[[Kategorija:Julius Peter Christian Petersen]] |
||
[[Kategorija:1892 v znanosti]] |
[[Kategorija:1892 v znanosti]] |
Redakcija: 00:09, 25. avgust 2010
Petersenov graf | |
---|---|
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 po razdalji prehoden snark |
Petersenov graf 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
Osnovne značilnosti
Petersenov graf
- je 3-povezan (stopnja vsake točke je enaka 3),
- je kubičen, krepko regularen,
- ima kromatično število 3 in kromatični indeks 4 in je zato snark.
Druge značilnosti
Petersenov graf
- je neravninski graf,
- ima najmanjše možno število križajočih povezav 2,
- ima Hamiltonovo pot (Hamiltonov sprehod), ne pa tudi Hamiltonovega cikla,
- je simetričen,
- je Kneserjev graf ,
- ima spekter −2, −2, −2, −2, 1, 1, 1, 1, 1, 3 (-24, 15, 31),
- ...
Največji in najmanjši
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.