sl.wikipedia.org

Kvartični graf - Wikipedija, prosta enciklopedija

Iz Wikipedije, proste enciklopedije

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:

{\displaystyle e={\frac {nr}{2}}\!\,,}

tako da je pri kvartičnem grafu število povezav enako dvojnemu številu točk ({\displaystyle r=4\,}):

{\displaystyle e=2n\!\,.}

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]

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.

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]