Petersenov graf: Razlika med redakcijama

Petersenov graf
Petersenov graf
	Najbolj znana predstavitev Petersenovega grafa s petkotnikom in petimi prečkami.
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
	p; p; u;

Pregledujte zgodovino interaktivno

← Starejše urejanje Novejše urejanje →

Izbrisana vsebina Dodana vsebina

VizualnoVikibesedilo

Znotrajvrstično

Redakcija: 15:02, 1. julij 2016

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 $K_{5,2}$ ,
ima spekter −2, −2, −2, −2, 1, 1, 1, 1, 1, 3 (-2⁴, 1⁵, 3¹),
...

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)

Wikimedijina zbirka ponuja več predstavnostnega gradiva o temi: Petersenov graf.

Ta matematični članek je škrbina. Pomagajte Wikipediji in ga razširite.

[1] Brouwer, Andries Evert, The Petersen graph (v angleščini)

[1]

@@ Vrstica 1: / Vrstica 1: @@
 {{infopolje graf
- | name = Petersenov graf
+ | name     = Petersenov graf
- | image = [[Slika:Petersen1 tiny.svg|200px]]
+ | 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
+ | edges    = 15
  | automorphisms = 120 (S<sub>5</sub>)
- | radius = 2
+ | radius   = 2
  | diameter = 2
- | girth = 5
+ | girth    = 5
  | chromatic_number = 3
  | chromatic_index = 4
  | fractional_chromatic_index = 3
- | properties = [[kubični graf|kubičen]] <br /> [[krepko regularni graf|krepko regularen]] <br /> [[po razdalji prehodni graf|razdaljno-prehoden]] <br /> [[snark (teorija grafov)|snark]] <br /> [[graf z enotsko razdaljo|z enotsko razdaljo]]
+ | properties = [[regularni graf|3-regularen]] <br /> ([[kubični graf|kubičen]]) <br /> [[krepkoregularni graf|krepkoregularen]] <br /> [[po razdalji prehodni graf|razdaljnoprehoden]] <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.]]
@@ Vrstica 21: / 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.]]
-'''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. 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]].
+'''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>
 == Značilnosti ==
@@ Vrstica 28: / Vrstica 29: @@
 Petersenov graf
 * je 3-povezan (stopnja vsake točke je enaka 3),
-* je [[kubični graf|kubičen]], [[krepko regularni graf|krepko regularen]],
+* je [[kubični graf|kubičen]], [[krepkoregularni graf|krepkoregularen]],
 * ima [[kromatično število]] 3 in [[kromatični indeks]] 4 in je zato [[snark (teorija grafov)|snark]].
@@ Vrstica 55: / Vrstica 56: @@
 == Zunanje povezave ==
+* {{MathWorld|id= |title= }}
+== Sklici ==
+{{sklici|1}}
 {{kategorija v Zbirki|Petersen graph|Petersenov graf}}