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:
- Varje enskild hörn av en graf är en kograf;
- Om är en kograf, då är dess komplement också en kograf;
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![\overline{G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56491b3b8403461a746482cb3eb0d8e2ecbbd7d9)
- Om och är kografer, så är deras osammanhängande förening också en kograf.
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![H](https://wikimedia.org/api/rest_v1/media/math/render/svg/75a9edddcca2f782014371f75dca39d7e13a9c1b)
![G\kopp H](https://wikimedia.org/api/rest_v1/media/math/render/svg/343e9f3223aab0e75d322b91f23a12de760e2eac)
Flera andra beskrivningar av kografer kan ges. Bland dem:
- En kograf är en graf som inte innehåller en väg P 4 med 4 hörn (det vill säga längd 3) som en genererad subgraf . Således är en graf en kograf om och endast om för fyra hörn , om och är kanter på grafen, då är åtminstone en av eller också en kant [7] .
![v_1,v_2,v_3,v_4](https://wikimedia.org/api/rest_v1/media/math/render/svg/0572d54bc7bf62912bf7d43417835dfca33e7e09)
![\{v_1,v_2\},\{v_2,v_3\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ba6145bd8b81ceb47b83a9ccec4cf1519e8edff)
![\{v_3,v_4\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48ec39df010b3ba5bd0b9a92d0e2d3ffdf6b0a53)
![\{v_1,v_3\},\{v_1,v_4\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3406137ce6a92f9a4508a48f8fde23fe815b60b)
![\{v_2,v_4\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67f67e4f50ba6339ef2f670e67bd7a3704501d65)
- En kograf är en graf vars alla genererade subgrafer har egenskapen att varje maximal klick skär varje största oberoende uppsättning vid en enda vertex.
- En kograf är en graf där varje icke-trivial genererad subgraf har minst två hörn med sammanfallande kvarter.
- En kograf är en graf där varje ansluten genererad subgraf har ett frånkopplat komplement.
- En kograf är en graf vars alla anslutna inducerade subgrafer har en diameter på högst 2.
- En kograf är en graf där varje ansluten komponent är en avståndsärvd graf med en diameter på högst 2.
- En kograf är en graf med en klickbredd som inte överstiger 2 [8] .
- En kograf är en jämförbarhetsgraf av en seriell-parallell partiell ordning [1] .
- En kograf är en permutationsgraf av en separerbar permutation [9] .
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 underträd som består av ett enda blad motsvarar en genererad subgraf med en enda vertex.
- Underträdet som är rotat i vertexet med etikett 0 motsvarar föreningen av subgraferna som bildas av vertexens avkomlingar.
- Underträdet som är rotat i vertexet med etikett 1 motsvarar anslutningen av subgrafer som bildas av vertexens avkomlingar. Det vill säga, vi bildar en förening och lägger till en kant mellan två valfria hörn som motsvarar två löv som ligger i olika underträd. Man kan också tänka på en sammanfogning som komplementet till alla grafer som bildas av föreningen av komplementen, följt av att konstruera komplementet till den resulterande föreningen.
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 2 3 Jung, 1978 .
- ↑ Lerchs, 1971 .
- ↑ Seinsche, 1974 .
- ↑ 12 Sumner , 1974 .
- ↑ Burlet, Uhry, 1984 .
- ↑ Brandstädt, Le, Spinrad, 1999 .
- ↑ 1 2 Corneil, Lerchs, Burlingham, 1981 .
- ↑ Courcelle, Olariu, 2000 .
- ↑ Bose, Buss, Lubiw, 1998 .
- ↑ Corneil, Perl, Stewart, 1985 .
- ↑ Habib, Paul, 2005 .
- ↑ Gioan, Paul, 2008 .
- ↑ Damaschke, 1990 .
Litteratur
- Prosenjit Bose, Jonathan Buss, Anna Lubiw. Mönstermatchning för permutationer // Information Processing Letters . - 1998. - T. 65 . - S. 277-283 . - doi : 10.1016/S0020-0190(97)00209-3 .
- Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Grafklasser: En undersökning. - SIAM Monographs on Discrete Mathematics and Applications, 1999. - ISBN 978-0-89871-432-6 .
- M. Burlet, JP Uhry. Ämnen om Perfect Graphs. - 1984. - T. 21 . - S. 253-277 .
- DG Corneil, H. Lerchs, L. Stewart Burlingham. Komplettera reducerbara grafer // Diskret tillämpad matematik. - 1981. - T. 3 , nr. 3 . - S. 163-174 . - doi : 10.1016/0166-218X(81)90013-5 .
- D.G. Corneil, Y. Perl, L.K. Stewart. En linjär igenkänningsalgoritm för kografer // SIAM Journal on Computing. - 1985. - T. 14 , nr. 4 . - S. 926-934 . - doi : 10.1137/0214065 .
- B. Courcelle, S. Olariu. Övre gränser för klickbredden av grafer // Diskret tillämpad matematik. - 2000. - T. 101 , nr. 1-3 . - S. 77-144 . - doi : 10.1016/S0166-218X(99)00184-5 .
- Peter Damaschke. Inducerade subgrafer och väl kvasiordnande // Journal of Graph Theory. - 1990. - T. 14 , nr. 4 . - S. 427-435 . - doi : 10.1002/jgt.3190140406 .
- Emeric Gioan, Christophe Paul. Delad nedbrytning och grafmärkta träd: karakteriseringar och helt dynamiska [ sic ] algoritmer för helt nedbrytbara grafer. — 2008.
- Michel Habib, Christophe Paul. En enkel linjär tidsalgoritm för kografigenkänning // Discrete Applied Mathematics. - 2005. - T. 145 , nr. 2 . - S. 183-197 . - doi : 10.1016/j.dam.2004.01.011 .
- H.A. Jung. På en klass av posetter och motsvarande jämförbarhetsgrafer // Journal of Combinatorial Theory, Series B. - 1978. - Vol. 24 , nr. 2 . - S. 125-133 . - doi : 10.1016/0095-8956(78)90013-8 .
- H. Lerchs. På klickar och kärnor. — 1971.
- D. Seinsche. På en egenskap av klassen n -färgbara grafer // Journal of Combinatorial Theory, Series B. - 1974. - Vol. 16 , nr. 2 . - S. 191-193 . - doi : 10.1016/0095-8956(74)90063-X .
- D.P. Sumner. Dacey grafer // J. Austral. Matematik. Soc.. - 1974. - V. 18 , nr. 04 . - S. 492-502 . - doi : 10.1017/S1446788700029232 .
Länkar