Pojdi na vsebino

Kvartični graf

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:

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]
  • Bondy, John Adrian; Häggkvist, Roland (1981), »Edge-disjoint Hamilton cycles in 4-regular planar graphs«, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007/BF02190157, MR 0623315
  • Brinkmann, Gunnar; Meringer, Markus (1997), »The Smallest 4-Regular 4-Chromatic Graphs with Girth 5«, Graph Theory Notes of New York, 32: 40–41
  • Chvátal, Václav (1970), »The smallest triangle-free 4-chromatic 4-regular graph«, Journal of Combinatorial Theory, 9 (1): 93–94, doi:10.1016/S0021-9800(70)80057-6
  • Fleischner, Herbert (1994), »Uniqueness of maximal dominating cycles in 3-regular graphs and of Hamiltonian cycles in 4-regular graphs«, Journal of Graph Theory, 18 (5): 449–459, doi:10.1002/jgt.3190180503, MR 1283310
  • Folkman, Jon (1967), »Regular line-symmetric graphs«, Journal of Combinatorial Theory, 3: 215–232, doi:10.1016/s0021-9800(67)80069-3, MR 0224498
  • Gabow, Harold N. (1976), »Using Euler partitions to edge color bipartite multigraphs«, International Journal of Computer and Information Sciences, 5 (4): 345–355, doi:10.1007/bf00998632, MR 0422081
  • Meredith, Guy H. J. (1973), »Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs«, Journal of Combinatorial Theory, Series B, 14: 55–60, doi:10.1016/s0095-8956(73)80006-1, MR 0311503
  • Robertson, Neil (1964), »The Smallest Graph of Girth 5 and Valency 4«, Bull. Amer. Math. Soc., 70: 824–825
  • Thomason, Andrew Gordon (1978), »Hamiltonian cycles and uniquely edge colourable graphs«, Annals of Discrete Mathematics, 3: 259–268, doi:10.1016/s0167-5060(08)70511-9, MR 0499124
  • Toida, Šuniči (1974), »Construction of quartic graphs«, Journal of Combinatorial Theory, Series B, 16: 124–133, doi:10.1016/0095-8956(74)90054-9, MR 0347693
  • Welsh, Dominic J. A. (1993), »The complexity of knots«, Quo vadis, graph theory?, Annals of Discrete Mathematics, zv. 55, Amsterdam: North-Holland, str. 159–171, doi:10.1016/S0167-5060(08)70385-6, MR 1217989

Zunanje povezave

[uredi | uredi kodo]