Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
Brez povzetka urejanja |
m robot Dodajanje: ja:ピーターセングラフ |
||
Vrstica 55: | Vrstica 55: | ||
[[fr:Graphe Petersen]] |
[[fr:Graphe Petersen]] |
||
[[hu:Petersen-gráf]] |
[[hu:Petersen-gráf]] |
||
[[ja:ピーターセングラフ]] |
|||
[[ko:페테르센 그래프]] |
[[ko:페테르센 그래프]] |
||
[[no:Petersen-grafen]] |
[[no:Petersen-grafen]] |
Redakcija: 11:22, 26. september 2008
Petersenov graf je v teoriji grafov pomemben graf na desetih točkah (vozliščih) z mnogimi zanimivimi lastnostmi. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga je vpeljal leta 1892 in objavil leta 1898.
Lastnosti
Osnovne lastnosti
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 lastnosti
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.