Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m robot Dodajanje: vi:Đồ thị Petersen |
m robot Dodajanje: pt:Grafo de Petersen |
||
Vrstica 77: | Vrstica 77: | ||
[[no:Petersen-grafen]] |
[[no:Petersen-grafen]] |
||
[[pl:Graf Petersena]] |
[[pl:Graf Petersena]] |
||
[[pt:Grafo de Petersen]] |
|||
[[ru:Граф Петерсена]] |
[[ru:Граф Петерсена]] |
||
[[sk:Petersenov graf]] |
[[sk:Petersenov graf]] |
Redakcija: 16:53, 25. oktober 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 razdaljno-prehoden snark z enotsko razdaljo |
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.