Kograf

I grafteorin är en kograf , eller en ytterligare reducerbar graf , eller en graf fri från P 4 ,  en graf som kan erhållas från en graf med en enda vertex K 1 genom grafaddition och föreningsoperationer . Således är en familj av kografer den minsta klassen av grafer som innehåller K 1 och är stängd under komplement och förening.

Cographs har upptäckts oberoende av flera författare sedan 1970-talet. De tidigaste omnämnandena finns i Young [1] , Lerchs [2] , Zainsche [3] och Sumner [4] . Dessa grafer kallades D*-grafer [1] , ärftliga Dacey-grafer (efter arbete av James C. Dacey, Jr. på ortomodulära gitter . Se Sumner [4] ) och grafer med två ättlingar till Barlet och Ury [ 5] .

Se boken av Brandstedt, Lie och Spinrad [6] för en mer detaljerad diskussion av kografer, inklusive fakta som ges här.

Definition och beskrivning

Alla kografer kan konstrueras genom att följa följande regler:

  1. Varje enskild hörn av en graf är en kograf;
  2. Om  är en kograf, då är dess komplement också en kograf;
  3. Om och  är kografer, så är deras osammanhängande förening också en kograf.

Flera andra beskrivningar av kografer kan ges. Bland dem:

Alla kompletta grafer , kompletta tvådelade grafer , tröskeldiagram och Turan-grafer är kografer. Varje kograf är en avståndsärvd perfekt jämförbarhetsgraf .

Codetrees

Ett kodträd  är ett träd vars inre hörn är märkta 0 och 1. Varje kodträd T definierar en kograf G som har bladen av T som hörn, och ett underträd med rötter i T motsvarar en genererad subgraf i G definierad av en uppsättning avkomblad denna topp:

Ett likvärdigt sätt att konstruera en kograf från en kodare är att två hörn är förbundna med en kant om och endast om den minst gemensamma förfadern av motsvarande blad är märkt 1. Omvänt kan vilken kograf som helst representeras av en kodare på detta sätt. Om vi ​​kräver att alla etiketter på alla vägar från roten till bladen växlar, blir en sådan representation unik [7] .

Beräkningsegenskaper

En kograf kan kännas igen i linjär tid och en coderee-representation kan konstrueras genom att använda modulär dekomposition [10] , dekompositionsförfining [11] eller delad dekomposition [12] . När kodaren väl har byggts kan många välbekanta grafteoretiska problem lösas genom att korsa kodaren nerifrån och upp.

Till exempel, för att hitta den maximala klicken i en kograf, beräknar vi, från botten till toppen, den maximala klicken i varje subgraf som representeras av ett underträd till kodaren. För varje vertex märkt 0, är ​​den maximala klicken den maximala klick som tas emot från vertexens ättlingar. För en vertex märkt 1 kommer den maximala klicken att vara föreningen av klickarna som beräknas för vertexens avkomlingar, och storleken på denna klick är summan av klickstorlekarna. Genom att växelvis ta den maximala storleken och summera värdena för varje vertex av kodaren, kommer vi att beräkna den maximala klickstorleken, och genom att växelvis välja den maximala klicken och sammanfoga, kommer vi att konstruera själva den maximala klicken. Ett liknande tillvägagångssätt nedifrån och upp gör det möjligt att erhålla den maximala oberoende uppsättningen , kromatiskt antal , maximal klicktäckning och förekomsten av en Hamiltonsk bana i linjär tid. Man kan också använda cotrees för att avgöra i linjär tid om två cographs är isomorfa .

Om H  är en genererad subgraf av en kograf G , så är H själv en kograf. En kodare för H kan erhållas genom att ta bort några av bladen från kodaren för G och sedan slå samman de hörn som har ett enda barn. Det följer av Kruskals trädsats att relationen som ska genereras av en subgraf är en bra kvasiordning på kografer [13] . Så, om en familj av kografer (som plana kografer) stängs under driften av att konstruera en genererad subgraf, så har den ett ändligt antal förbjudna genererade subgrafer . Ur beräkningssynpunkt innebär detta att kontroll av om en graf tillhör en sådan familj kan göras i linjär tid med hjälp av en bottom-up-traversering av den givna grafens kodare.

Anteckningar

  1. ↑ 1 2 3 Jung, 1978 .
  2. ↑ Lerchs, 1971 .
  3. ↑ Seinsche, 1974 .
  4. ↑ 12 Sumner , 1974 .
  5. ↑ Burlet, Uhry, 1984 .
  6. ↑ Brandstädt, Le, Spinrad, 1999 .
  7. ↑ 1 2 Corneil, Lerchs, Burlingham, 1981 .
  8. ↑ Courcelle, Olariu, 2000 .
  9. ↑ Bose, Buss, Lubiw, 1998 .
  10. ↑ Corneil, Perl, Stewart, 1985 .
  11. ↑ Habib, Paul, 2005 .
  12. ↑ Gioan, Paul, 2008 .
  13. ↑ Damaschke, 1990 .

Litteratur

Länkar