Petersenov graf: razlika med redakcijama

dodanih 587 zlogov ,  pred 4 leti
m/dp/pnp
m (m/pnp/nvg)
(m/dp/pnp)
{{infopolje graf
| name = Petersenov graf
| image = [[Slika:Petersen1 tiny.svg|200px]]
| image_caption = Najbolj znana predstavitev Petersenovega grafa s [[petkotnik]]om in petimi prečkami.
| namesake = [[Julius Peter Christian Petersen|Julius Petersen]]
| vertices = 10
| edges = 15
| automorphisms = 120 (S<sub>5</sub>)
| radius = 2
| diameter = 2
| girth = 5
| chromatic_number = 3
| chromatic_index = 4
| fractional_chromatic_index = 3
| properties = [[regularni graf|3-regularen]] <br /> ([[kubični graf|kubičen]]) <br /> [[krepko regularnikrepkoregularni graf|krepko regularenkrepkoregularen]] <br /> [[po razdalji prehodni graf|razdaljno-prehodenrazdaljnoprehoden]] <br /> [[snark (teorija grafov)|snark]] <br /> [[graf z enotsko razdaljo|z enotsko razdaljo]]
| genus = 1
}}
[[Slika:Petersen graph.svg|thumb|right|Petersenov graf. Najbolj znana predstavitev s petimi križajočimi povezavami. Predstavitev Petersenovega grafa je neskončno mnogo.]]
[[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]] (vozlišči) 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>
 
== Značilnosti ==
Petersenov graf
* je 3-povezan (stopnja vsake točke je enaka 3),
* je [[kubični graf|kubičen]], [[krepko regularnikrepkoregularni graf|krepko regularenkrepkoregularen]],
* ima [[kromatično število]] 3 in [[kromatični indeks]] 4 in je zato [[snark (teorija grafov)|snark]].
 
 
== Zunanje povezave ==
 
* {{MathWorld|id= |title= }}
 
== Sklici ==
 
{{sklici|1}}
 
{{kategorija v Zbirki|Petersen graph|Petersenov graf}}