Cograph

En graf er, i grafteorien , en graf som kan genereres ved komplementering og usammenhengende forening fra grafen i en node.

De fleste algoritmiske problemer kan løses på denne klassen i polynomisk tid, og til og med lineær, på grunn av dens strukturelle egenskaper.

Definisjoner og karakteriseringer

Denne familien av grafer ble introdusert av flere forfattere uavhengig på 1970-tallet under forskjellige navn, inkludert D * -grafer, arvelige Dacey-grafer og 2-paritetsgrafer .

Definisjon

En graf er en enkel graf som kan bygges rekursivt i henhold til følgende regler:

grafen i toppunktet er en graf,
komplementet til en graf er en graf,
foreningen av to graver er en graf.

Definisjon ved hjelp av sammenføyningsoperasjonen

"Bli med" av to usammenhengende grafer, og er operasjonen som består i å lage en ny graf , hvor og . Denne operasjonen er faktisk komplementet til foreningen av de komplementære. $G_ {1} = (V_ {1}, E_ {1})$ $G_ {2} = (V_ {2}, E_ {2})$ $G = (V, E)$ $V = V_ {1} \ kopp V_ {2}$ $E = E_ {1} \ cup E_ {2} \ cup \ {(i, j) | i \ in V_ {1}, j \ in V_ {2} \}$

En graf er da en graf som kan dannes ut fra grafene i toppunktet, ved "join" og ved union.

Karakteriseringer

Det er mange karakteriseringer av graver, inkludert:

grafene er de -frie grafene , det vil si de som ikke har banen på fire hjørner som indusert undergraf ; $P_ {4}$
grafer er grafer der alle de ikke-trivielle induserte undergrafene har to hjørner som har samme nabolag .
grafer er grafer over inversjoner av skillbare permutasjoner .

Grove

En kull beskriver en graf, takket være operasjonene som er nødvendige for å bygge dem.

Bladene representerer noder i grafen, og de interne nodene representerer operasjoner. Nodene merket med 0 representerer foreningen av grafene representert av undertrærne og de merket med 1 representerer "sammenføyningen" av disse tegningene. Det er en kant mellom to noder på treet hvis og bare hvis den minste felles forfedren til disse noder er merket med 1.

Denne representasjonen er unik. Det er en kompakt måte å representere graver på.

Videre, ved å utveksle 1s og 0s, får vi co-treet til den komplementære grafen .

Matematiske egenskaper og inneslutninger

Cograffamilien er stabil av induserte underbilder;
Grafer er perfekte grafer .
De grafene Turan er cographs.
grafer er grafer over permutasjons- og sammenlignbarhetsgrafer .

Algoritmiske egenskaper

Grafer kan gjenkjennes på lineær tid. De fleste klassiske problemer kan løses i lineær tid på denne klassen, for eksempel problemene knyttet til klikker og Hamilton-sykluser . Den maksimale kutt problemet er polynom på denne klassen.

I en sammenheng med synkron distribuert beregning gjør karakteriseringen med 4-sti ekskludert det mulig å gjenkjenne grafene i et konstant antall svinger.

Merknader og referanser

se spesielt ( Jung 1978 ), ( Sumner 1974 ) og ( Burlet og Uhry 1984 )
Se ( Corneil, Lerchs og Burlingham 1981 ) og ( Seinsche 1974 ).
Dette følger direkte av P4-fri karakterisering.
( Corneil, Perl og Stewart 1985 )
Se relatert side om informasjonssystem om grafklasser og deres inkluderinger
Se ( Bodlaender og Jansen 2000 )
( Fraigniaud, Halldorsson og Korman 2012 )

Bibliografi

HA Jung , “ On a class of posets and the corresponding comparability charts ”, Journal of Combinatorial Theory, Series B , vol. 24 n o to1978, s. 125–133 ( DOI 10.1016 / 0095-8956 (78) 90013-8 ).

DP Sumner , " Dacey-grafer ", J. Austral. Matte. Soc. , vol. 18, n o 4,1974, s. 492–502 ( DOI 10.1017 / S1446788700029232 ).

M. Burlet og JP Uhry , “ Topics on Perfect Graphs (Parity Graphs) ”, Annals of Discrete Mathematics , vol. 21,1984, s. 253–277.

DG Corneil , H. Lerchs og L. Stewart Burlingham , “ Complement reducible graphs ”, Discrete Applied Mathematics , vol. 3, n o 3,nitten åtti en, s. 163–174 ( DOI 10.1016 / 0166-218X (81) 90013-5 ).

DG Corneil , Y. Perl og LK Stewart , “ En lineær gjenkjenningsalgoritme for cographs ”, SIAM Journal on Computing , vol. 14, n o 4,1985, s. 926–934 ( DOI 10.1137 / 0214065 , matematiske anmeldelser 0807891 ).

Hans L. Bodlaender og Klaus Jansen , “ On the Complexity of the Maximum Cut Problem ”, Nord. J. Comput. , vol. 7, n o 1,2000, s. 14-31.

D. Seinsche , " On a property of the class of n -colorable charts ", Journal of Combinatorial Theory, Series B , vol. 16, n o to1974, s. 191-193 ( DOI 10.1016 / 0095-8956 (74) 90063-X , matematiske anmeldelser 0337679 ).

Pierre Fraigniaud , Magnus M Halldorsson og Amos Korman , "Om virkningen av identifikatorer på lokal beslutning" , i Principles of Distributed Systems ,2012, s. 224 -238