Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m + |
|||
Vrstica 1: | Vrstica 1: | ||
[[Slika:Petersen graph. |
[[Slika:Petersen graph.svg|thumb|right|Petersenov graf.]] |
||
[[Slika:Petersen graph, two crossings.png|thumb|right|Petersenov graf z le dvema križajočima povezavama.]] |
[[Slika:Petersen graph, two crossings.png|thumb|right|Petersenov graf z le dvema križajočima povezavama.]] |
||
[[Slika:Petersen graph, three crossings.png|thumb|right|Petersenov graf s tremi križajočimi povezavami.]] |
[[Slika:Petersen graph, three crossings.png|thumb|right|Petersenov graf s tremi križajočimi povezavami.]] |
||
Vrstica 41: | Vrstica 41: | ||
[[Category:Teorija grafov]] |
[[Category:Teorija grafov]] |
||
[[en:Petersen graph]] |
|||
[[de:Petersen-Graph]] |
[[de:Petersen-Graph]] |
||
[[ |
[[fr:Graphe Petersen]] |
||
[[pl:Graf Petersena]] |
Redakcija: 05:21, 6. oktober 2005
Petersenov graf je v teoriji grafov pomemben graf na desetih vozliščih (točkah) z mnogimi zanimivimi lastnostmi. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga vpeljal leta 1892 in objavil leta 1898.
Lastnosti
Osnovne lastnosti
Petersenov graf
- je 3-povezan (stopnja vsakega vozlišča je enaka 3),
- je kubičen, močno regularen,
- ima kromatično število 3 in kromatični indeks 4 in je zato snark.
Druge lastnosti
Petersenov graf
- je neravninski graf,
- ima najmanjše možno število križajočih povezav 2,
- ima Hamiltonovo pot, ne pa obhoda (cikla),
- je simetričen,
- je Kneserjev graf ,
- ima spekter −2, −2, −2, −2, 1, 1, 1, 1, 1, 3,
- ...
Največji in najmanjši
Petersenov graf
- je najmanjši snark,
- je najmanjši kubični graf brez mostov in brez Hamiltonovega oghoda (cikla),
- je največji kubični graf s premerom 2,
- je najmanjši hipohamiltonski graf.