Kvartični graf

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

Kvártični gráf je v teoriji grafov graf v katerem imajo vse točke stopnjo enako 4 in je tako 4-regularni graf.[1] Kvartični graf se imenuje tudi štírivaléntni graf. Po lemi o rokovanju je v vsakem regularnem grafu na n točkah s stopnjo r število povezav enako:

tako da je pri kvartičnem grafu število povezav enako dvojnemu številu točk ():

Zgledi[uredi | uredi kodo]

Več dobro znanih grafov je kvartičnih. Med njimi so:

Vsak sredinski graf je kvartični ravninski graf, in vsak kvartični ravninski graf je sredinski graf parov dualnih ravninskih grafov ali multigrafov.[7] Vozelni diagrami in povezavni diagrami so tudi kvartični ravninski multigrafi v katerih točke predstavljajo presekanja diagramov in so označeni z dodatno informacijo, ki pove katera od dveh vej vozla prečka drugo vejo v tisti točki.[8]

Značilnosti[uredi | uredi kodo]

Ker je stopnja vsake točke v kvartičnem grafu soda, ima vsak povezani kvartični graf Eulerjevo pot. In kakor za regularne dvodelne grafe v splošnem ima vsak dvodelni kvartični graf popolno parjenje. V tem primeru je možen veliko preprostejši in hitrejši algoritem za iskanje takšnega parjenja kot pri neregularnih grafih – z zbiranjem katerekoli druge povezave Eulerjeve poti se lahko najde 2-faktor, ki mora v tem primeru biti zbirka krožnic, vsaka z liho dolžino, kjer se vsaka točka grafa pojavi točno v eni krožnici. S ponovno izbiro katerekoli druge povezave v teh krožnicah se lahko dobi popolno parjenje v linearnem času. Enaka metoda se lahko uporabi za barvanje povezav grafa s štirimi barvami v linearnem času.[9]

Kvartični grafi imajo liho število Hamiltonovih dekompozicij.[10]

Število možnih neizomorfnih povezanih kvartičnih grafov na n ≥ 0 točkah je: (OEIS A006820):

1, 0, 0, 0, 0, 1, 1, 2, 6, 16, 59, 265, 1544, 10778, 88168, 805491, 8037418, 86221634, 985870522, 11946487647, 152808063181, 2056692014474, 28566273166527, ...

Pri tem velja, da regularnost ničelnega grafa brez točk (n = 0) ni definirana in je tako lahko poljubna, zato je graf tudi 4-regularen. Na 5-ih in 6-ih točkah sta edina neizomorfna grafa polni graf K5 in oktaedrski graf. Cirkulantna grafa C7(1,2) in C7(1,3) sta med seboj izomorfna. Na 7-ih točkah obstaja le še en tema grafoma neizomorfen graf.

Odprti problemi[uredi | uredi kodo]

Ali imajo vsi kvartični grafi liho število Hamiltonovih ciklov ali imajo več kot enega je odprta domneva. Izjava ne velja za kvartične multigrafe.[11]

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]