Graf zděděný vzdáleností

V teorii grafů je graf zděděný vzdáleností (nebo zcela oddělitelný graf ) [1] graf, ve kterém jsou vzdálenosti v jakémkoli připojeném generovaném podgrafu stejné jako v původním grafu. Každý vygenerovaný podgraf tedy zdědí vzdálenosti většího grafu.

Grafy zděděné vzdáleností pojmenoval a poprvé studoval Howorka [2] , ačkoli pro ekvivalentní třídu grafů již v roce 1970 Olaru a Sachs ukázali, že třída obsahuje dokonalé grafy [3] .

Již nějakou dobu je známo, že grafy zděděné vzdáleností tvoří třídu grafů průniků [4] , ale model průniku nebyl znám, dokud jej nepodali Gioan a Paul ( Gioan, Paul 2012 ).

Definice a popis

Původní definice vzdálenostně zděděného grafu je graf G takový , že pokud libovolné dva vrcholy u a v patří do spojeného generovaného podgrafu H z G , pak nějaká nejkratší cesta spojující u a v v G musí být v podgrafu H , takže vzdálenost mezi u a v v H bude stejná jako v G .

Grafy zděděné vzdáleností lze popsat několika dalšími ekvivalentními způsoby: [5]

Vztah k jiným skupinám grafů

Dokonalý je jakýkoli graf zděděný vzdáleností [2] , přesněji zcela uspořádaný graf [8] . Jakýkoli graf zděděný vzdáleností je také sudý graf , tedy graf, ve kterém jsou libovolné dvě cesty mezi stejnou dvojicí vrcholů současně buď sudé nebo liché délky [9] . Libovolný sudý stupeň vzdálenostně zděděného grafu G (tj. grafu G 2 i vytvořeného spojením dvojic vrcholů ve vzdálenosti nepřesahující 2 i v G ) je akordický graf [10] .

Jakýkoli graf zděděný vzdáleností může být reprezentován jako graf průsečíků tětiv v kruhu, tedy jako kruhový graf . To lze ukázat vytvořením grafu přidáním visících vrcholů, „dvojčat“ a „dvojčat“, čímž se v každém kroku vytvoří soubor akordů reprezentujících graf. Přidání visícího vrcholu odpovídá přidání akordu blízko konce existujícího akordu, takže nový akord bude protínat pouze tento akord. Přidání „dvojčete“ odpovídá nahrazení akordu dvěma rovnoběžnými akordy protínajícími stejnou sadu akordů. Přidání „dvojčete“ odpovídá nahrazení akordu dvěma téměř rovnoběžnými protínajícími se akordy, které protínají stejnou sadu jiných akordů.

Graf zděděný vzdáleností je bipartitní právě tehdy, když nemá žádné trojúhelníky . Bipartitní graf zděděný vzdáleností lze sestavit z jednoho vrcholu přidáním pouze visících vertexů a dvojčat, protože každé dvojče tvoří trojúhelník a přidáním visícího vertexu a dvojčat se zachová bipartitnost.

Grafy, které lze sestavit z jednoho vrcholu přidáním visících vrcholů a vytvořením „dvojčat“ bez vytváření „dvojčat“, jsou speciální případy Ptolemaiových grafů a zahrnují blokové grafy . Grafy, které lze vytvořit z jednoho vrcholu vytvořením dvojčat a dvojčat, ale bez přidání visících vrcholů, jsou kografy , které se tedy dědí podle vzdálenosti. Cographs jsou přesně disjunktní spojení vzdáleností zděděných grafů s průměrem 2. Okolí libovolného vrcholu dálkově zděděného grafu je cograph. Tranzitivní uzavření orientovaného grafu vytvořeného výběrem libovolné sady hran libovolného stromu je zděděno vzdáleností. Speciální případ, kdy je strom orientován pryč od některého vrcholu, tvoří podtřídu vzdálenostně zděděných grafů známých jako triviálně dokonalé grafy , které se také nazývají akordické kografy [11] .

Algoritmy

Grafy zděděné vzdáleností lze rozpoznat a rozložit na posloupnost visících vrcholů a operací zdvojení v lineárním čase [12] .

Vzhledem k tomu, že grafy zděděné vzdáleností jsou dokonalé, lze některé optimalizační problémy vyřešit v polynomiálním čase, ačkoli tyto problémy jsou NP-obtížné pro obecnější třídy grafů. Je tedy možné v polynomiálním čase najít maximální kliku nebo nezávislou množinu v grafu zděděném vzdáleností nebo najít její optimální zabarvení [13] . Protože grafy zděděné vzdáleností jsou kruhové grafy, zdědí polynomiální-časové algoritmy pro kruhové grafy. Například lze určit v polynomiálním čase šířku stromu libovolného kruhového grafu, a tedy libovolného grafu zděděného vzdáleností [14] [15] . Navíc šířka kliky žádného grafu zděděného vzdáleností nepřesahuje tři [16] . V důsledku toho, podle Courcelleovy věty , pro mnoho problémů na těchto grafech existují účinné algoritmy založené na dynamickém programování [17] [18] .

Některé další optimalizační problémy na grafech zděděných vzdáleností lze efektivně vyřešit pomocí algoritmů speciálně navržených pro takové grafy. Jak ukázali de Atri a Moscarini [19] , minimální souvislou dominující množinu (nebo ekvivalentně kostru s maximálním možným počtem listů) lze nalézt v polynomiálním čase na grafech zděděných vzdáleností. Hamiltonovský graf nebo hamiltonovská cesta jakéhokoli grafu zděděného vzdáleností lze nalézt v polynomiálním čase [20] [21] .

Poznámky

  1. ↑ Hammer, Maffray, 1990 .
  2. ↑ 12 Howorka , 1977 .
  3. ↑ Olaru a Sachs ukázali α-dokonalost grafů, ve kterých má každý cyklus délky pět nebo více dvojici protínajících se diagonál ( Sachs, 1970 , Věta 5). Podle Lovásze ( Lovász 1972 ) je α-dokonalost ekvivalentní formou definice dokonalých grafů.
  4. ↑ McKee, McMorris, 1999 .
  5. ↑ Howorka (1977 ); Bandelt, Mulder (1986 ); Hammer, Maffray (1990 ); Brandstädt, Le, Spinrad (1999 ), Věta 10.1.1, str. 147.
  6. ↑ Gioan, Paul (2012 ). Úzce související dekompozice se používá pro vizualizaci grafů od Epsteina, Goodricha a Menga ( Eppstein, Goodrich, Meng (2006 )) a (pro bipartitní grafy zděděné vzdáleností) od Hui , Schaefera, Štefankoviče (2004 )).
  7. ↑ Oum, 2005 .
  8. ↑ Brandstädt, Le, Spinrad, 1999 , str. 70–71, 82.
  9. ↑ Brandstädt, Le, Spinrad, 1999 , str. 45.
  10. ↑ Brandstädt, Le, Spinrad, 1999 , str. 164 Věta 10.6.14.
  11. ↑ Cornelsen, Di Stefano, 2005 .
  12. ↑ Damiand, Habib, Paul (2001 ); Gioan, Paul (2012 ). Předtím tuto hranici stanovili Hammer a Maffray (1990 ), ale Damiand objevil chybu v uvažování.
  13. ↑ Cogis a Thierry Cogis, Thierry (2005 ) představili jednoduchý přímý algoritmus pro nalezení maximálních vážených nezávislých množin v grafech zděděných vzdáleností založený na rozkladu grafu na visící vrcholy a dvojité vrcholy, opravující dřívější pokus o takový algoritmus od Hammera a Maffraye ( Hammer, Maffray). (1990 )). Vzhledem k tomu, že grafy zděděné vzdáleností jsou dobře uspořádané, lze je optimálně vybarvovat v lineárním čase pomocí algoritmu dokonalého řazení LexBFS a použití zištného zbarvení .
  14. ↑ Kloks, 1996 .
  15. ↑ Brandstädt, Le, Spinrad, 1999 , str. 170.
  16. ↑ Golumbic, Rotics, 2000 .
  17. ↑ Courcelle, Makowski, Rotics, 2000 .
  18. ↑ Espelage, Gurski, Wanke, 2001 .
  19. ↑ D'Atri, Moscarini, 1988 .
  20. ↑ Hsieh, Ho, Hsu, Ko, 2002 .
  21. ↑ Müller, Nicolai, 1993 .

Literatura

Odkazy