Ackordsgraf

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2021; verifiering kräver 1 redigering .

I grafteorin kallas en graf för ackord om var och en av dess cykler , som har fyra eller fler kanter, har ett ackord (en kant som förbinder två hörn av cykeln, men inte är en del av den).

En motsvarande definition är om någon cykel utan ackord har högst tre kanter. Med andra ord är en ackordsgraf en graf utan genererade cykler med längd större än tre.

Ackordsgrafer är en delmängd av perfekta grafer . De kallas också ibland cykliskt stela grafer [1] eller triangulerade grafer . (Den senare termen används ibland felaktigt för plan triangulering. Se maximala plana grafer .) [2]

Perfekt eliminering och effektiv igenkänning av ackordsgrafer

En perfekt uteslutningsordning i en graf är ordningen för grafens hörn så att v , v och grannarna till v som är efter v i ordningen bildar en klick för varje vertex . En graf är ackord om och endast om den har en perfekt uteslutningsordning [3]

Rose, Lucker och Tarjan (1976) [4] (se även Habib, McConnell, Paul, Vienneno (2000) [5] ) visade att den perfekta elimineringsordningen för en ackordsgraf effektivt kan hittas med hjälp av en algoritm som kallas lexikografisk bredd- första sökningen . Denna algoritm delar upp grafens hörn i en sekvens av uppsättningar. Ursprungligen består sekvensen av en enda uppsättning som innehåller alla hörn. Algoritmen i slingan väljer vertex v från den äldsta mängden i sekvensen som innehåller de hörn som ännu inte är valda, och delar upp varje set S i sekvensen i två mindre - den ena består av grannarna till vertexen v i S , den andra inkluderar alla återstående hörn. När divisionsprocessen utförs för alla hörn, innehåller alla uppsättningar av sekvensen en hörn vardera och bildar en sekvens omvänd till den perfekta elimineringsordningen.

Eftersom både den lexikografiska bredd-först-sökningen och att kontrollera om en ordning är perfekt undantag kan göras i linjär tid, är det möjligt att känna igen en ackordsgraf i linjär tid. Sandwichproblemet på en ackordsgraf är NP-komplett [6] , medan testgrafproblemet på en ackordsgraf har polynom-tidskomplexitet [7] .

Uppsättningen av alla perfekta uteslutningsordningar för en ackordsgraf kan betraktas som basorden för en antimatroid . Chandran et al [8] använde denna koppling till antimatroider som en del av en algoritm för att effektivt räkna upp alla perfekta uteslutningsordningar för en given ackordsgraf.

Största klickar och graffärgning

En annan applikation för perfekt elimineringsordning är att hitta den maximala klicken för en ackordsgraf i polynomtid, medan för allmänna grafer samma problem är NP-komplett (en ackordsgraf kan bara ha linjärt många största klick , medan icke-ackordala grafer kan ha exponentiellt många av dem). För att få en lista över alla de största klicken i en ackordsgraf räcker det att hitta den perfekta elimineringsordningen, konstruera en klick för varje vertex v från alla angränsande hörn i ordning efter v och kontrollera om den resulterande klicken är största.

Den största klicken som har den maximala storleken är den maximala klicken, och eftersom ackordsgrafer är perfekta är storleken på denna klick lika med det kromatiska numret på ackordsgrafen. Ackordsgrafer är välordnade  - den optimala färgningen kan erhållas med den giriga färgningsalgoritmen , som tar hörnen i omvänd ordning till perfekt eliminering. [9]

Minsta avgränsare

I vilken graf som helst är en vertexseparator  en uppsättning hörn vars borttagning gör att den återstående grafen kopplas bort. En separator är minimal om den inte innehåller en delmängd som också är en separator. Enligt Diracs teorem [1] är ackordsgrafer grafer där varje minimal separator är en klick. Dirac använde denna egenskap för att bevisa att ackordsgrafer är perfekta .

En familj av ackordsgrafer kan definieras som uppsättningen grafer vars hörn kan delas in i tre icke-tomma delmängder A , S , och B så att A  ∪  S och S  ∪  B båda bildar ackordalgenererade subgrafer , S är en klick, och det finns inga kanter som förbinder A och B. _ Detta är alltså grafer som tillåter rekursiv uppdelning i mindre subgrafer med hjälp av klick. Av denna anledning kallas ackordsgrafer ibland nedbrytbara grafer . [tio]

Skärning av underträdsgrafer

En annan egenskap hos ackordsgrafer [11] använder träd och deras underträd.

Från en uppsättning underträd av ett träd kan man bestämma en underträdsgraf  - en skärningsgraf , vars hörn motsvarar ett underträd och en kant förbinder två underträd om de har en eller flera gemensamma kanter. Gavril visade att underträdsgrafer är exakt ackordsgrafer.

Att representera ackordsgrafer som en underträdsskärningsgraf bildar en uppdelning av grafen till träd med en trädbredd som är en mindre än storleken på grafens största klick. Nedbrytningen av vilken graf G som helst till träd kan betraktas som en representation av grafen G som en subgraf till kordalgrafen. Att sönderdela en graf i träd är också ett unionsträd i konfidensutbredningsalgoritmen .

Relation till andra klasser av grafer

Underklasser

Intervallgrafer  är underträdsskärningsgrafer , ett specialfall av träd. Således är intervallgrafer en underfamilj av ackordsgrafer.

Delade grafer är både ackord i sig och är komplement till ackordsgrafer. Bender, Richmond och Wormald (1985) [12] visade att eftersom n tenderar mot oändligheten tenderar bråkdelen av ackordsgrafer med n hörn som är delade mot en.

Ptolemaiosgrafer är grafer som är både kordala och avståndsärvda . Kvasitröskelgrafer är en underklass av ptolemaiska grafer som är både ackordala och kografiska . Blockgrafer  är en annan underklass av ptolemaiska grafer där vilka två största klick som helst har en gemensam vertex. Ett specialfall är kvarnar , som har samma vertex för vilket par av klick som helst.

Strengt ackordsgrafer  är grafer som är ackordala och inte innehåller en n-sol ( n ≥ 3) som genererade subgrafer.

K-träd  är ackordsgrafer vars största klick och största klickseparatorer alla har samma storlek. [13] Apollonius-grafer  är ackordala maximala plana grafer , eller, ekvivalent, plana 3-träd. [13] Maximala ytterplanära grafer  är en underklass av 2-träd och därför också kordala.

Superklasser

Ackordsgrafer är en underklass av välkända perfekta grafer . Andra superklasser av ackordsgrafer inkluderar svaga ackordsgrafer, grafer utan udda hål och grafer utan jämna hål . I själva verket är ackordsgrafer exakt grafer, både utan jämna hål och utan udda hål (se hål i grafteori).

Varje kordagraf är sammandragen , d.v.s. en graf där varje perifer cykel är en triangel, eftersom perifera cykler är ett specialfall av en genererad cykel. Sammandragna grafer kan bildas av klicksummor av ackordsgrafer och maximala ackordsgrafer. Sammandragna grafer inkluderar således maximala plana grafer . [fjorton]

Anteckningar

  1. 1 2 G. A. Dirac. På stela kretsdiagram // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. - 1961. - T. 25 . — S. 71–76 . - doi : 10.1007/BF02992776 . .
  2. Weisstein, Eric W. Triangulated Graph  på Wolfram MathWorld- webbplatsen .
  3. D.R. Fulkerson, OA Gross. Incidensmatriser och intervallgrafer // Pacific J. Math. - 1965. - T. 15 . S. 835–855 . .
  4. D. Rose, George Lueker, Robert E. Tarjan. Algoritmiska aspekter av vertexeliminering på grafer // SIAM Journal on Computing. - 1976. - V. 5 , nr. 2 . — S. 266–283 . - doi : 10.1137/0205021 . .
  5. Michel Habib, Ross McConnell, Christophe Paul, Laurent Viennot. Lex-BFS och partitionsförfining, med applikationer för transitiv orientering, intervallgrafigenkänning och konsekutiva tester // Teoretisk datavetenskap. - 2000. - T. 234 . — s. 59–84 . - doi : 10.1016/S0304-3975(97)00241-7 . .
  6. HL Bodlaender, MR Fellows, TJ Warnow. Två slag mot perfekt fylogeni, Proc. av 19:e internationella kollokviet om automatspråk och programmering. — 1992. .
  7. Anne Berry, Martin Charles Golumbic, Marina Lipshteyn. Identifiera ackordsondsgrafer och cykliska tvåfärgsgrafer // SIAM Journal on Discrete Mathematics. - 2007. - T. 21 , nr. 3 . — S. 573–591 . - doi : 10.1137/050637091 . .
  8. LS Chandran, L. Ibarra, F. Ruskey, J. Sawada. Räkna upp och karakterisera de perfekta elimineringsordningarna för en ackordsgraf // Teoretisk datavetenskap. - 2003. - T. 307 , nr. 2 . — S. 303–317 . - doi : 10.1016/S0304-3975(03)00221-4 . .
  9. Frederic Maffray. Senaste framsteg inom algoritmer och kombinatorik / redaktörer: Bruce A. Reed, Claudia L. Sales. - Springer-Verlag, 2003. - T. 11. - S. 65–84. - (CMS-böcker i matematik). ISBN 0-387-95434-1 . - doi : 10.1007/0-387-22444-0_3 . .
  10. Peter Bartlett. Oriktade grafiska modeller: ackordsgrafer, nedbrytbara grafer, korsningsträd och faktoriseringar: .
  11. Fănică Gavril. Skärningsgraferna för underträd i träd är exakt ackordsgraferna // Edition of Combinatorial Theory, Series B. - 1974. - Vol 16 . s. 47–56 . - doi : 10.1016/0095-8956(74)90094-X . .
  12. EA Bender, LB Richmond, NC Wormald. Nästan alla ackordsgrafer splittras // J. Austral. Matematik. Soc .. - 1985. - T. 38 , nr. 2 . — S. 214–221 . - doi : 10.1017/S1446788700023077 . .
  13. 12 H. P. Patil . Om strukturen av k -träd // Edition of Combinatorics, Information and System Sciences. - 1986. - T. 11 , nr. 2–4 . s. 57–64 . .
  14. P.D. Seymour, R.W. Weaver. En generalisering av ackordsgrafer // Edition of Graph Theory. - 1984. - T. 8 , nr. 2 . — S. 241–251 . - doi : 10.1002/jgt.3190080206 . .

Litteratur

Länkar