Kubični graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Petersenov graf je kubični graf
Polni dvodelni graf K_{3,3} (graf napeljav) je zgled bikubičnega grafa

Kúbični gráf je v teoriji grafov graf v katerem imajo vse točke stopnjo enako 3 in je tako 3-regularni graf. Kubični graf se imenuje tudi trívaléntni graf.

Bíkúbični gráf je kubični dvodelni graf.

Simetrija[uredi | uredi kodo]

Leta 1932 je Ronald Martin Foster začel zbirati primere kubičnih simetričnih grafov in sestavil Fosterjev popis.[1] Veliko znanih posameznih grafov je kubičnih in simetričnih. Med njimi so najbolj znani: graf napeljav, Petersenov, Heawoodov, Möbius-Kantorjev, Paposov, Desarguesov, Naurujski, Coxetrov, Tutte-Coxetrov, Dyckov, Fosterjev in Biggs-Smithov. William Thomas Tutte je klasificiral simetrične kubične grafe glede na najmanjše takšno celo število s, da se lahko vsaki usmerjeni povezavi z dolžino s preslikajo druga v drugo s točno eno simetrijo grafa. Pokazal je, da je s lahko največ 5 in podal primere grafov za vsako možno vrednost s od 1 do 5.[2]

Med polsimetrične kubične grafe spadajo: Grayjev (najmanjši polsimetrični kubični graf), Jofinove in Ivanova, Ljubljanski in Tuttejeva 12-kletka.

Fruchtov graf je eden od dveh najmanjših kubičnih grafov brez simetrije - ima le en avtomorfizem, enotski avtomorfizem.

Barvanje in neodvisne množice[uredi | uredi kodo]

Po Brooksovem izreku se lahko vsak kubični graf razen polni graf K_{4}\, pobarva z največ tremi barvami. Tako ima vsak kubični graf razen K_{4}\, neodvisno množico vsaj n/3\, točk, kjer je n\, število točk v grafu: največji barvni razred v 3-barvanju ima vsaj toliko točk.

Po Vizingovem izreku se za barvanje povezav potrebuje tri ali štiri barve. 3-točkovno-barvanje je znano kot Taitovo barvanje in tvori particijo točk grafa v tri popolna parjenja. Po Kőnigovem izreku o barvanju povezav ima vsak bikubični graf Taitovo barvanje.

Kubični grafi brez mostov, ki nimajo Taitovega barvanja, so znani kot snarki. Najbolj znani snarki so: Petersenov graf, Tietzejev graf, Blanuševa snarka, cvetlični snark, snark dvojna zvezda, Szekeresov snark in Watkinsov snark. Obstaja neskončno mnogo različnih snarkov.[3]

Opombe in sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]