Kograf

I grafteori er en cograph , eller en yderligere reducerbar graf , eller en graf fri for P4 , en graf , der kan fås fra en graf med et enkelt toppunkt K 1 ved grafaddition og foreningsoperationer . En familie af kografer er således den mindste klasse af grafer, der indeholder K 1 og er lukket under komplement og forening.

Cographs er blevet opdaget uafhængigt af flere forfattere siden 1970'erne. De tidligste omtaler kan findes hos Young [1] , Lerchs [2] , Zainsche [3] og Sumner [4] . Disse grafer blev kaldt D*-grafer [1] , arvelige Dacey-grafer (efter arbejdet af James C. Dacey, Jr. på ortomodulære gitter . Se Sumner [4] ) og grafer med to efterkommere af Barlet og Ury [ 5] .

Se bogen af Brandstedt, Lie og Spinrad [6] for en mere detaljeret diskussion af kografer, herunder fakta givet her.

Definition og beskrivelse

Enhver kograf kan konstrueres ved at følge følgende regler:

Ethvert enkelt toppunkt på en graf er en kograf;
Hvis er en cograph, så er dens komplement også en cograph; $G$ $\overline{G}$
Hvis og er kografer, så er deres usammenhængende forening også en kograf. $G$ $H$ $G\kop H$

Der kan gives flere andre beskrivelser af kografer. Blandt dem:

En kograf er en graf, der ikke indeholder en sti P 4 med 4 hjørner (det vil sige længde 3) som en genereret undergraf . En graf er således en kograf, hvis og kun hvis for fire hjørner , hvis og er kanter af grafen, så er mindst én af eller også en kant [7] . $v_1,v_2,v_3,v_4$ $\{v_1,v_2\},\{v_2,v_3\}$ $\{v_3,v_4\}$ $\{v_1,v_3\},\{v_1,v_4\}$ $\{v_2,v_4\}$
En kograf er en graf, hvis alle genererede undergrafer har den egenskab, at enhver maksimal klike skærer ethvert største uafhængige sæt ved et enkelt toppunkt.
En kograf er en graf, hvor enhver ikke-triviel genereret undergraf har mindst to hjørner med sammenfaldende kvarterer.
En kograf er en graf, hvor enhver forbundet genereret subgraf har et frakoblet komplement.
En kograf er en graf, hvis alle forbundne inducerede subgrafer har en diameter på højst 2.
En kograf er en graf, hvor enhver forbundet komponent er en afstandsarvet graf med en diameter på højst 2.
En kograf er en graf med klikbredde, der ikke overstiger 2 [8] .
En kograf er en sammenlignelighedsgraf af en seriel-parallel partiel orden [1] .
En kograf er en permutationsgraf af en separerbar permutation [9] .

Alle komplette grafer , komplette todelte grafer , tærskelgrafer og Turan-grafer er kografer. Enhver kograf er en afstandsnedarvet perfekt sammenlignelighedsgraf .

Codetrees

Et kodetræ er et træ, hvis indre hjørner er mærket 0 og 1. Ethvert kodetræ T definerer en kograf G , der har bladene af T som knudepunkter, og et undertræ med rod til T svarer til en genereret undergraf i G defineret af et sæt efterkommerblade denne top:

Et undertræ bestående af et enkelt blad svarer til en genereret undergraf med et enkelt toppunkt.
Undertræet, der er forankret i toppunktet med etiket 0, svarer til foreningen af undergraferne dannet af toppunktets efterkommere.
Undertræet forankret i toppunktet med etiket 1 svarer til forbindelsen af subgrafer dannet af toppunktets efterkommere. Det vil sige, at vi danner en forening og tilføjer en kant mellem to vilkårlige hjørner svarende til to blade, der ligger i forskellige undertræer. Man kan også tænke på en joinforbindelse som komplementet af alle grafer dannet af foreningen af komplementerne, efterfulgt af at konstruere komplementet af den resulterende union.

En ækvivalent måde at konstruere en kograf fra en indkoder er, at to hjørner er forbundet med en kant, hvis og kun hvis den mindst fælles forfader af de tilsvarende blade er mærket 1. Omvendt kan enhver kograf repræsenteres af en indkoder på denne måde. Hvis vi kræver, at alle etiketter på alle stier fra roden til bladene veksler, vil en sådan repræsentation være unik [7] .

Beregningsmæssige egenskaber

En kograf kan genkendes i lineær tid, og en coderee-repræsentation kan konstrueres ved hjælp af modulær dekomponering [10] , dekomponeringsforfining [11] eller split-dekomponering [12] . Når koderen er bygget, kan mange velkendte grafteoretiske problemer løses ved at krydse koderen fra bunden og op.

For at finde den maksimale klik i en kograf, beregner vi, fra bund til top, den maksimale klik i hver undergraf repræsenteret af et undertræ af indkoderen. For hvert knudepunkt mærket 0 er den maksimale klik den maksimale klik, der modtages fra knudepunktets efterkommere. For et toppunkt mærket 1 vil den maksimale klik være foreningen af klikerne beregnet for toppunktets efterkommere, og størrelsen af denne klike er summen af klikstørrelserne. Ved skiftevis at tage den maksimale størrelse og summere værdierne for hvert hjørne af indkoderen, vil vi således beregne den maksimale klikstørrelse, og ved skiftevis at vælge den maksimale klike og sammenkæde, vil vi konstruere selve den maksimale klike. En lignende bottom-up tilgang gør det muligt at opnå det maksimale uafhængige sæt , kromatisk tal , maksimal klikdækning og eksistensen af en Hamiltonsk sti i lineær tid. Man kan også bruge cotrees til at bestemme i lineær tid, om to cographs er isomorfe .

Hvis H er en genereret undergraf af en kograf G , så er H selv en kograf. En koder til H kan fås ved at fjerne nogle af bladene fra koderen til G og derefter slå de hjørner sammen, der har et enkelt barn. Det følger af Kruskals træsætning , at den relation, der skal genereres af en subgraf, er en god kvasi-orden på kografer [13] . Så hvis en familie af kografer (såsom plane kografer) er lukket under driften af at konstruere en genereret subgraf, så har den et begrænset antal forbudte genererede subgrafer . Fra et beregningsmæssigt synspunkt betyder det, at kontrol af, om en graf tilhører en sådan familie, kan ske i lineær tid ved hjælp af en bottom-up-gennemgang af den givne grafs encoder.

Noter

↑ 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