Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m r2.7.1) (robot Dodajanje: et:Peterseni graaf |
m Bot: Migracija 18 interwikija/-ev, od zdaj gostuje(-jo) na Wikipodatkih, na d:q835614 |
||
Vrstica 65: | Vrstica 65: | ||
[[Kategorija:1892 v znanosti]] |
[[Kategorija:1892 v znanosti]] |
||
[[Kategorija:1898 v znanosti]] |
[[Kategorija:1898 v znanosti]] |
||
[[cs:Petersenův graf]] |
|||
[[de:Petersen-Graph]] |
|||
[[en:Petersen graph]] |
|||
[[es:Grafo de Petersen]] |
|||
[[et:Peterseni graaf]] |
|||
[[fa:گراف پترسن]] |
|||
[[fr:Graphe de Petersen]] |
|||
[[hu:Petersen-gráf]] |
|||
[[ja:ピーターセングラフ]] |
|||
[[ko:페테르센 그래프]] |
|||
[[no:Petersen-grafen]] |
|||
[[pl:Graf Petersena]] |
|||
[[pt:Grafo de Petersen]] |
|||
[[ru:Граф Петерсена]] |
|||
[[sk:Petersenov graf]] |
|||
[[uk:Граф Петерсена]] |
|||
[[vi:Đồ thị Petersen]] |
|||
[[zh:佩特森圖]] |
Redakcija: 22:48, 8. marec 2013
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.