Petersenov graf: razlika med redakcijama

dodanih 173 zlogov ,  pred 15 leti
m
Cikel ni isto kot obhod|dodal sliko iz Zbirke
m (tn)
m (Cikel ni isto kot obhod|dodal sliko iz Zbirke)
[[Slika:Petersen graph, two crossings.svg|thumb|right|Petersenov graf z le dvema križajočima povezavama.]]
[[Slika:Petersen graph, three crossings.png|thumb|right|Petersenov graf s tremi križajočimi povezavami. Primer lepo kaže kako je ta Petersenov graf [[izomorfizem grafov|izomorfen]] prvemu in vsem ostalim. Izgleda precej drugače, vendar je z očmi teorije grafov enak drugim.]]
[[Slika:Petersen graph, unit distance.svg|thumb|right|Petersenov graf zs enako dolgimi povezavami enakih dolžine [[1 (število).]]
[[Slika:Petersen graph 2.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 graf''' je v [[teorija grafov|teoriji grafov]] pomemben [[graf (matematika)|graf]] na [[10 (število)|desetih]] vozliščih ([[točka]]h (vozliščih) z mnogimi zanimivimi lastnostmi. Imenuje se po [[Danci|danskem]] [[matematik]]u [[Julius Peter Christian Petersen|Juliusu Petersenu]], ki ga vpeljal leta [[1892]] in objavil leta [[1898]].
 
== Lastnosti ==
 
Petersenov graf
* je 3-povezan (stopnja vsakegavsake vozliščatočke je enaka 3),
* je [[kubični graf|kubičen]], [[močno regularen graf|močno regularen]],
* ima [[kromatično število]] 3 in [[kromatični indeks]] 4 in je zato [[snark]].
* je [[ravninski graf|neravninski]] graf,
* ima najmanjše možno število križajočih povezav 2,
* ima [[Hamiltonova pot|Hamiltonovo pot]] (Hamiltonov sprehod), ne pa tudi [[Hamiltonov obhodcikel|Hamiltonovega obhoda]] ([[Hamiltonov cikel|cikla]]),
* je [[simetrični graf|simetričen]],
* je [[Kneserjev graf]] <math>K_{5,2}</math>,
Petersenov graf
* je najmanjši snark,
* je najmanjši kubični graf brez mostov in brez Hamiltonovega obhoda (cikla),
* je največji kubični graf s premerom 2,
* je najmanjši hipohamiltonski graf.