Petersenov graf

Petersenov graf, vrsta je grafa iz teorije grafova koji posjeduje niz 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[uredi | uredi kôd]

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 $K_{5}$ i $K_{3,3}$ , 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 $Aut(P)$ Petersenova grafa je simetrična grupa $S_{5}$ te je ukupan broj automorfizama jednak 120. Otkriće Petersenova grafa utjecalo je na razvoj različitih grana moderne teorije grafova.^[1]

Vidi[uredi | uredi kôd]

Izvori[uredi | uredi kôd]

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

[Majstorović,_Boras-1] th.e Snježana Majstorović i Luka Boras: Petersenov graf, br. 27. (pristupljeno 25. svibnja 2020.)

[1]