Petersenov graf

Petersenov graf, vrsta grafa iz teorije grafova. je malen graf sa nizom posebnih svojstava koja ga svrstavaju u jedno od ključnih otkrića na području teorije grafova. Nazvan je po Juliusu Petersenu koji je 1898. godine ustanovio da je baš ovaj najmanji 3-regularan graf bez mostova koji nije 3-bridno obojiv. ^[1]

Osobine

Prvi koji ga je nacrtao je Alfred Bray Kempe 1886. godine. Tada se bavio Desargueosovim konfiguracijama. Vrhovi mu predstavljaju 10 pravaca Desargueosovih konfiguracija, a bridovi reprezentiraju parove pravaca koji se ne sijeku niti u jednoj od 10 točaka konfiguracije. Graf je 3-povezan i 3-bridno povezan. Jednostavan je i najmanji 3-regularan graf bez reznih bridova koji nema Hamiltonov ciklus, najmanji hipohamiltonov graf, najmanji 3-regularan graf bez reznih bridova čiji bridno kromatski broj iznosi 4 te najveći 3-regularan graf dijametra 2 (isti toliki mu je radijus) i ujedno najmanji 3-regularan graf struka 5. Bridno kromatski broj je 4. Ima 10 vrhova i 15 bridova. Sadrži savršeno sparivanje. Simetričan je pa je tranzitivan i po vrhovima i po bridovima. Petersenov graf je najveći (3,2)-Mooreov graf, najmanja najmanja (3,5)-rešetka, najmanji je snark, Kneserov graf K(5,2) , sadrži minore [math]\displaystyle{ K_{5} }[/math] i [math]\displaystyle{ K_{3,3} }[/math], nije planaran, genus mu je jednak 1 i dr. Protuprimjer je Taitovom 'teoremu' u svezi s problemom četiriju boja: "Svaki 3-regularan graf je 1-faktorabilan". Grupa automorfizama [math]\displaystyle{ Aut(P) }[/math] Petersenova grafa je simetrična grupa [math]\displaystyle{ S_{5} }[/math] te je ukupan broj automorfizama jednak 120. Otkriće Petersenova grafa utjecalo je na razvoj različitih grana moderne teorije grafova.^[1]

Vidi

Izvori

↑ ^1,0 ^1,1 math.e Snježana Majstorović i Luka Boras: Petersenov graf, br. 27. (pristupljeno 25. svibnja 2020.)

[Majstorovi.C4.87.2C_Boras-1] 1,0 ^1,1 math.e Snježana Majstorović i Luka Boras: Petersenov graf, br. 27. (pristupljeno 25. svibnja 2020.)

[1]