Cograph

Kograf jest w teorii wykres , na wykresie, które mogą być generowane przez komplementację , a suma rozłączna z wykresu na jednym węźle.

Większość problemów algorytmicznych na tej klasie można rozwiązać w czasie wielomianowym, a nawet liniowym, ze względu na jej właściwości strukturalne.

Definicje i charakterystyka

Ta rodzina grafów została wprowadzona przez kilku autorów niezależnie w latach 70. XX wieku pod różnymi nazwami, w tym grafami D *, grafami dziedzicznymi Daceya i grafami 2-parzystości .

Definicja

Cograph to prosty wykres, który można zbudować rekurencyjnie zgodnie z następującymi zasadami:

• graf na wierzchołku to cograph,
• dopełnieniem kodu jest kod,
• związek dwóch znaczników jest kodem.

Definicja za pomocą operacji łączenia

„Łączenie” dwóch rozłącznych wykresów i , jest operacją polegającą na utworzeniu nowego wykresu , gdzie i . Ta operacja jest w istocie dopełnieniem połączenia komplementarnych. sol1=(V1,mi1){\ Displaystyle G_ {1} = (V_ {1}, E_ {1})}sol2=(V2,mi2){\ Displaystyle G_ {2} = (V_ {2}, E_ {2})}sol=(V,mi){\ Displaystyle G = (V, E)}V=V1∪V2{\ Displaystyle V = V_ {1} \ kubek V_ {2}}mi=mi1∪mi2∪{(ja,jot)|ja∈V1,jot∈V2}{\ Displaystyle E = E_ {1} \ Puchar E_ {2} \ Puchar \ {(i, j) | ja \ w V_ {1}, j \ w V_ {2} \}}

Cograph jest wówczas grafem, który można utworzyć z wykresów na wierzchołku, przez „łączenie” i sumowanie.

Charakteryzacje

Istnieje wiele charakterystyk kografów, w tym:

• wykresy są grafami wolnymi , to znaczy takimi, które nie mają ścieżki na czterech wierzchołkach jako indukowanego podgrafu ;P.4{\ displaystyle P_ {4}}
• Cographs to grafy, dla których wszystkie nietrywialne indukowane podgrafy mają dwa wierzchołki mające to samo sąsiedztwo .
• cographs są wykresami inwersji w oddzielnych permutacji .

Coarbre

Coarbre opisuje kograf dzięki operacjom, które są niezbędne do ich zbudowania.

Liście reprezentują węzły cograph, a węzły wewnętrzne reprezentują operacje. Węzły oznaczone „0” reprezentują sumę znaczników reprezentowanych przez poddrzewa, a te oznaczone „1” reprezentują „połączenie” tych znaczników. Istnieje krawędź między dwoma węzłami drzewa wtedy i tylko wtedy, gdy najmniejszy wspólny przodek tych węzłów jest oznaczony jako 1.

Ta reprezentacja jest wyjątkowa. To zwarty sposób przedstawiania kodów.

Ponadto, zamieniając jedynki i zera, otrzymujemy wspólne drzewo grafu komplementarnego .

Właściwości matematyczne i inkluzje

• Rodzina cograph jest stabilna dzięki indukowanym podgrafom;
• Cographs to doskonałe wykresy .
• Te wykresy Turan są cographs.
• cographs to wykresy permutacji i wykresów porównywalności .

Właściwości algorytmiczne

Cographs można rozpoznać w czasie liniowym. Większość klasycznych problemów można rozwiązać w czasie liniowym na tej klasie, na przykład problemy związane z klikami i cyklami Hamiltona . Problem z maksymalnym cięciem jest wielomianowy w tej klasie.

W kontekście synchronicznych obliczeń rozproszonych charakterystyka z wyłączeniem 4 ścieżek umożliwia rozpoznanie cographs w stałej liczbie zwojów.

Uwagi i odniesienia

1. patrz w szczególności ( Jung 1978 ), ( Sumner 1974 ) i ( Burlet i Uhry 1984 )
2. Patrz ( Corneil, Lerchs i Burlingham 1981 ) i ( Seinsche 1974 ).
3. Wynika to bezpośrednio z charakterystyki wolnej od P4.
4. ( Corneil, Perl i Stewart 1985 )
5. Zobacz powiązaną stronę o systemie informacyjnym o klasach grafów i ich włączeniach
6. Patrz ( Bodlaender i Jansen 2000 )
7. ( Fraigniaud, Halldorsson i Korman 2012 )

Bibliografia

• HA Jung , „  O klasie posetów i odpowiednich wykresach porównywalności  ”, Journal of Combinatorial Theory, Series B , vol.  24 N O  21978, s.  125–133 ( DOI  10.1016 / 0095-8956 (78) 90013-8 ).

• DP Sumner , „  Dacey graphs  ”, J. Austral. Matematyka. Soc. , vol.  18 N O  4,1974, s.  492–502 ( DOI  10.1017 / S1446788700029232 ).

• M. Burlet i JP Uhry , „  Tematy dotyczące wykresów doskonałych (wykresy parzystości)  ”, Annals of Discrete Mathematics , t.  21,1984, s.  253–277.

• DG Corneil , H. Lerchs i L. Stewart Burlingham , „  Complement reducible graphs  ”, Discrete Applied Mathematics , tom.  3 n o  3,Dziewiętnaście osiemdziesiąt jeden, s.  163-174 ( DOI  10.1016 / 0166-218X (81) 90013-5 ).

• DG Corneil , Y. Perl i LK Stewart , „  Liniowy algorytm rozpoznawania dla cographs  ”, SIAM Journal on Computing , tom.  14 N O  4,1985, s.  926–934 ( DOI  10.1137 / 0214065 , Recenzje matematyczne  0807891 ).

• Hans L. Bodlaender i Klaus Jansen , „  O złożoności problemu maksymalnego cięcia  ”, Nord. J. Comput. , vol.  7, N O  1,2000, s.  14-31.

• D. Seinsche , „  On a property of the class of n -colorable graphs  ”, Journal of Combinatorial Theory, Series B , vol.  16 N O  21974, s.  191-193 ( DOI  10.1016 / 0095-8956 (74) 90063-X , Recenzje matematyczne  0337679 ).

• Pierre Fraigniaud , Magnus M Halldorsson i Amos Korman , „On the impact of identifiers on local Decision ” , w Principles of Distributed Systems ,2012, s.  224 -238

Zobacz też

Linki zewnętrzne

• Rodzina cograph w systemie informacyjnym o klasach grafów i ich włączeniach
• (en) Eric W. Weisstein , „  Cograph  ” , na MathWorld