V teorii grafů se graf nazývá tětivový , pokud každý z jeho cyklů , které mají čtyři nebo více hran, má tětivu (hranu, která spojuje dva vrcholy cyklu, ale není jeho součástí).
Ekvivalentní definicí je, pokud má jakýkoli cyklus bez tětiv nejvýše tři hrany. Jinými slovy, chordální graf je graf bez generovaných cyklů delších než tři.
Chordální grafy jsou podmnožinou dokonalých grafů . Někdy se jim také říká cyklicky rigidní grafy [1] nebo triangulované grafy . (Poslední termín je někdy chybně používán pro rovinnou triangulaci. Viz maximální rovinné grafy .) [2]
Dokonalé pořadí vyloučení v grafu je pořadí vrcholů grafu takové, že pro každý vrchol v , v a sousedy v , kteří jsou po v v pořadí , tvoří kliku . Graf je chordální právě tehdy, když má dokonalé pořadí vyloučení [3]
Rose, Lucker a Tarjan (1976) [4] (viz také Habib, McConnell, Paul, Vienneno (2000) [5] ) ukázali, že dokonalé eliminační pořadí akordického grafu lze efektivně nalézt pomocí algoritmu známého jako lexikografická šířka- první hledání . Tento algoritmus rozdělí vrcholy grafu do posloupnosti množin. Zpočátku se sekvence skládá z jediné sady obsahující všechny vrcholy. Algoritmus ve smyčce vybere vrchol v z nejstarší množiny v posloupnosti obsahující vrcholy, které ještě nebyly vybrány, a rozdělí každou množinu S posloupnosti na dvě menší - jedna se skládá ze sousedů vrcholu v v S , druhá zahrnuje všechny zbývající vrcholy. Když se proces dělení provádí pro všechny vrcholy, všechny sady posloupnosti obsahují každý jeden vrchol a tvoří posloupnost inverzní k dokonalému pořadí eliminace.
Vzhledem k tomu, že jak lexikografické prohledávání šířky, tak i kontrola, zda je řád dokonalou výjimkou, lze provádět v lineárním čase, je možné rozpoznat akordický graf v lineárním čase. Sendvičový problém na akordickém grafu je NP-úplný [6] , zatímco problém testovacího grafu na akordickém grafu má polynomiálně-časovou složitost [7] .
Množinu všech řádů dokonalého vyloučení akordického grafu lze považovat za základní slova antimatroidu . Chandran et al ., [8] použili toto spojení s antimatroidy jako součást algoritmu pro efektivní výčet všech dokonalých vylučovacích řádů pro daný akordický graf.
Další aplikací pro dokonalé eliminační pořadí je nalezení maximální kliky akordického grafu v polynomiálním čase, zatímco pro obecné grafy je stejný problém NP-úplný (akordický graf může mít pouze lineárně mnoho největších kliků , zatímco grafy nekordálních grafů mohou mít exponenciálně mnoho z nich). Abychom získali seznam všech největších klik akordického grafu, stačí najít dokonalé eliminační pořadí, sestrojit kliku pro každý vrchol v ze všech sousedních vrcholů v pořadí po v a zkontrolovat, zda výsledná klika je největší.
Největší klika, která má maximální velikost, je maximální klika, a protože akordické grafy jsou dokonalé, je velikost této kliky rovna chromatickému číslu akordického grafu. Chordální grafy jsou dobře uspořádané - optimálního zbarvení lze získat pomocí algoritmu greedy colouring , kdy vrcholy v opačném pořadí k dokonalé eliminaci. [9]
V libovolném grafu je oddělovač vrcholů sada vrcholů, jejichž odstranění způsobí odpojení zbývajícího grafu. Oddělovač je minimální, pokud neobsahuje podmnožinu, která je zároveň oddělovačem. Podle Diracovy věty [1] jsou akordické grafy grafy, ve kterých je každý minimální oddělovač klikou. Dirac použil tuto vlastnost, aby dokázal, že akordické grafy jsou dokonalé .
Rodinu akordických grafů lze definovat jako množinu grafů, jejichž vrcholy lze rozdělit do tří neprázdných podmnožin A , S a B tak, že A ∪ S a S ∪ B oba tvoří akordicky generované podgrafy , S je klika, a nejsou zde žádné hrany spojující A a B. _ Jedná se tedy o grafy, které umožňují rekurzivní rozdělení na menší podgrafy pomocí klik. Z tohoto důvodu se akordické grafy někdy nazývají rozložitelné grafy . [deset]
Další charakteristikou akordických grafů [ 11] jsou stromy a jejich podstromy.
Ze sady podstromů stromu lze určit graf podstromu - graf průniku , jehož každý vrchol odpovídá podstromu a hrana spojuje dva podstromy, pokud mají jednu nebo více společných hran. Gavril ukázal, že podstromové grafy jsou přesně akordické grafy.
Reprezentace akordických grafů jako graf průsečíku podstromu vytváří rozklad grafu na stromy se šířkou stromu o jednu menší, než je velikost největší kliky grafu. Rozklad libovolného grafu G na stromy lze považovat za zobrazení grafu G jako podgrafu tětivového grafu. Rozložení grafu na stromy je také sjednocovacím stromem v algoritmu šíření důvěry .
Intervalové grafy jsou grafy průniku podstromu , speciální případ stromů. Intervalové grafy jsou tedy podrodinou akordických grafů.
Rozdělené grafy jsou samy o sobě akordické a jsou doplňky akordických grafů. Bender, Richmond a Wormald (1985) [12] ukázali, že jak n směřuje k nekonečnu, zlomek akordických grafů s n vrcholy, které jsou rozděleny, má tendenci k jedné.
Ptolemaiovy grafy jsou grafy, které jsou jak chordální, tak zděděné podle vzdálenosti . Kvaziprahové grafy jsou podtřídou Ptolemaiových grafů, které jsou jak chordální, tak cograph . Blokové grafy jsou další podtřídou Ptolemaiových grafů, ve kterých jakékoli dvě největší kliky mají nejvýše jeden společný vrchol. Speciálním případem jsou mlýny , které mají stejný vrchol pro libovolnou dvojici klik.
Striktně tětivové grafy jsou grafy, které jsou tětivové a neobsahují n-slunce ( n ≥ 3) jako generované podgrafy.
K-stromy jsou chordální grafy, jejichž největší kliky a největší oddělovače klik mají všechny stejnou velikost. [13] Apolloniovy grafy jsou chordální maximální rovinné grafy nebo ekvivalentně rovinné 3-stromy. [13] Maximální vnější rovinné grafy jsou podtřídou 2-stromů a tedy také tětivové.
Chordální grafy jsou podtřídou známých dokonalých grafů . Mezi další supertřídy akordických grafů patří slabé akordické grafy, grafy bez lichých děr a grafy bez sudých děr . Ve skutečnosti jsou akordické grafy přesně grafy, a to jak bez sudých děr, tak bez lichých děr (viz díra v teorii grafů).
Jakýkoli graf tětivy je kontrahován , tj. graf, ve kterém je jakýkoli periferní cyklus trojúhelníkem, protože periferní cykly jsou speciálním případem generovaného cyklu. Stažené grafy mohou být tvořeny klikovými součty akordických grafů a maximálních akordických grafů. Takto stažené grafy zahrnují maximální rovinné grafy . [čtrnáct]