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.Encyclopaedia of Mathematics, first Supplementary volume, 1988, , p. 281, article "Halin Graph", and references therein.

A Halin-gráfok Rudolf Halin német matematikusról kapták nevüket, aki 1971-ben tanulmányozta őket,. 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. 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.

Példák

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.: „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.” 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.Lásd , 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.

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.

Tulajdonságai 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ő. 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.

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. 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.Lásd a 10. tétel bizonyítását itt: : „Mivel G tartalmaz 3-kört, ami egy belső és két külső csúcsból áll, G nem páros gráf.”

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..

A négynél nagyobb maximális fokszámú Halin-gráf illeszkedési kromatikus száma .. 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 vagy , az illeszkedési kromatikus szám akár az -öt, illetve -ot is elérheti..

Számítási bonyolultság Adott 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 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.. Egy másik megközelítés szerint egy csúccsal és é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 ciklikus rangjával; ezek mindegyike lineáris időben ellenőrizhető.. 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..

Minden Halin-gráf faszélessége = 3. . 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,. 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. 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..

Története 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. 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. 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.

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,. majd 1965-ben Hans Rademacher foglalkozott.. 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 tartománya egyikének 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, 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..

A Halin-gráfokat néha nevezik „szoknyás fáknak” (skirted trees) vagy „tető nélküli poliédereknek” (roofless polyhedra) is.. 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. Továbbá, ahogy a „based polyhedra”, úgy a „roofless polyhedra” név is utalhat a 3-reguláris Halin-gráfokra is.. Az olyan konvex poliédereket, melyek gráfjai Halin-gráfok, szintén nevezik „kupoláknak” (domes)..

Fordítás

Jegyzetek

További információk Halin graphs, Information System on Graph Class Inclusions.

Kategória:Gráfcsaládok Kategória:Síkgráfok