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]

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.

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]

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]

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]

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]

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]

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

• Halin graphs, Information System on Graph Class Inclusions.