Merev körű gráf

A Wikipédiából, a szabad enciklopédiából
(Húrgráf szócikkből átirányítva)
Egy kör (fekete) két húrral (zöld). A gráfnak ez a része húrgráf. Bármelyik zöld élt eltávolítva már nem lenne húrgráf; a másik zöld él a három fekete éllel négy hosszúságú húrmentes kört alkotna.

A matematika, azon belül a gráfelmélet területén egy merev körű gráf vagy húrgráf (chordal graph) olyan gráf, melynek minden négy vagy több csúcsot tartalmazó körének van „húrja”, tehát olyan éle, ami nem része a körnek, de összeköt a körbe tartozó két csúcsot. Ezzel egyenértékű megfogalmazás, hogy a gráf minden feszített köre pontosan három csúcsból állhat. A húrgráfok úgy is jellemezhetők, mint a gráfok, melyek csúcsaira létezik olyan, ún. szimpliciális rendezés (perfect elimination ordering), melyben tetszőleges v csúcs környezetében a rendezésben utána következő csúcsok klikket alkotnak (bármely feszített részgráf tartalmaz szimpliciális csúcsot); a gráfok, melyben minden minimális elvágó csúcshalmaz klikket alkot; illetve amely egy fa részfáinak metszetgráfja. Ismert elnevezéseik közé tartoznak még: kordális gráfok, merev körű gráfok (rigid circuit graphs),[1] háromszögelt gráfok (triangulated graphs),[2] felbontható gráfok (decomposable graphs)[3] vagy átlós gráfok.

A merev körű gráfok a perfekt gráfok részhalmazát alkotják. Polinomiális időben felismerhetők, és számos olyan problémát, ami más gráfosztályokon nehézséget okoz (pl. gráfszínezés) merev körű gráfokon polinom időben meg lehet oldani. Tetszőleges gráf favastagságát jellemzi az őt tartalmazó húrgráfok klikkjeinek mérete.

Szimpliciális rendezés és hatékony felismerés[szerkesztés]

Egy gráf szimpliciális rendezése vagy perfekt eliminációs rendezése (perfect elimination ordering) a csúcsok olyan rendezése, melyben tetszőleges v csúcs környezetében a rendezésben utána következő csúcsok klikket alkotnak. Egy gráf pontosan akkor merev körű gráf, ha létezik perfekt eliminációs rendezése.[4]

(Rose, Lueker & Tarjan 1976) (lásd még Habib et al. 2000) megmutatják, hogy egy húrgráfhoz tartozó szimpliciális rendezés hatékonyan megkereshető lexikografikus szélességi bejárással. Ez az algoritmus fenntartja a gráf csúcsainak csúcshalmazok egy sorozatába való particionálását; a kiinduláskor ez a sorozat egyetlen, az összes csúcsot tartalmazó halmazból áll. Az algoritmus minden lépésben kiválaszt egy v csúcsot a sorozat legkorábbi olyan halmazából, melyből még nem volt csúcs kiválasztva, majd a sorozat minden S halmazát két kisebb részhalmazra bontja fel, melyek közül az első tartalmazza v S-beli szomszédait, a második pedig a nem szomszédos csúcsokat. Mikor ez a felosztási folyamat minden csúcson végigment, a halmazok sorozata halmazonként pontosan egy csúcsot tartalmaz, és éppen a szimpliciális rendezés megfordítását adja.

Mivel lineáris időben elvégezhető a lexikografikus szélességi bejárás, valamint egy rendezés szimpliciális voltának tesztelése is, ezért a húrgráfok lineáris időben felismerhetőek. A húrgráfokra vonatkozó gráfszendvics-probléma NP-teljes[5], míg a próbagráf-probléma[6] polinom idejű.[7]

Egy merev körű gráf összes szimpliciális rendezésének halmaza modellezhető egy antimatroid formális nyelv-reprezentációjának alapszavaival; (Chandran et al. 2003) ezt az antimatroidokkal való kapcsolatot aknázza ki az adott merev körű gráf összes szimpliciális rendezését hatékonyan listázó algoritmusában.

Maximális klikkek és gráfszínezés[szerkesztés]

A szimpliciális rendezés másik alkalmazási területe a merev körű gráfok maximális elemszámú klikkjeinek polinom idejű megkeresése; a probléma általános gráfokban NP-teljes. Általánosabban nézve, egy merev körű gráfnak csak lineárisan sok maximális klikkje lehet, míg az általános gráfokban ez exponenciálisan sok lehet. A merev körű gráf összes maximális klikkjének listázásához csak keresni kell egy szimpliciális rendezést, venni kell minden v csúcsnak a rendezésben v utáni szomszédaival alkotott klikkjét, és ellenőrizni kell, hogy az eredményül kapott klikkek közül melyik a maximális elemszámú.

A merev körű gráfok klikkgráfjai duális húrgráfok.[8]

Mivel a merev körű gráfok perfektek, a maximális elemszámú klikkjük mérete megegyezik a kromatikus számukkal. A merev körű gráfok perfekt rendezhetőek, hiszen a perfekt eliminációs rendezésük megfordítására alkalmazott mohó színezés mindig optimális lesz.[9]

A merev körű gráfok kromatikus polinomja könnyen kiszámítható. Keressünk egy szimpliciális rendezést. Legyen Ni vi azon szomszédainak száma, melyek ebben a rendezésben vi után következnek. Például Nn = 0. A kromatikus polinom értéke (Az utolsó tényező egyszerűen x, ezért x osztója a polinomnak, ahogy annak lennie kell.) Ez a számítás nyilvánvalóan csak merev körű gráfokon működik.[10]

Minimális elvágó csúcshalmazok[szerkesztés]

Bármely gráf elvágó csúcshalmaza a csúcsainak olyan halmaza, mely csúcsok eltávolításával a gráf szétesik; egy elvágó halmaz akkor minimális, ha egyetlen valódi részhalmaza sem elvágó halmaz. (Dirac 1961) tétele szerint a húrgráfok olyan gráfok, melyek minden minimális elvágó csúcshalmaza klikk; Dirac ennek a karakterizációnak a segítségével látta be, hogy valamennyi húrgráf perfekt.

A húrgráfok családja a következő indukciós módszerrel is meghatározható: a gráfok, melyek csúcsai feloszthatók három nem üres A, S és B részhalmazba oly módon, hogy A ∪ S és S ∪ B feszített részgráfjai is húrgráfok, S egy klikk, továbbá A és B között nem húzódnak élek. Tehát a húrgráfok azok a gráfok, melyek elválasztó klikk-csúcshalmazokkal rekurzív módon kisebb részgráfokra bonthatók. Emiatt a húrgráfokat néha felbontható gráfoknak (decomposable graphs) is hívták.[3]

Részfák metszetgráfjai[szerkesztés]

Nyolc csúcsból álló húrgráf reprezentációja egy hat csomópontú fa nyolc részfájának metszetgráfjaként.

Egy (Gavril 1974) által megadott alternatív karakterizáció fák és részfák segítségével írja le a merev körű gráfokat.

Egy fa részfáinak gyűjteményén definiálható egy részfa-gráf, azaz egy metszetgráf, amiben minden részfához egy csúcs tartozik, és él köt össze bármely két részfát, melyek egy vagy több csomópontban megegyeznek. Gavril megmutatta, hogy a részfa-gráfok pontosan megegyeznek a merev körű gráfokkal.

A merev körű gráf a fent leírt módon megalkotott reprezentációja a gráf fafelbontását adja, melyben a favastagság eggyel kisebb a gráf legnagyobb klikkjének méreténél; tetszőleges G gráf fafelbontása úgy is tekinthető, mint G reprezentációja egy merev körű gráf részgráfjaként. Egy gráf fafelbontása egyben a klaszterfa-algoritmusban szereplő klaszterfa.

Más gráfosztályokkal való kapcsolata[szerkesztés]

Alosztályok[szerkesztés]

Az intervallumgráfok a fák egy speciális eseteinek, az útgráfoknak a metszetgráfjai. Ilyenformán ezek is a húrgráfok alesetét adják.

A split gráfok olyan húrgráfok, melyeknek a komplementere is húrgráf. (Bender, Richmond & Wormald 1985) megmutatta, hogy ha n tart a végtelenbe, az n-csúcsú húrgráfok közül a split gráfok aránya az egyhez tart.

A ptolemaioszi gráfok olyan gráfok, melyek egyszerre húrgráfok és távolság-örökletes gráfok. A triviálisan perfekt gráfok a ptolemaioszi gráfok közül azok, melyek egyben kográfok is. A blokkgráfok olyan ptolemaioszi gráfok, melyekben bármely két maximális klikknek legfeljebb egy közös csúcsa lehet. Ezek speciális esetei a szélmalomgráfok, melyekben a közös csúcs minden klikkpár esetében ugyanaz.

Az erősen merev körű gráfok olyan merev körű gráfok, melyek nem tartalmaznak n-napot (ahol n ≥ 3) feszített részgráfként. Itt az n-nap alatt egy G n-csúcsú merev körű gráfot értünk, melyhez hozzávesszük a G Hamilton-körével szomszédos n db 2 fokszámú csúcsot is.

A k-fák olyan merev körű gráfok, melyekben az összes maximális klikk, illetve az összes maximális klikk-elválasztó csúcshalmaz mérete megegyezik.[11] Az Apollóniusz-hálózatok maximális merev körű síkgráfok, vagy ezzel ekvivalensen síkba rajzolható 3-fák.[11] A maximális külsíkgráfok a 2-fák alosztályaként szintén merev körűek.

Bővebb halmazok[szerkesztés]

A húrgráfok a jól ismert perfekt gráfok közé tartoznak. További bővebb halmazok közé tartoznak az erdők, a gyengén merev körű gráfok,[12] a Meyniel-gráfok, a „pandúr győz”-gráfok, a páratlan lyukmentes gráfok és a páros lyuk-mentes gráfok. Valójában a húrgráfok pontosan azok a gráfok, melyek egyszerre páros és páratlan lyukmentesek (feszített részgráfjaik nem tartalmaznak köröket).

Minden húrgráf egyben lekötött gráf is, azaz olyan gráf, melynek minden periferikus köre háromszög; hiszen a periferikus körök csak a feszített körök alesetei. A lekötött gráfok olyan gráfok, melyek húrgráfokból és maximális síkgráfokból előállíthatók a klikk-összeg művelet segítségével. Ezért a lekötött gráfok közé tartoznak a maximális síkgráfok is.[13]

Merev körű kiegészítések és favastagság[szerkesztés]

Bővebben: Merev körű kiegészítés

Ha G egy általános gráf, a G merev körű kiegészítése (chordal completion) (vagy minimális kitöltése – minimum fill-in) egy olyan merev körű gráf, ami G-t részgráfként tartalmazza. A minimális kitöltés parametrizált változata rögzített paraméter mellett kezelhető, továbbá parametrizált szubexponenciális időben megoldható.[14][15] A G favastagsága éppen eggyel kisebb, mint a minimális klikkszámúra választott merev körű kiegészítésének maximális elemszámú klikkje. A k-fák olyan gráfok, melyekhez nem adható él anélkül, hogy favastagságuk k-nál nagyobb értékre növekedjen. Ezért a k-fák saját maguk merev körű kiegészítései, és a merev körű gráfok alosztályát alkotják. A merev körű kiegészítések számos kapcsolódó gráfosztály, például a kográfok és a csillagszerű hármas-mentes gráfok karakterizálására felhasználhatók.[16]

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Chordal 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. ↑ (Dirac 1961).
  2. ↑ Weisstein, Eric W.: Triangulated Graph (angol nyelven). Wolfram MathWorld. Ez a megnevezés utalhat viszont a maximális síkgráfokra is.
  3. ↑ a b Peter Bartlett: Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations:
  4. ↑ Fulkerson & Gross (1965).
  5. ↑ Bodlaender, Fellows & Warnow (1992).
  6. ↑ David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng: Probe Graph Classes, October 17, 2012
  7. ↑ Berry, Golumbic & Lipshteyn (2007).
  8. ↑ Szwarcfiter & Bornstein (1994).
  9. ↑ Maffray (2003).
  10. ↑ Például (Agnarsson 2003), Remark 2.5 ezt a módszert jól ismertnek nevezi.
  11. ↑ a b (Patil 1986).
  12. ↑ [1]
  13. ↑ Seymour & Weaver (1984).
  14. ↑ Kaplan, Shamir & Tarjan (1999).
  15. ↑ Fomin & Villanger (2013).
  16. ↑ Parra & Scheffler (1997).

További információk[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Merev_körű_gráf&oldid=21511765”