Cograf

V teorii grafů je cograph , nebo dodatečně redukovatelný graf , nebo graf bez P 4 ,  graf , který lze získat z grafu s jediným vrcholem K 1 operacemi sčítání a sjednocení grafu . Rodina kografů je tedy nejmenší třída grafů, která obsahuje K 1 a je uzavřena pod doplňkem a sjednocením.

Kografy byly objeveny nezávisle na sobě několika autory od 70. let 20. století. Nejstarší zmínky najdeme u Younga [1] , Lerchse [2] , Zainscheho [3] a Sumnera [4] . Tyto grafy se nazývaly D*-grafy [1] , dědičné Daceyho grafy (podle práce Jamese C. Daceyho, Jr. o ortomodulárních mřížkách . Viz Sumner [4] ) a grafy se dvěma potomky Barleta a Uryho [ 5] .

Podrobnější pojednání o kografech, včetně zde uvedených faktů, naleznete v knize Brandstedta, Lie a Spinrada [6] .

Definice a popis

Jakýkoli kograf lze sestavit podle následujících pravidel:

  1. Každý jednotlivý vrchol grafu je cograph;
  2. Jestliže  je cograph, pak jeho doplněk je také cograph;
  3. Jestliže a  jsou kografy, pak jejich disjunktní spojení je také kografem.

Lze uvést několik dalších popisů kografů. Mezi nimi:

Všechny kompletní grafy , kompletní bipartitní grafy , prahové grafy a Turanovy grafy jsou kografy. Jakýkoli kograf je graf dokonalé srovnatelnosti zděděný vzdáleností .

Codetrees

Kódový  strom je strom, jehož vnitřní vrcholy jsou označeny 0 a 1. Jakýkoli kódový strom T definuje cograph G , který má listy T jako vrcholy, a podstrom s kořenem v T odpovídá vygenerovanému podgrafu v G definovaném sadou následných listů . tento top:

Ekvivalentní způsob, jak sestrojit kograf z kodéru, je ten, že dva vrcholy jsou spojeny hranou právě tehdy, když je nejmenší společný předek odpovídajících listů označen 1. Naopak, tímto způsobem může být kodérem reprezentován jakýkoli kograf. Pokud požadujeme, aby se všechny popisky na všech cestách od kořene po listy střídaly, bude takové znázornění jedinečné [7] .

Výpočtové vlastnosti

Kograf může být rozpoznán v lineárním čase a reprezentace coderee může být konstruována pomocí modulární dekompozice [10] , zpřesnění dekompozice [11] nebo děleného rozkladu [12] . Jakmile je kodér sestaven, mnoho známých problémů teorie grafů lze vyřešit procházením kodéru zdola nahoru.

Abychom například našli maximální kliku v cographu, vypočítáme zdola nahoru maximální kliku v každém podgrafu reprezentovaném podstromem kodéru. Pro každý vrchol označený 0 je maximální klika maximální klika přijatá od potomků vrcholu. Pro vrchol označený 1 bude maximální klika sjednocením klik vypočítaných pro potomky vertexu a velikost této kliky je součtem velikostí klik. Střídavým odebíráním maximální velikosti a sečtením hodnot pro každý vrchol kodéru tedy vypočítáme maximální velikost kliky a střídavým výběrem maximální kliky a zřetězením zkonstruujeme samotnou maximální kliku. Podobný přístup zdola nahoru umožňuje získat maximální nezávislou množinu , chromatické číslo , maximální pokrytí klikou a existenci hamiltonovské cesty v lineárním čase. Jeden může také používat cotrees k určení v lineárním čase zda dva cographs jsou izomorfní .

Jestliže H  je vygenerovaný podgraf kografu G , pak H sám je kografem. Kodér pro H lze získat odstraněním některých listů z kodéru pro G a poté sloučením vrcholů, které mají jednoho potomka. Z Kruskalovy věty o stromě vyplývá, že vztah, který má být generován podgrafem, je dobrý kvazi-řád na kografech [13] . Pokud je tedy rodina kografů (jako jsou planární kografy) uzavřena operací konstrukce generovaného podgrafu, pak má konečný počet zakázaných generovaných podgrafů . Z výpočtového hlediska to znamená, že kontrolu, zda graf patří do takové rodiny, lze provádět v lineárním čase pomocí procházení zdola nahoru kodérem daného grafu.

Poznámky

  1. ↑ 1 2 3 Jung, 1978 .
  2. ↑ Lerchs, 1971 .
  3. ↑ Seinsche, 1974 .
  4. ↑ 12. Sumner , 1974 .
  5. ↑ Burlet, Uhry, 1984 .
  6. ↑ Brandstädt, Le, Spinrad, 1999 .
  7. ↑ 1 2 Corneil, Lerchs, Burlingham, 1981 .
  8. ↑ Courcelle, Olariu, 2000 .
  9. ↑ Bose, Buss, Lubiw, 1998 .
  10. ↑ Corneil, Perl, Stewart, 1985 .
  11. ↑ Habib, Paul, 2005 .
  12. ↑ Gioan, Paul, 2008 .
  13. ↑ Damaschke, 1990 .

Literatura

Odkazy