Kubični graf

Iz Wikipedije, proste enciklopedije
(Preusmerjeno s strani Bikubični graf)
Petersenov graf je kubični graf
Polni dvodelni graf (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 pobarva z največ tremi barvami. Tako ima vsak kubični graf razen neodvisno množico vsaj točk, kjer je š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]

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

  • Foster, Ronald Martin (1932), »Geometrical Circuits of Electrical Networks«, Transactions of the American Institute of Electrical Engineers, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068
  • Isaacs, Rufus Philip (1975), »Infinite families of nontrivial trivalent graphs which are not Tait colorable«, American Mathematical Monthly, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844
  • Tutte, William Thomas (1959), »On the symmetry of cubic graphs«, Canad. J. Math, 11: 621–624, doi:10.4153/CJM-1959-057-2

Zunanje povezave[uredi | uredi kodo]