Petersenov graf

Iz Wikipedije, proste enciklopedije

Petersenov graf. Najbolj znana predstavitev s petimi križajočimi povezavami. Predstavitev Petersenovega grafa je neskončno mnogo.

Petersenov graf z le dvema križajočima povezavama.

Petersenov graf s tremi križajočimi povezavami. Primer lepo kaže kako je ta Petersenov graf izomorfen prvemu in vsem ostalim. Izgleda precej drugače, vendar je z očmi teorije grafov enak drugim.

Petersenov graf s povezavami dolžine 1.

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 teoriji grafov pomemben graf na desetih točkah (vozliščih) z mnogimi zanimivimi lastnostmi. Imenuje se po danskem matematiku Juliusu Petersenu, ki ga je vpeljal leta 1892 in objavil leta 1898.

[uredi] Lastnosti

[uredi] Osnovne lastnosti

Petersenov graf

• je 3-povezan (stopnja vsake točke je enaka 3),
• je kubičen, krepko regularen,
• ima kromatično število 3 in kromatični indeks 4 in je zato snark.

[uredi] Druge lastnosti

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¹),
• ...

[uredi] 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.

[uredi] Posplošeni Petersenov graf

[uredi] Družina Petersenovih grafov

[uredi] Zunanje povezave

Wikimedijina Zbirka ponuja še več predstavnostnega gradiva o temi: Petersenov graf

Ta matematični članek je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.