Cograph

A cograph van, a gráfelmélet , egy grafikon, amely által generált komplementációs és diszjunkt egyesítését a grafikonon egy csomópontot.

A legtöbb algoritmikus probléma ezen az osztályon megoldható polinomiális időben, sőt szerkezeti tulajdonságai miatt lineáris is.

Definíciók és jellemzések

Ezt a grafikoncsaládot számos szerző önállóan vezette be az 1970-es években különböző nevek alatt, beleértve D * -gráfokat, örökletes Dacey-grafikonokat és 2-paritású grafikonokat .

Meghatározás

A cograph egy egyszerű grafikon, amelyet rekurzívan lehet felépíteni a következő szabályok szerint:

a csúcson lévő grafikon egy kográf,
a cograph kiegészítője egy cograph,
két kográf egyesülése kográf.

Definíció az összekapcsolási művelettel

Két diszjunkt gráf "összekapcsolása", és a művelet egy új gráf létrehozásából áll , ahol és . Ez a művelet valójában a komplementer uniójának kiegészítője. $G_ {1} = (V_ {1}, E_ {1})$ $G_ {2} = (V_ {2}, E_ {2})$ $G = (V, E)$ $V = V_ {1} \ csésze V_ {2}$ $E = E_ {1} \ csésze E_ {2} \ csésze \ {(i, j) | i \ a V_-ben {1}, j \ a V_-ben {2} \}$

A kográf ekkor egy olyan gráf, amelyet a csúcsban lévő grafikonokból, "összekapcsolás" és egyesülés útján lehet kialakítani.

Jellemzések

A kográfok sokféle jellemzéssel rendelkeznek, többek között:

A cographs a -mentes grafikonok , vagyis azok, amelyek nem rendelkeznek a pálya négy csúcsot, mint egy indukált részgráf ; $P_ {4}$
A cographs olyan grafikonok, amelyekhez az összes nem triviális indukált részgráfnak két csúcsa van azonos szomszédsággal .
a cographs az elválasztható permutációk inverzióinak grafikonjai .

Coarbre

A széndarab leírja a kográfot, az építésükhöz szükséges műveleteknek köszönhetően.

A levelek a fényképész csomópontjait, a belső csomópontok pedig a műveleteket jelentik. A 0-val jelölt csomópontok az alfák által ábrázolt kográfok unióját, az 1-vel jelölt csomópontok pedig ezeknek a kográfoknak a "csatlakozását" jelentik. A fa két csomópontja között akkor és csak akkor van él, ha ezeknek a csomópontoknak a legkisebb közös ősét 1 jelöli.

Ez az ábrázolás egyedülálló. Kompakt módon ábrázolhatja a fényképeket.

Sőt, az 1-ek és a 0-k cseréjével megkapjuk a komplementer gráf társfáját .

Matematikai tulajdonságok és zárványok

A cograph család stabil az indukált részgráfokkal;
A térképek tökéletes grafikonok .
A Turán grafikonok krógrák.
A cographs a permutáció és az összehasonlíthatóság grafikonja .

Algoritmikus tulajdonságok

A fényképeket lineáris időben lehet felismerni. A legtöbb klasszikus probléma lineáris időben megoldható ezen az órán, például a klikkekkel és a Hamilton-ciklusokkal kapcsolatos problémák . A maximális vágási probléma ebben az osztályban polinom.

A szinkron elosztott számítások kontextusában a 4 útvonalon kívüli jellemzés kizárva lehetővé teszi a térképek állandó fordulatszámú felismerését.

Megjegyzések és hivatkozások

lásd különösen ( Jung 1978 ), ( Sumner 1974 ) és ( Burlet és Uhry 1984 )
Lásd ( Corneil, Lerchs és Burlingham 1981 ) és ( Seinsche 1974 ).
Ez közvetlenül a P4-mentes jellemzésből következik.
( Corneil, Perl és Stewart 1985 )
Lásd a kapcsolódó oldalt a Grafikon osztályok információs rendszeréről és azok beillesztéséről
Lásd ( Bodlaender és Jansen 2000 )
( Fraigniaud, Halldorsson és Korman 2012 )

Bibliográfia

HA Jung , „ A posztok osztályáról és a megfelelő összehasonlíthatósági grafikonokról ”, Journal of Combinatorial Theory, B sorozat , vol. 24, n o 21978, P. 125–133 ( DOI 10.1016 / 0095-8956 (78) 90013–8 ).

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

M. Burlet és JP Uhry , „ Témák a tökéletes grafikonokról ( paritásgrafikonok ) ”, Annals of Discrete Mathematics , vol. 21,1984, P. 253–277.

DG Corneil , H. Lerchs és L. Stewart Burlingham , „ Komplement redukálható grafikonok ”, Diszkrét alkalmazott matematika , vol. 3, n o 3,tizenkilenc nyolcvan egy, P. 163–174 ( DOI 10.1016 / 0166-218X (81) 90013–5 ).

DG Corneil , Y. Perl és LK Stewart , „ Lineáris felismerési algoritmus a fényképészekhez ”, SIAM Journal on Computing , vol. 14, n o 4,1985, P. 926–934 ( DOI 10.1137 / 0214065 , Math Reviews 0807891 ).

Hans L. Bodlaender és Klaus Jansen , „ A maximális vágási probléma összetettségéről ”, Nord. J. Comput. , vol. 7, n o 1,2000, P. 14-31.

D. Seinsche : „ Az n- színezhető grafikonok osztályának tulajdonságáról ”, Journal of Combinatorial Theory, B sorozat , vol. 16, n o 21974, P. 191-193 ( DOI 10.1016 / 0095-8956 (74) 90063-X , matematikai vélemények 0337679 ).

Pierre Fraigniaud , Magnus M Halldorsson és Amos Korman , „Az azonosítók helyi döntésre gyakorolt hatásáról” , Principles of Distributed Systems ,2012, P. 224-238