Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m dp/+/-ktgr |
m dp/druga slika |
||
Vrstica 19: | Vrstica 19: | ||
[[Slika:Petersen graph 3.svg|thumb|right|Petersenov graf s tremi križajočimi povezavami. Primer lepo kaže kako je ta Petersenov graf [[izomorfizem grafov|izomorfen]] prvemu in vsem ostalim. Izgleda precej drugače, vendar je z očmi teorije grafov enak drugim.]] |
[[Slika:Petersen graph 3.svg|thumb|right|Petersenov graf s tremi križajočimi povezavami. Primer lepo kaže kako je ta Petersenov graf [[izomorfizem grafov|izomorfen]] prvemu in vsem ostalim. Izgleda precej drugače, vendar je z očmi teorije grafov enak drugim.]] |
||
[[Slika:Petersen graph, unit distance.svg|thumb|right|Petersenov graf s povezavami dolžine [[1 (število)|1]].]] |
[[Slika:Petersen graph, unit distance.svg|thumb|right|Petersenov graf s povezavami dolžine [[1 (število)|1]].]] |
||
[[Slika: |
[[Slika:Petersen2 tiny.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]] 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]]. |
'''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]]. |
||
Vrstica 56: | Vrstica 56: | ||
== Zunanje povezave == |
== Zunanje povezave == |
||
{{ |
{{kategorija v Zbirki|Petersen graph|Petersenov graf}} |
||
{{math-stub}} |
{{math-stub}} |
||
Vrstica 65: | Vrstica 65: | ||
[[Kategorija:1892 v znanosti]] |
[[Kategorija:1892 v znanosti]] |
||
[[Kategorija:1898 v znanosti]] |
[[Kategorija:1898 v znanosti]] |
||
[[cs:Petersenův graf]] |
[[cs:Petersenův graf]] |
Redakcija: 23:56, 26. 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.