Akkorddiagram - Chordal graph
I det matematiska området för grafteori är ett ackorddiagram en där alla cykler med fyra eller fler hörn har ett ackord , vilket är en kant som inte ingår i cykeln men förbinder två hörnpunkter i cykeln. Likaså bör varje inducerad cykel i diagrammet ha exakt tre hörn. Akkorddiagrammen kan också karaktäriseras som diagrammen som har perfekta eliminationsordningar, som diagrammen där varje minimiseparator är en klick och som korsningsdiagrammen för ett träds underträd. De kallas ibland också styva kretsdiagram eller triangulerade grafer .
Akkorddiagram är en delmängd av de perfekta graferna . De kan kännas igen linjärt och flera problem som är svåra för andra klasser av grafer, såsom graffärgning, kan lösas i polynomtid när ingången är ackordal. Den treewidth för en godtycklig graf kan kännetecknas av storleken på klickarna i de ackord grafer som innehåller det.
Perfekt eliminering och effektivt erkännande
En perfekt eliminationsordning i en graf är en ordning av kurvorna i diagrammet så att för varje toppunkt v , v och grannarna till v som inträffar efter v i ordningen bildar en klick . En graf är ackordal om och endast om den har en perfekt eliminationsordning.
Rose, Lueker & Tarjan (1976) (se även Habib et al. 2000 ) visar att en perfekt eliminationsordning av ett ackorddiagram kan hittas effektivt med hjälp av en algoritm som kallas lexikografisk bredd-första sökning . Denna algoritm upprätthåller en partition av kurvorna i diagrammet i en uppsättning sekvenser; initialt består denna sekvens av en enda uppsättning med alla hörn. Algoritmen väljer upprepade gånger ett vertex v från den tidigaste uppsättningen i sekvensen som innehåller tidigare icke valda hörn och delar upp varje uppsättning S i sekvensen i två mindre delmängder, den första består av grannarna till v i S och den andra består av den icke -grannar. När denna delningsprocess har utförts för alla hörn, har sekvensen för uppsättningar ett toppunkt per uppsättning, i motsats till en perfekt eliminationsordning.
Eftersom både den här lexikografiska bredden första sökprocessen och processen att testa huruvida en ordning är en perfekt eliminationsordning kan utföras i linjär tid är det möjligt att känna igen ackorddiagram i linjär tid. Den graf sandwich problem på ackord grafer är NP-komplett medan sond grafen problem på ackord grafer har polynomial-time komplexitet.
Uppsättningen av alla perfekta eliminationsordningar i ett ackorddiagram kan modelleras som grundord för en antimatroid ; Chandran et al. (2003) använder denna anslutning till antimatroider som en del av en algoritm för att effektivt lista alla perfekta eliminationsordningar för en given ackordgraf.
Maximala klick och graffärgning
En annan tillämpning av perfekta eliminationsordningar är att hitta en maximal klick av ett ackorddiagram i polynomtid, medan samma problem för allmänna grafer är NP-komplett . Mer allmänt kan ett ackorddiagram endast ha linjärt många maximala klick , medan icke-ackorddiagram kan ha exponentiellt många. För att lista alla maximala klick i ett ackorddiagram, hitta helt enkelt en perfekt eliminationsordning, bilda en klick för varje toppunkt v tillsammans med grannarna till v som är senare än v i den perfekta eliminationsordningen och testa om var och en av de resulterande klickarna är maximal.
De Clique grafer av ackord grafer är dubbelt ackord grafer .
Den största maximala klicken är en maximal klick, och eftersom ackorddiagram är perfekta, är storleken på denna klick lika med ackorddiagrammets kromatiska antal . Akkorddiagram är perfekt beställbara : en optimal färgning kan erhållas genom att tillämpa en girig färgningsalgoritm på topparna i motsatsen till en perfekt eliminationsordning.
Det kromatiska polynomet i ett ackorddiagram är lätt att beräkna. Hitta en perfekt eliminationsordning Låt N i vara lika med grannarna till v i som kommer efter v i den ordningen. Till exempel, N n = 0. Det kromatiska polynomet är lika med (Den sista faktorn är helt enkelt x , så x delar polynomet, som det borde.) Det är uppenbart att denna beräkning beror på ackordalitet.
Minsta avgränsare
I vilket diagram som helst är en vertexavgränsare en uppsättning vertikaler vars avlägsnande lämnar kvarvarande graf urkopplad; en separator är minimal om den inte har någon korrekt delmängd som också är en separator. Enligt en teorem från Dirac (1961) är ackorddiagram grafer där varje minimal separator är en klick; Dirac använde denna karakterisering för att bevisa att ackorddiagram är perfekta .
Familjen med ackorddiagram kan definieras induktivt som diagrammen vars hörn kan delas in i tre icke-fria underuppsättningar A , S och B , så att A ∪ S och S ∪ B båda bildar ackordinducerade underbilder , S är en klick och där finns inga kanter från A till B . Det vill säga de är graferna som har en rekursiv sönderdelning av klickseparatorer i mindre underbilder. Av denna anledning har ackorddiagram ibland också kallats nedbrytbara grafer .
Korsningsdiagram över underträd
En alternativ karaktärisering av ackorddiagram, på grund av Gavril (1974) , involverar träd och deras underträd.
Från en samling underträd i ett träd kan man definiera ett underträdsdiagram , vilket är ett korsningsdiagram som har ett toppunkt per underträd och en kant som förbinder två subträd som överlappar varandra i en eller flera noder i trädet. Gavril visade att underträdsdiagrammen är exakt ackorddiagrammen.
En representation av en korda-graf som en skärning av underträd bildar en träd sönderdelning av grafen, med treewidth lika med ett mindre än storleken på den största klicken i diagrammet; trädnedbrytningen av vilken graf som helst G kan ses på detta sätt som en representation av G som en subgraf till ett ackorddiagram. Trädnedbrytningen av en graf är också korsningsträdet för korsningsträdets algoritm .
Förhållande till andra diagramklasser
Underklasser
Intervall grafer är skärnings grafer av underträd av väg grafer , ett specialfall av träd. Därför är de en underfamilj av ackorddiagram.
Delade grafer är grafer som är både ackordala och komplement till ackorddiagram. Bender, Richmond & Wormald (1985) visade att, i gränsen när n går till oändlighet, närmar sig fraktionen av n-vertexkorddiagram som delas en.
Ptolemaiska grafer är grafer som är både ackordala och avståndsarvliga . Kvasitröskeldiagram är en underklass av ptolemaiska grafer som är både ackord- och grafer . Blockdiagram är en annan underklass av Ptolemaic-grafer där varannan maximala klick har högst ett toppunkt gemensamt. En speciell typ är diagram över väderkvarnar , där det gemensamma toppunktet är detsamma för varje par klick.
Starkt ackorddiagram är diagram som är ackordala och innehåller ingen n- sol (för n ≥ 3) som en inducerad subgraf. Här en n -sun är en n -vertex ackord graf G tillsammans med en samling av n grad två hörn, som gränsar till kanterna av en Hamiltoncykeln i G .
K- träd är ackorddiagram där alla maximala klick och alla maximala klickseparatorer har samma storlek. Apolloniska nätverk är ackordala maximala plana grafer , eller motsvarande plana 3-träd. Maximala yttre plana grafer är en underklass av 2-träd och är därför också ackordala.
Superklasser
Akkorddiagram är en underklass av de välkända perfekta graferna . Andra superklasser med ackorddiagram inkluderar svagt ackorddiagram, cop-win-grafer , udda hålfria grafer, jämnt hålfria grafer och Meyniel-grafer . Akkorddiagram är exakt diagrammen som är både udda hålfria och jämna hålfria (se hål i grafteorin).
Varje ackorddiagram är en strangulerad graf , en graf där varje perifer cykel är en triangel, eftersom perifera cykler är ett speciellt fall av inducerade cykler. Strangulerade grafer är grafer som kan bildas av klicksummor av ackorddiagram och maximala plana grafer. Därför inkluderar strangulerade grafer maximala plana grafer .
Ackordiska kompletteringar och trebredd
Om G är ett godtyckligt diagram är en ackordutfyllning av G (eller minsta utfyllnad ) ett ackorddiagram som innehåller G som subgraf. Den parametrerade versionen av minsta utfyllnad är fast parameter som kan hanteras och dessutom är lösbar på parametrerad subexponentiell tid. Den treewidth av G är ett mindre än antalet hörn i en maximal klick av en korda-avslutad väljs för att minimera denna klick storlek. De k -träd är grafer för vilka inga ytterligare kanter kan läggas utan att öka deras treewidth till ett nummer som är större än k . Därför är k- träden deras egna ackordkompletteringar och bildar en underklass av ackorddiagrammen. Akkordiska kompletteringar kan också användas för att karakterisera flera andra relaterade diagramklasser.
Anteckningar
Referenser
- Agnarsson, Geir (2003), "On chordal graphs and their chromatic polynomials" , Mathematica Scandinavica , 93 (2): 240–246, doi : 10.7146 / math.scand.a-14421 , MR 2009583.
- Bender, EA; Richmond, LB; Wormald, NC (1985), "Nästan alla ackorddiagram delas", J. Austral. Matematik. Soc. , A, 38 (2): 214-221, doi : 10.1017 / S1446788700023077 , MR 0770128.
- Berge, Claude (1967), "Några klasser av perfekta grafer", i Harary, Frank (red.), Grafteori och teoretisk fysik , Academic Press, s. 155–165, MR 0232694.
- Berry, Anne; Golumbic, Martin Charles ; Lipshteyn, Marina (2007), "Recognizing chordal probe charts and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics , 21 (3): 573–591, doi : 10.1137 / 050637091.
- Bodlaender, HL ; Fellows, MR ; Warnow, TJ (1992), "Två strejker mot perfekt fylogeni" (PDF) , Proc. av det 19: e internationella kollokviet om automataspråk och programmering , föreläsningsanteckningar inom datavetenskap, 623 , s. 273–283, doi : 10.1007 / 3-540-55719-9_80 , hdl : 1874/16653.
- Chandran, LS; Ibarra, L .; Ruskey, F .; Sawada, J. (2003), "Att räkna upp och karakterisera de perfekta eliminationsordningarna för ett ackorddiagram" (PDF) , Teoretisk datavetenskap , 307 (2): 303–317, doi : 10.1016 / S0304-3975 (03) 00221- 4.
- Dirac, GA (1961), "On rigid circuit charts" (PDF) , Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 25 (1–2): 71–76, doi : 10.1007 / BF02992776 , MR 0130190 , S2CID 120608513.
- Fomin, Fedor V .; Villanger, Yngve (2013), "Subexponential Parameterized Algorithm for Minimum Fill-In", SIAM J. Comput. , 42 (6): 2197-2216, arXiv : 1104.2230 , doi : 10.1137 / 11085390X , S2CID 934546.
- Fulkerson, DR ; Gross, OA (1965), "Incidensmatriser och intervalldiagram" , Pacific J. Math. , 15 (3): 835–855, doi : 10.2140 / pjm.1965.15.835.
- Gavril, Fănică (1974), "Korsningsdiagrammen för underträd i träd är exakt ackorddiagrammen", Journal of Combinatorial Theory , serie B, 16 : 47–56, doi : 10.1016 / 0095-8956 (74) 90094-X.
- Golumbic, Martin Charles (1980), algoritmisk grafteori och perfekta grafer , Academic Press.
- Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS och partitionförfining, med tillämpningar på transitiv orientering, intervalldiagrigenkänning och på varandra följande testning" , Teoretisk datavetenskap , 234 (1–2): 59–84, doi : 10.1016 / S0304-3975 (97) 00241-7.
- Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs", SIAM J. Comput. , 28 (5): 1906–1922, doi : 10.1137 / S0097539796303044.
- Maffray, Frédéric (2003), "On the coloration of perfect charts", i Reed, Bruce A .; Försäljning, Cláudia L. (red.), Senaste framstegen inom algoritmer och kombinatorik , CMS-böcker i matematik, 11 , Springer-Verlag, s. 65–84, doi : 10.1007 / 0-387-22444-0_3 , ISBN 0-387-95434-1.
- Parra, Andreas; Scheffler, Petra (1997), "Karaktäriseringar och algoritmiska tillämpningar av kordliga grafinbäddningar", Diskret tillämpad matematik , 79 (1–3): 171–188, doi : 10.1016 / S0166-218X (97) 00041-3 , MR 1478250.
- Patil, HP (1986), "On the structure of k -trees", Journal of Combinatorics, Information and System Sciences , 11 (2–4): 57–64, MR 0966069.
- Rose, D .; Lueker, George; Tarjan, Robert E. (1976), "Algoritmiska aspekter av vertexeliminering på grafer", SIAM Journal on Computing , 5 (2): 266-283, doi : 10.1137 / 0205021 , MR 0408312.
- Seymour, PD ; Weaver, RW (1984), "A generalization of chordal charts", Journal of Graph Theory , 8 (2): 241–251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
- Szwarcfiter, JL ; Bornstein, CF (1994), "Clique graphs of chordal and path charts", SIAM Journal on Discrete Mathematics , 7 (2): 331–336, doi : 10.1137 / s0895480191223191 , hdl : 11422/1497.