Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m r2.7.1) (robot Dodajanje: uk:Граф Петерсена |
m r2.7.1) (robot Dodajanje: et:Peterseni graaf |
||
Vrstica 70: | Vrstica 70: | ||
[[en:Petersen graph]] |
[[en:Petersen graph]] |
||
[[es:Grafo de Petersen]] |
[[es:Grafo de Petersen]] |
||
[[et:Peterseni graaf]] |
|||
[[fa:گراف پترسن]] |
[[fa:گراف پترسن]] |
||
[[fr:Graphe de Petersen]] |
[[fr:Graphe de Petersen]] |
Redakcija: 21:48, 25. januar 2012
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.