Merev körű gráf
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ésEgy 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ésA 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ésBá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
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ésAlosztályok
szerkesztésAz 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ésA 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
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- ↑ (Dirac 1961).
- ↑ Weisstein, Eric W.: Triangulated Graph (angol nyelven). Wolfram MathWorld. Ez a megnevezés utalhat viszont a maximális síkgráfokra is.
- ↑ a b Peter Bartlett: Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations:
- ↑ Fulkerson & Gross (1965).
- ↑ Bodlaender, Fellows & Warnow (1992).
- ↑ David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng: Probe Graph Classes, October 17, 2012
- ↑ Berry, Golumbic & Lipshteyn (2007).
- ↑ Szwarcfiter & Bornstein (1994).
- ↑ Maffray (2003).
- ↑ Például (Agnarsson 2003), Remark 2.5 ezt a módszert jól ismertnek nevezi.
- ↑ a b (Patil 1986).
- ↑ [1]
- ↑ Seymour & Weaver (1984).
- ↑ Kaplan, Shamir & Tarjan (1999).
- ↑ Fomin & Villanger (2013).
- ↑ Parra & Scheffler (1997).
- Agnarsson, Geir (2003), "On chordal graphs and their chromatic polynomials", Mathematica Scandinavica 93 (2): 240–246, <http://www.mscand.dk/article/view/14421>.
- Bender, E. A.; Richmond, L. B. & Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A 38 (2): 214–221, DOI 10.1017/S1446788700023077.
- Berry, Anne; Golumbic, Martin Charles & Lipshteyn, Marina (2007), "Recognizing chordal probe graphs and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics 21 (3): 573–591, DOI 10.1137/050637091.
- Bodlaender, H. L.; Fellows, M. R. & Warnow, T. J. (1992), "Two strikes against perfect phylogeny", Proc. of 19th International Colloquium on Automata Languages and Programming, vol. 623, Lecture Notes in Computer Science, pp. 273–283, DOI 10.1007/3-540-55719-9_80.
- Chandran, L. S.; Ibarra, L. & Ruskey, F. et al. (2003), "Enumerating and characterizing the perfect elimination orderings of a chordal graph", Theoretical Computer Science 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4, <http://www.cis.uoguelph.ca/~sawada/papers/chordal.pdf>.
- Dirac, G. A. (1961), "On rigid circuit graphs", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25: 71–76, DOI 10.1007/BF02992776.
- Fomin, Fedor V. & Villanger, Yngve (2013), "Subexponential Parameterized Algorithm for Minimum Fill-In", SIAM J. Comput. 6: 2197–2216, DOI 10.1137/11085390X.
- Fulkerson, D. R. & Gross, O. A. (1965), "Incidence matrices and interval graphs", Pacific J. Math 15: 835–855, doi:10.2140/pjm.1965.15.835, <http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572>[halott link].
- Gavril, Fănică (1974), "The intersection graphs of subtrees in trees are exactly the chordal graphs", Journal of Combinatorial Theory, Series B 16: 47–56, DOI 10.1016/0095-8956(74)90094-X.
- Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press.
- Habib, Michel; McConnell, Ross & Paul, Christophe et al. (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing", Theoretical Computer Science 234: 59–84, doi:10.1016/S0304-3975(97)00241-7, <http://www.cs.colostate.edu/~rmm/lexbfs.ps>.
- Kaplan, Haim; Shamir, Ron & Tarjan, Robert (1999), "Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs", SIAM J. Comput. 5: 1906–1922, DOI 10.1137/S0097539796303044.
- Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A. & Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, vol. 11, CMS Books in Mathematics, Springer-Verlag, pp. 65–84, ISBN 0-387-95434-1, DOI 10.1007/0-387-22444-0_3.
- Parra, Andreas & Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics 79 (1-3): 171–188, DOI 10.1016/S0166-218X(97)00041-3.
- Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences 11 (2–4): 57–64.
- Rose, D.; Lueker, George & Tarjan, Robert E. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (2): 266–283, DOI 10.1137/0205021.
- Seymour, P. D. & Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory 8 (2): 241–251, DOI 10.1002/jgt.3190080206.
- Szwarcfiter, J.L. & Bornstein, C.F. (1994), "Clique graphs of chordal and path graphs", SIAM Journal on Discrete Mathematics 7: 331–336, DOI 10.1137/s0895480191223191.