Striktně akordický graf

Neorientovaný graf G se nazývá přísně tětivový , pokud je tětivový a každý cyklus sudé délky ( ) v G má lichý tětivec , tedy hranu, která spojuje dva vrcholy cyklu v liché vzdálenosti (>1) od sebe. [1] .

Popis

Striktně tětivové grafy jsou zakázanými grafy popsány jako grafy, které neobsahují vygenerovaný cyklus o více než třech délkách nebo n -sun ( ) jako generovaný podgraf [2] [3] [4] . n -Slunce je tětivový graf s 2n vrcholy rozdělenými do dvou podmnožin a takový, že každý vrchol w i z W má právě dva sousedy, u i a . n -Slunce nemůže být přísně akordické, protože cyklus ... nemá žádné liché akordy.

Striktně akordické grafy lze popsat jako grafy s přísným pořadím dokonalé eliminace, pořadí vrcholů takové, že sousedé jakéhokoli vrcholu, který přijde později v pořadí, tvoří kliku , a takové, že pro jakýkoli , pokud je i -tý vrchol v pořadí sousedí s k -tým a l -tým vrcholem a j -tý a k - tý vrchol sousedí, pak musí sousedit oba j - tý i l - tý vrchol [3] [5] .

Graf je přísně tětivový právě tehdy, když kterýkoli z jeho generovaných podgrafů má jednoduchý vrchol, tedy vrchol, jehož sousedé jsou lineárně uspořádáni podle pořadí inkluze [3] [6] . Také graf je přísně akordický právě tehdy, když je akordický a každý cyklus o délce pět a více má 2-akordický trojúhelník, tedy trojúhelník tvořený dvěma akordy a hranou cyklu [7] .

Graf je striktně akordický právě tehdy a jen tehdy, když některý z jeho vygenerovaných podgrafů je duálním akordickým grafem [8] .

Striktně tětivové grafy lze popsat počtem úplných podgrafů , ke kterým hrana náleží [9] . Další popis je uveden v článku De Caria a McKee [10] .

Rozpoznávání

Opakovaným vyhledáváním a odstraňováním jednoduchého vrcholu je možné určit, zda je graf v polynomiálním čase striktně akordický. Pokud tento proces eliminuje všechny vrcholy grafu, pak musí být graf přísně tětivový. Jinak proces nenajde podgraf bez jednoduchého vrcholu a v tomto případě nemůže být původní graf striktně akordický. Pro striktně akordický graf se pořadí, ve kterém jsou v tomto procesu odstraňovány vrcholy, nazýváno striktní řád dokonalé eliminace [3] .

Jsou známy alternativní algoritmy, které dokážou určit, zda je graf striktně akordický, a pokud ano, sestrojí striktně dokonalý eliminační řád efektivněji v čase pro graf s n vrcholy a m hranami [11] [12] [13] .

Podtřídy

Důležitou podtřídou (založenou na fylogenezi ) je třída k - listových stupňů , tedy grafy vytvořené z listů stromu spojením dvou listů hranou, pokud vzdálenost ve stromu nepřesahuje k . Listový stupeň je graf, který je k -listovým stupněm pro nějaké k . Protože stupně přísně tětivových grafů jsou přísně tětivové a stromy jsou přísně tětivové, vyplývá z toho, že stupně listů jsou přísně tětivové. Tvoří svou vlastní podtřídu silně tětivových grafů, která zase zahrnuje shlukové grafy jako 2-listové mocniny [14] . Další důležitou podtřídou striktně akordických grafů jsou intervalové grafy . Branstedt, Hudt, Mancini a Wagner [15] ukázali, že intervalové grafy a větší třída směrovaných kořenových drah jsou mocniny listů.

Algoritmické problémy

Protože silně akordické grafy jsou akordické i duálně akordické , lze pro silně akordické grafy efektivně vyřešit různé NP-úplné problémy, jako je problém nezávislé množiny , problém kliky , zbarvení , problém krytu kliky , dominující množina a problém minimálního stromu Steiner . Problém izomorfismu grafu je GI-úplný [16] pro striktně akordické grafy [17] . Hledání hamiltonovských cyklů zůstává NP-úplným problémem pro striktně chordální rozdělené grafy [18] .

Poznámky

  1. ↑ Brandstädt, Le, Spinrad, 1999 , str. 43, definice 3.4.1.
  2. ↑ Chang, 1982 .
  3. ↑ 1 2 3 4 Farber, 1983 .
  4. ↑ Brandstädt, Le, Spinrad, 1999 , str. 112, Věta 7.2.1.
  5. ↑ Brandstädt, Le, Spinrad, 1999 , str. 77, Věta 5.5.1.
  6. ↑ Brandstädt, Le, Spinrad, 1999 , str. 78, Věta 5.5.2.
  7. ↑ Dahlhaus, Manuel, Miller, 1998 .
  8. ↑ Brandstädt, Dragan, Chepoi, Voloshin, 1998 , str. 444, důsledek 3.
  9. ↑ McKee, 1999 .
  10. ↑ De Caria, McKee, 2014 .
  11. ↑ Lubiw, 1987 .
  12. ↑ Paige, Tarjan, 1987 .
  13. ↑ Spinrad, 1993 .
  14. ↑ Nishimura, Ragde, Thilikos, 2002 .
  15. ↑ Brandstädt, Hundt, Mancini, Wagner, 2010 .
  16. ↑ Článek představuje novou třídu úplnosti - Graph Isomorphism úplnost
  17. ↑ Uehara, Toda, Nagoja, 2005 .
  18. ↑ Müller, 1996 .

Literatura