Wikipédia

Halin-gráf

matematikai fogalom a gráfelméletben

A matematika, azon belül a gráfelmélet területén a Halin-gráfok olyan síkbarajzolható gráfok, melyek egy fa leveleinek körré történő összehúzásával állíthatók elő. A fának legalább négy csúcsból kell állnia, a csúcsok egyikének sem lehet pontosan két szomszédja; le kell rajzolni az euklideszi síkba úgy, hogy élei ne messék egymást (ezt nevezik síkba ágyazásnak), a kör pedig ennek a beágyazásnak a leveleit köti össze az óramutató járása szerint. Így a kör alkotja a Halin-gráf külső tartományát, benne egy fával.[1]

Egy Halin-gráf

A Halin-gráfok Rudolf Halin német matematikusról kapták nevüket, aki 1971-ben tanulmányozta őket,[2] bár a 3-reguláris Halin-gráfokat – melyekben minden csúcs fokszáma pontosan három – már egy évszázaddal korábban Kirkman vizsgálta.[3] Ezek poliédergráfok, tehát minden Halin-gráf előáll egy konvex poliéder csúcsaiból és éleiből; ezeket a poliédereket „tető nélküli poliédereknek” (roofless polyhedra) vagy „kupoláknak” (domes) nevezik.

Minden Halin-gráfban található az összes csúcson átmenő, ún. Hamilton-kör, ahogy a csúcsok számáig bezárólag szinte az összes lehetséges hosszúságú kör is. A Halin-gráfok lineáris időben felismerhetők. Mivel faszélességük alacsony, az általános gráfokon nehéznek számító feladatok közül többet – például a Hamilton-körök keresését – gyorsan meg lehet oldani rajtuk.

Háromszög alapú hasáb, hat csúcsú fából Halin-gráfként előállítva.

Példák szerkesztés

 
Kerékgráfok

Egy csillaggráf olyan fa, aminek pontosan egy belső csúcsa van. A Halin-gráf konstrukciós lépését csillaggráfra alkalmazva kerékgráfot kapunk, a gúla vagy piramis gráfját.[4] A háromszög alapú hasáb gráfja szintén Halin-gráf: lerajzolható úgy, hogy az egyik téglalap alakú tartománya a külső kört alkossa, a maradék élek pedig egy négy levélből, két belső csúcsból és öt élből álló fát alkossanak.[5]

A Frucht-gráf, a két legkisebb, nemtriviális gráfautomorfizmus nélküli 3-reguláris gráf egyike, szintén Halin-gráf.[6]

Tulajdonságai szerkesztés

Minden Halin-gráf 3-szorosan összefüggő, tehát két csúcs törlésével a gráf nem esik szét több részre. Élminimális 3-összefüggő gráf, tehát bármely élének törlésével a gráf már nem lenne 3-összefüggő.[1] A Steinitz-tétel alapján, mint minden 3-összefüggő, síkbarajzolható gráfra, a Halin-gráfokra is igaz, hogy ábrázolhatók egy konvex poliéder csúcsaiként és éleiként; azaz poliédergráfként. Mint a poliédergráfoknál általában, síkba rajzolásuk egyedi a külsőnek választott tartomány erejéig.[1]

Minden Halin-gráfnak van Hamilton-köre, és a gráf minden éle beletartozik egy Hamilton-körbe. Továbbá minden Halin-gráfra igaz, hogy egy csúcsának törlése után is hamiltoni marad.[7] Mivel a 2 fokszámú csúcsok nélküli fáknak van legalább két, ugyanabból a szülő csúcsból származó levele, ezért minden Halin-gráf tartalmaz háromszöget. Egy Halin-gráf nem lehet háromszögmentes, sem páros gráf.[8]

 
8-kör nélküli Halin-gráf. Hasonló konstrukcióval bármely páros körhosszúság elkerülhető.[9]

Ennél erősebb állítás, hogy a Halin-gráfok csaknem pánciklikusak, amennyiben 3 és n között mindenféle hosszúságú kört tartalmaznak, egyetlen páros hosszúság esetleges kivételével. Egyetlen él összehúzása után a Halin-gráfok megtartják csaknem pánciklikusságukat, és a harmadfokú belső csúcs nélküli Halin-gráfok kivétel nélkül pánciklikusak.[10]

A négynél nagyobb Δ(G) maximális fokszámú G Halin-gráf illeszkedési kromatikus száma Δ(G) + 1.[11] Az illeszkedési kromatikus szám az ahhoz szükséges színek száma, hogy az összes (v,e) pár ki legyen színezve, ahol v a gráf egy csúcsa, e pedig a csúcsra illeszkedő él, a színezésnél bizonyos feltételeknek eleget téve. A megegyező csúcsot, vagy megegyező élt tartalmazó párak nem lehetnek azonos színűek. Ezen kívül, egy (v,e) párosnak nem egyezhet meg a színe olyan párral sem, ami az e másik végpontját tartalmazza. Az olyan Halin-gráfokon, ahol Δ(G) = 3 vagy 4, az illeszkedési kromatikus szám akár az 5-öt, illetve 6-ot is elérheti.[12]

Számítási bonyolultság szerkesztés

Adott n csúcsú gráfról lineáris időben eldönthető, hogy Halin-gráf-e, a gráf síkba rajzolásának előállításával (amennyiben az létezik), majd annak vizsgálatával, hogy létezik-e a síkba rajzolásnak olyan tartománya, amiben legalább n/2 + 1 csúcs van, mind harmadfokú. Ha igen, legfeljebb négy ilyen tartomány létezhet, az pedig mindegyik esetében lineáris időben vizsgálható, hogy a gráf maradéka fát alkot-e, melynek az ebbe a tartományba nyúló csúcsok a levelei. Amennyiben ilyen tartomány nem létezik, a gráf nem Halin-gráf.[13] Egy másik megközelítés szerint egy n csúccsal és m éllel rendelkező gráf pontosan akkor Halin-gráf, ha síkbarajzolható, 3-összefüggő, és van olyan tartománya, amiben a csúcsok száma megegyezik a gráf m − n + 1 ciklikus rangjával; ezek mindegyike lineáris időben ellenőrizhető.[14] A Halin-gráfok lineáris idejű felismeréséhez segítségül hívható a Courcelle-tétel, vagy egy gráfújraíráson alapuló módszer, melyek egyike sem foglalkozik a gráf síkba ágyazásával.[15]

Minden Halin-gráf faszélessége = 3.[16] Ezért több olyan gráfoptimalizálási probléma, ami tetszőleges síkbarajzolható gráfokon NP-teljes, például a maximális elemszámú független csúcshalmaz-probléma Halin-gráfokon lineáris időben megoldható akár dinamikus programozás,[17] akár a Courcelle-tétel segítségével, vagy néhány esetben (mint a Hamilton-körök konstrukciója esetén) közvetlen algoritmikus módon.[15] Azonban NP-teljes feladat adott gráf legnagyobb Halin-részgráfjának megkeresése, annak vizsgálata, hogy létezik-e adott gráf minden csúcsát tartalmazó Halin-részgráf, vagy hogy adott gráf részgráfja-e egy nagyobb Halin-gráfnak.[18]

Története szerkesztés

1971-ben Halin bevezette a minimális 3-csúcsösszefüggő gráfokat: a gráf bármelyik élének eltávolítása csökkenti a gráf összefüggőségét.[2] Ezeknek a Halin-gráfoknak megnőtt a jelentőségük, mikor felfedezték, hogy a tetszőleges síkbarajzolható gráfokon megvalósíthatatlanul számításigényes algoritmikus problémák hatékonyan megoldhatók rajtuk.[7][14] Ezt később megmagyarázták alacsony faszélességükkel, és a Courcelle-tételhez hasonló algoritmikus meta-tételek segítségével, melyek bármely alacsony faszélességű gráfra hatékony megoldásokat nyújtanak.[16][17]

Még Halin gráfelméleti kutatásait jóval megelőzően a 3-reguláris Halin-gráfok leszámlálási problémáival 1856-ban Thomas Kirkman,[3] majd 1965-ben Hans Rademacher foglalkozott.[19] Rademacher ezeket a gráfokat alapos poliéder (based polyhedra) névvel illette. Definíciója szerint ezek a 3-reguláris poliédergráfok, melyek f tartománya egyikének f − 1 oldala van. A definíciónak pontosan a 3-reguláris Halin-gráfok felelnek meg.

Megihletve attól, hogy a Halin-gráfok és a 4-összefüggő síkbarajzolható gráfok is tartalmaznak Hamilton-köröket, (Lovász & Plummer 1974) azt a sejtést állították fel, miszerint minden 4-szeresen összefüggő síkbarajzolható gráf tartalmaz feszítő Halin-részgráfot; itt a „feszítő” úgy értendő, hogy a részgráf tartalmazza a nagyobb gráf összes csúcsát. A Lovász–Plummer-sejtés 2015-ig eldöntetlen volt, ekkor találtak egy végtelen sok ellenpéldát nyújtó konstrukciót.[20]

A Halin-gráfokat néha nevezik „szoknyás fáknak” (skirted trees)[9] vagy „tető nélküli poliédereknek” (roofless polyhedra) is.[7] Ezek a nevek azonban kétértelműek. Egyes szerzők ugyanis a „skirted trees” alatt a fák leveleinek körbe kötésével kapott síkba rajzolható gráfokat értik, de annak megkövetelése nélkül, hogy a belső csúcsok fokszáma legalább három legyen.[21] Továbbá, ahogy a „based polyhedra”, úgy a „roofless polyhedra” név is utalhat a 3-reguláris Halin-gráfokra is.[22] Az olyan konvex poliédereket, melyek gráfjai Halin-gráfok, szintén nevezik „kupoláknak” (domes).[23]

Fordítás szerkesztés

  • Ez a szócikk részben vagy egészben a Halin 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. ↑ a b c Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0-7923-4709-9, p. 281, article "Halin Graph", and references therein.
  2. ↑ a b Halin, R. (1971), "Studies on minimally n-connected graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 129–136.
  3. ↑ a b Kirkman, Th. P. (1856), "On the enumeration of x-edra having triedral summits and an (x − 1)-gonal base", Philosophical Transactions of the Royal Society of London: 399–411, DOI 10.1098/rstl.1856.0018.
  4. ↑ (Cornuéjols, Naddef & Pulleyblank 1983): „Ha T csillag, tehát egyetlen v csúcs, ami n másik csúccsal van összekötve, akkor H egy kerék, és a legegyszerűbb fajtája a Halin-gráfoknak.”
  5. ↑ Lásd (Sysło & Proskurowski 1983), Prop. 4.3, p. 254, ami azonosítja a háromszög alapú hasábot azzal az egyetlen gráffal, amiben három kör van, ami egy Halin-gráf megvalósításának külső köre lehet.
  6. ↑ Weisstein, Eric W.: Halin Graph (angol nyelven). Wolfram MathWorld
  7. ↑ a b c Cornuéjols, G.; Naddef, D. & Pulleyblank, W. R. (1983), "Halin graphs and the travelling salesman problem", Mathematical Programming 26 (3): 287–294, DOI 10.1007/BF02591867.
  8. ↑ Lásd a 10. tétel bizonyítását itt: Wang, Weifan; Bu, Yuehua & Montassier, Mickaël et al. (2012), "On backbone coloring of graphs", Journal of Combinatorial Optimization 23 (1): 79–93, DOI 10.1007/s10878-010-9342-6: „Mivel G tartalmaz 3-kört, ami egy belső és két külső csúcsból áll, G nem páros gráf.”
  9. ↑ a b Malkevitch, Joseph (1978), "Cycle lengths in polytopal graphs", Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) (Berlin: Springer) 642: 364–370, DOI 10.1007/BFb0070393
  10. ↑ Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R. & Godsil, Christopher D., Cycles in Graphs, vol. 27, Annals of Discrete Mathematics, Elsevier Science Publishers B.V., pp. 179–194.
  11. ↑ Wang, Shu-Dong; Chen, Dong-Ling & Pang, Shan-Chen (2002), "The incidence coloring number of Halin graphs and outerplanar graphs", Discrete Mathematics 256 (1-2): 397–405, DOI 10.1016/S0012-365X(01)00302-8.
  12. ↑ Shiu, W. C. & Sun, P. K. (2008), "Invalid proofs on incidence coloring", Discrete Mathematics 308 (24): 6575–6580, DOI 10.1016/j.disc.2007.11.030.
  13. ↑ Fomin, Fedor V. & Thilikos, Dimitrios M. (2006), "A 3-approximation for the pathwidth of Halin graphs", Journal of Discrete Algorithms 4 (4): 499–510, DOI 10.1016/j.jda.2005.06.004.
  14. ↑ a b Sysło, Maciej M. & Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 248–256, DOI 10.1007/BFb0071635.
  15. ↑ a b Eppstein, David (2016), "Simple recognition of Halin graphs and their generalizations", Journal of Graph Algorithms and Applications 20 (2): 323–346, DOI 10.7155/jgaa.00395.
  16. ↑ a b Bodlaender, Hans (1988), Planar graphs with bounded treewidth, Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, <http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf>. Hozzáférés ideje: 2019-01-14 Archiválva 2004. július 28-i dátummal a Wayback Machine-ben Archivált másolat. [2004. július 28-i dátummal az eredetiből archiválva]. (Hozzáférés: 2019. január 14.).
  17. ↑ a b Bodlaender, Hans (1988), "Dynamic programming on graphs with bounded treewidth", Proceedings of the 15th International Colloquium on Automata, Languages and Programming, vol. 317, Lecture Notes in Computer Science, Springer-Verlag, pp. 105–118, ISBN 978-3540194880, DOI 10.1007/3-540-19488-6_110.
  18. ↑ Horton, S. B. & Parker, R. Gary (1995), "On Halin subgraphs and supergraphs", Discrete Applied Mathematics 56 (1): 19–35, DOI 10.1016/0166-218X(93)E0131-H.
  19. ↑ Rademacher, Hans (1965), "On the number of certain types of polyhedra", Illinois Journal of Mathematics 9: 361–380, <http://projecteuclid.org/euclid.ijm/1256068140>.
  20. ↑ Chen, Guantao; Enomoto, Hikoe & Ozeki, Kenta et al. (2015), "Plane triangulations without a spanning Halin subgraph: counterexamples to the Lovász-Plummer conjecture on Halin graphs", SIAM Journal on Discrete Mathematics 29 (3): 1423–1426, DOI 10.1137/140971610.
  21. ↑ Skowrońska, M. & Sysło, M. M. (1987), "Hamiltonian cycles in skirted trees", Polska Akademia Nauk 19 (3-4): 599–610 (1988)
  22. ↑ Lovász, L. & Plummer, M. D. (1974), "On a family of planar bicritical graphs", Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London: Cambridge Univ. Press, pp. 103–107. London Math. Soc. Lecture Note Ser., No. 13.
  23. ↑ Demaine, Erik D.; Demaine, Martin L. & Uehara, Ryuhei (2013), "Zipper unfolding of domes and prismoids", Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, pp. 43–48, <http://erikdemaine.org/papers/ZipperDomes_CCCG2013/>.

További információk szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Halin-gráf&oldid=26550760”