Ugrás a tartalomhoz

3-reguláris gráf

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
A Petersen-gráf egy 3-reguláris gráf.
A teljes páros gráf a páros 3-reguláris („bicubic”) gráfok közé tartozik

A matematika, azon belül a gráfelmélet területén egy 3-reguláris gráf vagy trivalens gráf, esetleg kubikus gráf (cubic graph, trivalent graph, 3-regular graph) olyan reguláris gráf, melyben minden csúcs fokszáma három.

A páros 3-reguláris gráfok angol nyelvterületen saját nevet kaptak: bicubic graph.

Szimmetria

[szerkesztés]

1932-ben Ronald M. Foster elkezdte gyűjteni a 3-reguláris szimmetrikus gráfokat, ami később a Foster censussá nőtte ki magát.[1] A jól ismert, egyedi gráfok közül jó néhány 3-reguláris és szimmetrikus: ilyen például a három ház–három kút-gráf, a Petersen-gráf, a Heawood-gráf, a Möbius–Kantor-gráf, a Papposz-gráf, a Desargues-gráf, a Nauru-gráf, a Coxeter-gráf, a Tutte–Coxeter-gráf, a Dyck-gráf, a Foster-gráf és a Biggs–Smith-gráf is. W. T. Tutte a szimmetrikus 3-reguláris gráfokat azon legkisebb s egész paraméterük szerint osztályozta, melyre igaz, hogy a gráf két, s hosszúságú irányított útját a gráf pontosan egy szimmetriája képezi le egymásba. Megmutatta, hogy s legfeljebb 5 lehet, és példákkal szolgált az s lehetséges értékeit 1-től 5-ig fölvevő gráfokra is.[2]

A félszimmetrikus 3-reguláris gráfok közé tartozik a Gray-gráf (a legkisebb félszimmetrikus 3-reguláris gráf), a Ljubljana-gráf és a Tutte 12-cage.

A Frucht-gráf a semmilyen szimmetriával nem rendelkező két legkisebb 3-reguláris gráf egyike: egyetlen gráfautomorfizmussal rendelkezik, az identitással.

Színezés és független csúcshalmazok

[szerkesztés]

A Brooks-tétel szerint a K4 teljes gráfon kívül az összes, összefüggő 3-reguláris gráf kiszínezhető legfeljebb három színnel. Ebből az is következik, hogy a K4-en kívüli összefüggő 3-reguláris gráf rendelkezik n/3 csúcsból álló független halmazzal, ahol n a gráf csúcsainak száma: egy 3-színezés legnagyobb színosztályában például mindig található legalább ennyi csúcs.

A Vizing-tétel értelmében minden 3-reguláris gráf élszínezéséhez elegendő 3 vagy 4 szín. A 3-élszínezést Tait-színezésnek nevezik, és a gráf éleit három teljes párosításba osztja szét. A Kőnig-tételből következik, hogy minden 3-reguláris páros gráf rendelkezik Tait-színezéssel.

Az olyan hídmentes 3-reguláris gráfokat, melyek nem rendelkeznek Tait-színezéssel (élkromatikus számuk 4), snarkoknak nevezik. A snarkok közé tartozik a Petersen-gráf, a Tietze-gráf, a Blanuša-snarkok, a virág-snarkok, a kettőscsillag-snark, a Szekeres-snark és a Watkins-snark. Végtelen számú különböző snark létezik.[3]

Topológia és geometria

[szerkesztés]

A 3-reguláris gráfok a topológia területén számos helyen előbukkannak. A 3-reguláris gráfok előállnak a háromdimenziós egyszerű poliéderek gráfjaiként – ezek a poliéderek, mint amilyen a szabályos dodekaéder is, azzal a tulajdonsággal rendelkeznek, hogy minden csúcsukban pontosan három lapjuk találkozik.

Síkba ágyazás reprezentációja gráfkódolt térképként

Egy kétdimenziós felületbe történő bármely gráfbeágyazás reprezentálható egy 3-reguláris gráfstruktúrával, amit gráfkódolt térképnek (graph-encoded map, gem) neveznek. Ebben a struktúrában a gráf minden csúcsa a beágyazás egy flagjét (kölcsönösen szomszédos csúcs-él-lap hármasát) reprezentálja. Minden flag három szomszédja az a három flag, ami előállítható a kölcsönösen szomszédos három tag valamelyikének megváltoztatásával a másik kettő változatlanul hagyásával.[4]

Hamilton-kör létezése

[szerkesztés]

Sokan vizsgálták már a 3-reguláris gráfok Hamilton-köreit. 1880-ban P.G. Tait felállította sejtését, miszerint minden poliédergráfnak van Hamilton-útja. William Thomas Tutte 1946-ban hozott a Tait-sejtésre ellenpéldát, a 46 csúcsú Tutte-gráfot. Tutte 1971-es sejtése szerint minden páros, 3-reguláris gráfnak van Hamilton-köre. Erre Joseph Horton hozott ellenpéldát, a 96 csúcsú Horton-gráfot.[5] Mark Ellingham később két további ellenpéldát konstruált: ezek az Ellingham–Horton-gráfok.[6][7] A Barnette-sejtés, Tait és Tutte sejtéseinek még eldöntetlen kombinációja szerint minden páros, 3-reguláris poliédergráfnak van Hamilton-köre. Ha egy 3-reguláris gráfnak van Hamilton-köre, az LCF-jelölés segítségével röviden lehet hivatkozni rá.

Ha egy 3-reguláris gráfot egyenletes eloszlás szerint véletlenszerűen kiválasztunk az összes n-csúcsú 3-reguláris gráf közül, nagyon valószínű, hogy lesz Hamilton-köre: az n-csúcsú 3-reguláris gráfok közül a Hamilton-körrel rendelkezők aránya egyhez tart, ahogy n a végtelenhez.[8]

David Eppstein sejtése szerint az n-csúcsú 3-reguláris gráfok legfeljebb 2n/3 (azaz kb. 1,260n) különböző Hamilton-körrel rendelkeznek; Eppstein megadott gráfokat, melyekre ténylegesen teljesül az egyenlőség.[9] A legjobb bizonyított felső becslés a különböző Hamilton-körök számára .[10]

Egyéb tulajdonságok

[szerkesztés]
A matematika megoldatlan problémája:
Mi egy -csúcsú 3-reguláris gráf legnagyobb lehetséges útszélessége?
(A matematika további megoldatlan problémái)

Egy n-csúcsú 3-reguláris gráf útszélessége legfeljebb n/6. Az útszélesség spektrális gráfelméleti eszközökkel megállapított, egyben elő is forduló alsó korlátja 0,082n. Nem ismert, hogyan lehetne ezen alsó korlát és az n/6 felső korlát közötti intervallumot szűkíteni.[11]

Az Euler által 1736-ban bizonyított kézfogás-lemma következménye, hogy minden 3-reguláris gráf páros számú csúccsal rendelkezik.

A Petersen-tétel kimondja, hogy minden 3-reguláris, hídmentes gráfnak van teljes párosítása.[12] Lovász és Plummer sejtése szerint minden 3-reguláris hídmentes gráfnak a csúcsok száma szerint exponenciálisan növekvő számú teljes párosítása van. A sejtés bizonyítását 2011-ben publikálták, megmutatva, hogy a 3-reguláris hídmentes, n csúcsú gráfok legalább 2n/3656 teljes párosítással rendelkeznek.[13]

Algoritmusok és bonyolultság

[szerkesztés]

Sokan vizsgálták az általános esetben exponenciális időt igénybe vevő algoritmusok komplexitását abban az esetben, ha 3-reguláris gráfokra korlátozzuk őket. Például a gráf útfelbontásán dinamikus programozás alkalmazásával Fomin és Høie megmutatták, hogy találhatók meg a maximális elemszámú független halmazok 2n/6 + o(n) időben.[11] Az utazó ügynök problémája 3-reguláris gráfokon O(1,2312n) időben és polinom tárban megoldható.[14][15]

Számos gráfoptimalizálási probléma APX-nehéz, ami azt jelenti, hogy bár léteznek közelítő algoritmusok, melyek approximációs rátájának konstans korlátja van, nincs olyan polinomiális approximációs sémájuk, melyben az arány 1-hez tart, hacsak nem P=NP. Az ilyen problémák közé tartozik a minimális csúcslefedés, a maximális elemszámú független csúcshalmaz, a minimális domináló halmaz és a maximális vágás megkeresése.[16] A metszési szám (síkba rajzoláskor az élek metszéspontjainak lehetséges minimális száma) meghatározása 3-reguláris gráfoknál is NP-nehéz, de approximálható.[17] Az utazó ügynök problémájának 3-reguláris gráfokon való approximációja NP-nehéz, ha a közelítés faktora kisebb 1153/1152-nél.[18]

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben a Cubic graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

[szerkesztés]
  1. ↑ Foster, R. M. (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.
  2. ↑ Tutte, W. T. (1959), "On the symmetry of cubic graphs", Can. J. Math 11: 621–624, doi:10.4153/CJM-1959-057-2, <http://cms.math.ca/cjm/v11/p621> Archiválva 2011. július 16-i dátummal a Wayback Machine-ben.
  3. ↑ Isaacs, R. (1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable", American Mathematical Monthly 82 (3): 221–239, DOI 10.2307/2319844.
  4. ↑ Bonnington, C. Paul & Little, Charles H. C. (1995), The Foundations of Topological Graph Theory, Springer-Verlag.
  5. ↑ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
  6. ↑ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  7. ↑ Ellingham, M. N. & Horton, J. D. (1983), "Non-Hamiltonian 3-connected cubic bipartite graphs", Journal of Combinatorial Theory, Series B 34 (3): 350–353, DOI 10.1016/0095-8956(83)90046-1.
  8. ↑ Robinson, R.W. & Wormald, N.C. (1994), "Almost all regular graphs are Hamiltonian", Random Structures and Algorithms 5 (2): 363–374, DOI 10.1002/rsa.3240050209.
  9. ↑ Eppstein, David (2007), "The traveling salesman problem for cubic graphs", Journal of Graph Algorithms and Applications 11 (1): 61–81, doi:10.7155/jgaa.00137, <http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf>.
  10. ↑ Gebauer, H. (2008), "On the number of Hamilton cycles in bounded degree graphs", Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), <https://epubs.siam.org/doi/pdf/10.1137/1.9781611972986.8>.
  11. ↑ a b Fomin, Fedor V. & Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters 97 (5): 191–196, DOI 10.1016/j.ipl.2005.10.012.
  12. ↑ Petersen, Julius Peter Christian (1891), "Die Theorie der regulären Graphs (The theory of regular graphs)", Acta Mathematica 15 (15): 193–220, DOI 10.1007/BF02392606.
  13. ↑ Esperet, Louis; Kardoš, František & King, Andrew D. et al. (2011), "Exponentially many perfect matchings in cubic graphs", Advances in Mathematics 227 (4): 1646–1664, DOI 10.1016/j.aim.2011.03.015.
  14. ↑ Xiao, Mingyu & Nagamochi, Hiroshi (2013), "An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure", Theory and Applications of Models of Computation, vol. 7876, Lecture Notes in Computer Science, Springer-Verlag, pp. 96–107, ISBN 978-3-642-38236-9, DOI 10.1007/978-3-642-38236-9_10.
  15. ↑ Xiao, Mingyu & Nagamochi, Hiroshi (2012), An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.
  16. ↑ Alimonti, Paola & Kann, Viggo (2000), "Some APX-completeness results for cubic graphs", Theoretical Computer Science 237 (1–2): 123–134, DOI 10.1016/S0304-3975(98)00158-3.
  17. ↑ Hliněný, Petr (2006), "Crossing number is hard for cubic graphs", Journal of Combinatorial Theory, Series B 96 (4): 455–471, DOI 10.1016/j.jctb.2005.09.009.
  18. ↑ Karpinski, Marek & Schmied, Richard (2013), Approximation Hardness of Graphic TSP on Cubic Graphs.

További információk

[szerkesztés]
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=3-reguláris_gráf&oldid=27314682”