Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m ... da ne bo pomot |
m tn |
||
Vrstica 29: | Vrstica 29: | ||
Petersenov graf |
Petersenov graf |
||
* je najmanjši snark, |
* je najmanjši snark, |
||
* je najmanjši kubični graf brez mostov in brez Hamiltonovega |
* je najmanjši kubični graf brez mostov in brez Hamiltonovega obhoda (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. |
Redakcija: 03:57, 15. 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 tudi Hamiltonovega 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 obhoda (cikla),
- je največji kubični graf s premerom 2,
- je najmanjši hipohamiltonski graf.