Petersenov graf
kubični graf z 10 točkami in 15 povezavami
Petersenov gráf [pétersenov ~] je v teoriji grafov pomemben graf z 10 točkami in 15 povezavami. Ima mnogo zanimivih značilnosti in se velikokrat rabi kot uporabni primer in protiprimer pri mnogih problemih v teoriji grafov. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga je vpeljal leta 1892 in objavil leta 1898. Leta 1898 je pokazal, da je graf najmanjši kubični graf brez mostov in brez 3-povezavnega barvanja.[1]
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 |
Rod | 1 |
Značilnosti | simetričen 3-regularen (kubičen) krepkoregularen razdaljnoprehoden snark z enotsko razdaljo hipohamiltonov |
Značilnosti uredi
Osnovne značilnosti uredi
Petersenov graf
- je 3-povezan (stopnja vsake točke je enaka 3),
- je kubičen, krepkoregularen,
- ima kromatično število 3 in kromatični indeks 4 in je zato snark.
Druge značilnosti uredi
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 uredi
Petersenov graf
- je najmanjši snark,
- je najmanjši kubični graf brez mostov in brez Hamiltonovega cikla,
- je najmanjši hipohamiltonov graf,
- je največji kubični graf s premerom 2.
Posplošeni Petersenov graf uredi
Družina Petersenovih grafov uredi
Zunanje povezave uredi
- Weisstein, Eric Wolfgang. MathWorld https://mathworld.wolfram.com/.
{{navedi splet}}
: Manjkajoč ali prazen|title=
(pomoč)
Sklici uredi
- ↑ Brouwer, Andries Evert, The Petersen graph (v angleščini)