Merev körű kiegészítés
From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén egy irányítatlan G gráf merev körű kiegészítése vagy húrgráffá kiegészítése (chordal completion) a G-vel megegyező csúcshalmazú merev körű gráf, ami a G-t részgráfként tartalmazza. A minimális merev körű kiegészítés (minimal chordal completion) olyan merev körű kiegészítés, mely bármely élének eltávolítása után már nem lenne merev körű kiegészítés. A minimális élszámú merev körű kiegészítés (minimum chordal completion) az összes merev körű kiegészités közül olyan, ami a lehető legkevesebb éllel rendelkezik.
Egy más jellegű merev körű kiegészítés az eredményül kapott húrgráf maximális elemszámú klikkjét minimalizálja, ami alkalmas a G favastagságának meghatározására. A merev körű kiegészítések számos más gráfosztály karakterizálására is alkalmas, ilyenek például a csillagszerű hármas-mentes (AT-free) gráfok, karommentes és csillagszerű hármas-mentes gráfok, valamint a kográfok.
A minimális élszámú merev körű kiegészítés az 1979-ben megjelent Computers and Intractability c. könyvben megjelent tizenkét azon probléma egyike, melyek komplexitása még ismeretlen. A merev körű kiegészítések alkalmazásai közé tartozik a feltöltődés minimalizálása a ritka szimmetrikus mátrixok Gauss-eliminációja során vagy a leszármazási fák rekonstrukciója.
A gráfok húrgráffá kiegészítését néha háromszögelésnek is nevezik,[1] de ez a megnevezés még a gráfelméleten belül is kétértelmű, hiszen a maximális síkgráfokra is utalhat.
Egy G gráf pontosan akkor csillagszerű hármas-mentes, ha minden minimális húrgráffá kiegészítése intervallumgráf. G pontosan akkor karommentes és csillagszerű hármas-mentes gráf, ha minden minimális húrgráffá kiegészítése valódi intervallumgráf. Továbbá G akkor és csak akkor kográf, ha minden minimális húrgráffá kiegészítése triviálisan perfekt gráf.[1]
Egy G gráf favastagsága pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, melynek maximális elemszámú klikkjének mérete nem nagyobb k + 1-nél. Útszélessége pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, ami intervallumgráf, k + 1-nél nem nagyobb maximális elemszámú klikkel. Sávszélessége pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, ami valódi intervallumgráf, k + 1-nél nem nagyobb maximális elemszámú klikkel.[2] Mélysége pedig pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, ami triviálisan perfekt gráf, k-nál nem nagyobb maximális elemszámú klikkel.[3]
A húrgráffá kiegészítés eredeti alkalmazása a ritka szimmetrikus mátrixok Gauss-eliminációja során jelentkező feltöltődés minimalizálása volt. A Gauss-elimináció során a mátrix korábban nulla értékű együtthatóinak egy része nemnulla értéket vesz fel, ami nemkívánatos folyamat, hiszen a további számoláskor lassítja az algoritmus végrehajtását. Egy ritka szimmetrikus mátrixban ezeknek a nemnulla értékeknek a mintázata leírható egy irányítatlan gráffal, melynek a mátrix a szomszédsági mátrixa; a feltöltődő mátrixban a nemnulla értékek mintázata mindig merev körű gráf, valamely minimális merev körű kiegészítés pedig egy ilyen feltöltődési mintázatnak felel meg. Ha adott egy gráf merev körű kiegészítése, megadható az a lépések sorozata, ami a Gauss-elimináció segítségével előállítja ezt a feltöltődési mintázatot az eredményül kapott merev körű gráf eliminációs rendezésével. Ily módon a minimális feltöltődés problémája ekvivalens a minimális élszámú merev körű kiegészítés problémájával.[4] Ebben az alkalmazásban síkgráfok léphetnek fel kétdimenziós végeselemes rendszerek megoldásaként; a síkgráf-elválasztási tételből adódóan egy n csúcsú síkgráfnak mindig létezik legfeljebb O(n log n) élből álló merev körű kiegészítése.[5]
Másik fő alkalmazási terület a leszármazási fák területe, az evolúciós fák rekonstruálása, legyenek azok a filogenetikus rendszertanban a genetikai mutációknak kitett élőlények leszármazási fái, vagy akár ókori kéziratok manuális másolása során fellépő hibák által meghatározott leszármazási fák. Ha fel lehet tételezni, hogy minden mutáció vagy másolási hiba csak egyetlenegyszer fordul elő, tökéletes leszármazási fa nyerhető, melyben a valamely speciális tulajdonsággal rendelkező fajok vagy kéziratok mindig egy összefüggő részfát alkotnak. (Buneman 1974) megállapítása szerint a tökéletes leszármazási fa merev körű kiegészítési problémaként modellezhető. Megadunk egy G „átfedési gráfot” (overlap graph), melynek csúcsai az attribútumértékek (a faj vagy kézirat valamely karakterisztikus értéke), az élek pedig olyan attribútumpárokat jelképeznek, melyek legalább még egy fajban jelen vannak. A gráf csúcsai színezhető az egyes attribútumok karakterisztikájának azonosságai szerint, így a színek száma megegyezik a leszármazási fában szereplő karakterisztikák számával. A tökéletes leszármazási fa pontosan akkor létezik, ha G rendelkezik a színezést tiszteletben tartó merev körű kiegészítéssel.[6]
Bár az 1979-es Computers and Intractability megoldatlanként kezeli,[7] a minimális élszámú merev körű kiegészítés problémája (avagy a minimális feltöltődés (minimum fill-in) probléma) bonyolultsága gyorsan eldőlt: (Yannakakis 1981) igazolta, hogy NP-teljes.[8] Ha a minimális élszámú merev körű kiegészítés k éllel bővíti a G gráfot, akkor polinom idejű algoritmussal lehetséges találni legfeljebb 8k2 élt felhasználó merev körű kiegészítést.[9] Az optimális hozzáadandó k élhalmaz megkeresése rögzített paraméter mellett kezelhető, a gráf méretét tekintve polinom időben, k-ban pedig szubexponenciálisan.[10]
A favastagság (a merev körű kiegészítés minimális klikkmérete) és a kapcsolódó paraméterek, mint az útszélesség és a fa mélysége szintén NP-teljesek, és (hacsaknem P=NP) optimális értékük nem közelíthető polinom időben konstans faktorral; léteznek azonban logaritmikus közelítési arányt elérő approximációs algoritmusok hozzájuk.[11]
Mind a minimális feltöltés, mind a favastagság problémája exponenciális időben megoldhatók. Precízebben, egy n-csúcsú gráfban a szükséges idő O(1,9601n).[12]
- Ez a szócikk részben vagy egészben a Chordal completion 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
