Petersenov graf: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m/dp/pnp |
m m/dp/pnp |
||
Vrstica 22: | Vrstica 22: | ||
[[Slika:Petersen2 tiny.svg|thumb|right|Petersenov graf, ki kaže, da je graf hipohamiltonski. To je posledica dejstva, da je Petersenov graf prehoden po točkah.]] |
[[Slika:Petersen2 tiny.svg|thumb|right|Petersenov graf, ki kaže, da je graf hipohamiltonski. To je posledica dejstva, da je Petersenov graf prehoden po točkah.]] |
||
'''Petersenov gráf''' [pétersenov ~] je v [[teorija grafov|teoriji grafov]] pomemben [[graf (matematika)|graf]] z [[10 (število)|10]] [[točka (teorija grafov)|točkami]] in [[15 (število)|15]] [[povezava (teorija grafov)|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 [[Julius Peter Christian Petersen|Juliusu Petersenu]], ki ga je vpeljal leta [[1892 v znanosti|1892]] in objavil leta [[1898 v znanosti|1898]]. Leta 1898 je pokazal, da je graf najmanjši [[kubični graf]] brez [[most (teorija grafov)|most]]ov in brez [[po povezavah k-pobarvljivi graf|3-povezavnega barvanja]].<ref>{{citat|last1= Brouwer|first1= Andries Evert|authorlink1= Andries Brouwer|title= The Petersen graph|date= |accessdate= |url=http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|language= en|ref= en}}</ref> |
'''Petersenov gráf''' [pétersenov ~] je v [[teorija grafov|teoriji grafov]] pomemben [[graf (matematika)|graf]] z [[10 (število)|10]] [[točka (teorija grafov)|točkami]] in [[15 (število)|15]] [[povezava (teorija grafov)|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 [[Julius Peter Christian Petersen|Juliusu Petersenu]], ki ga je vpeljal leta [[1892 v znanosti|1892]] in objavil leta [[1898 v znanosti|1898]]. Leta 1898 je pokazal, da je graf najmanjši [[kubični graf]] brez [[most (teorija grafov)|most]]ov in brez [[po povezavah k-pobarvljivi graf|3-povezavnega barvanja]].<ref>{{citat|last1= Brouwer|first1= Andries Evert|authorlink1= Andries Evert Brouwer|title= The Petersen graph|date= |accessdate= |url=http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|language= en|ref= en}}</ref> |
||
== Značilnosti == |
== Značilnosti == |
Redakcija: 15:31, 1. julij 2016
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 | 3-regularen (kubičen) krepkoregularen razdaljnoprehoden snark z enotsko razdaljo |
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]
Značilnosti
Osnovne značilnosti
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
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.
Posplošeni Petersenov graf
Družina Petersenovih grafov
Zunanje povezave
- Weisstein, Eric Wolfgang. MathWorld https://mathworld.wolfram.com/.
{{navedi splet}}
: Manjkajoč ali prazen|title=
(pomoč)
Sklici
- ↑ Brouwer, Andries Evert, The Petersen graph (v angleščini)