Wykres akordowy

Cykl (czarny) z dwoma akordami (zielony). Jeśli chodzi o tę część, wykres jest akordowy. Jednak usunięcie jednej zielonej krawędzi spowodowałoby powstanie wykresu bez akordów. Rzeczywiście, druga zielona krawędź z trzema czarnymi krawędziami utworzyłaby cykl o długości czterech bez akordów.

W matematycznym obszarze teorii grafów graf akordowy to taki, w którym wszystkie cykle o czterech lub więcej wierzchołkach mają akord , który jest krawędzią , która nie jest częścią cyklu, ale łączy dwa wierzchołki cyklu. Równoważnie, każdy indukowany cykl w grafie powinien mieć dokładnie trzy wierzchołki. Grafy akordowe można również scharakteryzować jako grafy, które mają doskonałe uporządkowania eliminacji, jako grafy, w których każdy minimalny separator jest kliką, oraz jako grafy przecięcia poddrzew drzewa. Czasami nazywane są również grafami obwodów sztywnych lub grafami triangulowanymi .

Wykresy akordowe są podzbiorem grafów doskonałych . Można je rozpoznać w czasie liniowym , a kilka problemów, które są trudne w przypadku innych klas grafów, takich jak kolorowanie wykresów, można rozwiązać w czasie wielomianowym, gdy wejście jest akordowe. Szerokość drzewa dowolnego wykresu można scharakteryzować na podstawie wielkości klik w grafach akordowych, które go zawierają.

Doskonała eliminacja i sprawne rozpoznawanie

Doskonałe $uporządkowanie$ eliminacyjne w grafie to uporządkowanie wierzchołków grafu w taki sposób, że dla każdego wierzchołka $v$ , $v$ i sąsiedzi v występujący po $v$ w kolejności tworzą klikę . Wykres jest akordowy wtedy i tylko wtedy, gdy ma doskonały porządek eliminacji.

Rose, Lueker i Tarjan (1976) (patrz także Habib i in. 2000 ) pokazują, że idealne uporządkowanie eliminacji grafu akordowego można skutecznie znaleźć za pomocą algorytmu znanego jako przeszukiwanie leksykograficzne wszerz . Algorytm ten utrzymuje podział wierzchołków grafu na sekwencję zbiorów; początkowo ta sekwencja składa się z jednego zestawu ze wszystkimi wierzchołkami. Algorytm wielokrotnie wybiera wierzchołek $v$ z najwcześniejszego zestawu w sekwencji, który zawiera poprzednio niewybrane wierzchołki, i dzieli każdy zestaw $S$ sekwencji na dwa mniejsze podzbiory, pierwszy składający się z sąsiadów $v$ w $S$ , a drugi składający się z nie -sąsiedzi. Kiedy ten proces podziału został przeprowadzony dla wszystkich wierzchołków, sekwencja zestawów ma jeden wierzchołek na zestaw, w odwrotności idealnej kolejności eliminacji.

Ponieważ zarówno ten leksykograficzny proces pierwszego przeszukiwania szerokości, jak i proces sprawdzania, czy uporządkowanie jest doskonałym uporządkowaniem eliminacji, można przeprowadzić w czasie liniowym , możliwe jest rozpoznawanie grafów akordowych w czasie liniowym. Problem kanapki grafowej na wykresach akordowych jest NP-zupełny , podczas gdy problem wykresu próbnego na grafach akordowych ma złożoność wielomianową.

Zbiór wszystkich doskonałych porządków eliminacji wykresu akordowego można modelować jako podstawowe słowa antymatroidu ; Chandrana i in. (2003) wykorzystują to połączenie z antymatroidami jako część algorytmu do efektywnego wymieniania wszystkich doskonałych porządków eliminacji danego grafu akordowego.

Maksymalne kliki i kolorowanie grafów

Innym zastosowaniem doskonałych porządków eliminacji jest znalezienie maksymalnej kliki wykresu akordowego w czasie wielomianowym, podczas gdy ten sam problem dla grafów ogólnych jest NP-zupełny . Mówiąc bardziej ogólnie, wykres akordowy może mieć tylko liniowo wiele maksymalnych klik , podczas gdy wykresy nieakordowe mogą mieć wiele wykładniczo. Aby wymienić wszystkie maksymalne kliki grafu akordowego, po prostu znajdź idealną kolejność eliminacji, utwórz klikę dla każdego wierzchołka $v$ razem z sąsiadami $v$ , którzy są późniejsi niż $v$ w doskonałej kolejności eliminacji, i sprawdź, czy każda z wynikowych klik jest maksymalny.

Wykresy klikowe grafów akordowych są grafami akordowymi dualnymi .

Największa klika maksymalna jest kliką maksymalną, a ponieważ grafy akordowe są doskonałe, rozmiar tej kliki jest równy liczbie chromatycznej wykresu akordowego. Grafy akordowe są doskonale uporządkowane : optymalne kolorowanie można uzyskać, stosując algorytm zachłannego kolorowania wierzchołków w odwrotności idealnego uporządkowania eliminacji.

Wielomian chromatyczny wykresu akordowego jest łatwy do obliczenia. Znajdź idealną eliminację porządkującą $v 1, v 2, \dots, v n$ . Niech $N i$ równa się liczbie sąsiadów $v i$ , którzy występują po $v i$ w tym porządku. Na przykład $N n = 0$ . Wielomian chromatyczny jest równy ${\ Displaystyle (x-N_ {1}) (x-N_ {2}) \ cdots (x-N_ {n}).}$ (Ostatni czynnik to po prostu $x$ , więc $x$ dzieli wielomian tak, jak powinien). Oczywiście to obliczenie zależy od akordowości.

Minimalne separatory

W każdym grafie separator wierzchołków to zbiór wierzchołków, których usunięcie pozostawia rozłączony pozostały graf; separator jest minimalny, jeśli nie ma odpowiedniego podzbioru, który jest również separatorem. Zgodnie z twierdzeniem Diraca (1961) grafy akordowe to grafy, w których każdy minimalny separator jest kliką; Dirac użył tej charakterystyki, aby udowodnić, że grafy akordowe są doskonałe .

Rodzinę grafów akordowych można zdefiniować indukcyjnie jako grafy, których wierzchołki można podzielić na trzy niepuste podzbiory $ZA$ , $S$ i $B$ , tak że ${\ Displaystyle A \ cup S}$ i ${\ displaystyle S \ cup B}$ oba tworzą podgrafy indukowane akordami , $S$ jest kliką i nie ma krawędzi od $A$ do $B.$ Oznacza to, że są to grafy, które mają rekurencyjną dekompozycję za pomocą separatorów klik na mniejsze podgrafy. Z tego powodu grafy akordowe były czasami nazywane grafami rozkładalnymi .

Wykresy przecięć poddrzew

Graf akordowy z ośmioma wierzchołkami, reprezentowany jako wykres przecięcia ośmiu poddrzew drzewa sześciowęzłowego.

Alternatywna charakterystyka grafów akordowych, ze względu na Gavrila (1974) , obejmuje drzewa i ich poddrzewa.

Ze zbioru poddrzew drzewa można zdefiniować graf poddrzewa , który jest grafem przecięcia , który ma jeden wierzchołek na poddrzewo i krawędź łączącą dowolne dwa poddrzewa, które zachodzą na siebie w jednym lub większej liczbie węzłów drzewa. Gavril wykazał, że grafy poddrzew są dokładnie grafami akordowymi.

Reprezentacja wykresu akordowego jako przecięcia poddrzew tworzy drzewiastą dekompozycję grafu, przy czym szerokość drzewa jest o jeden mniejsza niż rozmiar największej kliki na grafie; rozkład drzewa dowolnego wykresu G można postrzegać w ten sposób jako reprezentację G jako podwykresu wykresu akordowego. Dekompozycja drzewa grafu jest również drzewem połączeń algorytmu drzewa połączeń .

Związek z innymi klasami grafów

Podklasy

Grafy interwałowe to grafy przecięcia poddrzew grafów ścieżkowych , szczególny przypadek drzew. Dlatego są podrodziną grafów akordowych.

Grafy podzielone to grafy, które są zarówno grafami akordowymi, jak i dopełnieniami grafów akordowych. Bender, Richmond i Wormald (1985) wykazali, że w granicy, gdy $n$ dąży do nieskończoności, ułamek $n$ -wierzchołkowych grafów cięciwowych, które są podzielone, zbliża się do jedności.

Grafy ptolemejskie to grafy, które są dziedziczne zarówno akordowo, jak i odległościowo . Wykresy quasi-progowe są podklasą grafów ptolemeuszowych, które są zarówno akordami, jak i kografami . Grafy blokowe to kolejna podklasa grafów ptolemeuszowych, w których każde dwie maksymalne kliki mają co najwyżej jeden wspólny wierzchołek. Szczególnym typem są grafy wiatraków , w których wspólny wierzchołek jest taki sam dla każdej pary klik.

Grafy silnie akordowe to grafy, które są akordowe i nie zawierają $n$ -słońce (dla $n \geq 3$ ) jako indukowanego podgrafu. Tutaj $n$ -słońce jest $n-$ wierzchołkowym grafem cięciwy $G$ wraz ze zbiorem $n$ wierzchołków stopnia drugiego, sąsiadujących z krawędziami cyklu Hamiltona w $G$ .

$K$ -drzewa to grafy akordowe, w których wszystkie kliki maksymalne i wszystkie separatory klik maksymalnych mają ten sam rozmiar. Sieci apollińskie to akordowe maksymalne planarne grafy lub równoważnie planarne 3-drzewa. Maksymalne grafy płaszczyzny zewnętrznej są podklasą 2-drzew, a zatem są również akordowe.

Nadklasy

Grafy akordowe są podklasą dobrze znanych grafów doskonałych . Inne nadklasy grafów akordowych obejmują grafy słabo akordowe, grafy wygranych policjantów , grafy bez nieparzystych dziur, grafy bez parzystych dziur i grafy Meyniela . Wykresy akordowe to właśnie grafy, które są zarówno wolne od nieparzystych, jak i parzystych dziur (patrz dziury w teorii grafów).

Każdy wykres akordowy jest grafem zwichniętym , wykresem, w którym każdy cykl peryferyjny jest trójkątem, ponieważ cykle peryferyjne są szczególnym przypadkiem cykli indukowanych. Grafy spłaszczone to grafy, które można utworzyć z sum klików grafów akordowych i maksymalnych grafów planarnych. Dlatego grafy uduszone obejmują maksymalne grafy planarne .

Uzupełnienia akordowe i szerokość drzewa

Jeśli $G$ jest arbitralnym wykresem, akordowe dopełnienie G $($ lub minimalne wypełnienie ) jest wykresem akordowym, który zawiera $G$ jako podgraf. Sparametryzowana wersja minimalnego wypełnienia jest traktowalna z ustalonymi parametrami , a ponadto jest rozwiązywalna w sparametryzowanym czasie podwykładniczym. Szerokość drzewa G jest o jeden mniejsza niż liczba wierzchołków w maksymalnej kliki uzupełnienia akordowego wybranej w celu zminimalizowania rozmiaru tej kliki $.$ K $-$ drzewa to grafy, do których nie można dodawać żadnych dodatkowych krawędzi bez zwiększania ich szerokości drzewa do liczby większej niż $k$ . Dlatego $k$ są ich własnymi uzupełnieniami akordowymi i tworzą podklasę grafów akordowych. Uzupełnień akordowych można również użyć do scharakteryzowania kilku innych powiązanych klas grafów.

Notatki

Agnarsson, Geir (2003), „O grafach akordowych i ich wielomianach chromatycznych” , Mathematica Scandinavica , 93 (2): 240–246, doi : 10,7146/math.scand.a-14421 , MR 2009583 .
Bender, EA; Richmond, LB; Wormald, Karolina Północna (1985), „Prawie wszystkie wykresy akordów podzielone”, J. Austral. Matematyka soc. , A, 38 (2): 214–221, doi : 10.1017/S1446788700023077 , MR 0770128 .
Berge, Claude (1967), „Niektóre klasy doskonałych grafów”, w Harary, Frank (red.), Graph Theory and Theoretical Physics , Academic Press, s. 155–165, MR 0232694 .
Berry, Anna; Golumbic, Martin Charles ; Lipshteyn, Marina (2007), „Rozpoznawanie wykresów sondy akordowej i wykresów dwukolorowych w cyklu”, SIAM Journal on Discrete Mathematics , 21 (3): 573–591, doi : 10.1137/050637091 .
Bodlaender, HL ; Stypendyści, MR ; Warnow, TJ (1992), „Dwa uderzenia przeciwko doskonałej filogenezie” (PDF) , Proc. z XIX Międzynarodowego Kolokwium Języków i Programowania Automatów , Notatki z wykładów z informatyki, tom. 623, s. 273–283, doi : 10.1007/3-540-55719-9_80 , hdl : 1874/16653 .
Chandran, LS; Ibarra, L.; Ruskey, F .; Sawada, J. (2003), „Wyliczanie i charakteryzacja doskonałych porządków eliminacji grafu akordowego” (PDF) , Theoretical Computer Science , 307 (2): 303–317, doi : 10.1016 / S0304-3975 (03) 00221- 4 .
Dirac, GA (1961), „O wykresach obwodów sztywnych” (PDF) , Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 25 (1–2): 71–76, doi : 10.1007 / BF02992776 , MR 0130190 , S2CID 120608513 .
Fomin, Fedor V.; Villager, Yngve (2013), „Podwykładniczy algorytm parametryczny dla minimalnego wypełnienia”, SIAM J. Comput. , 42 (6): 2197-2216, arXiv : 1104.2230 , doi : 10.1137/11085390X , S2CID 934546 .
Fulkerson, DR ; Gross, OA (1965), „Macierze zdarzeń i wykresy interwałowe” , Pacific J. Math. , 15 (3): 835–855, doi : 10.2140/pjm.1965.15.835 .
Gavril, Fănică (1974), „Wykresy przecięcia poddrzew w drzewach są dokładnie wykresami akordów”, Journal of Combinatorial Theory , Seria B, 16 : 47–56, doi : 10.1016/0095-8956 (74) 90094-X .
Golumbic, Martin Charles (1980), Algorytmiczna teoria grafów i doskonałe wykresy , Academic Press .
Habib, Michel; McConnell, Ross; Paweł, Krzysztof; Viennot, Laurent (2000), „Lex-BFS i udoskonalanie partycji, z zastosowaniami do orientacji przechodniej, rozpoznawania wykresów interwałowych i testowania kolejnych” , Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016 / S0304-3975(97)00241-7 .
Kaplan, Haim; Szamir, Ron; Tarjan, Robert (1999), „Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal i Proper Interval Graphs”, SIAM J. Comput. , 28 (5): 1906–1922, doi : 10.1137/S0097539796303044 .
Maffray, Frédéric (2003), „O zabarwieniu doskonałych grafów”, w: Reed, Bruce A .; Sprzedaż, Cláudia L. (red.), Najnowsze postępy w algorytmach i kombinatoryce , CMS Books in Mathematics, tom. 11, Springer-Verlag, s. 65–84, doi : 10.1007/0-387-22444-0_3 , ISBN 0-387-95434-1 .
Parra, Andreas; Scheffler, Petra (1997), „Charakterystyka i algorytmiczne zastosowania osadzania grafu akordowego”, Discrete Applied Mathematics , 79 (1–3): 171–188, doi : 10.1016 / S0166-218X (97) 00041-3 , MR 1478250 .
Patil, HP (1986), „O strukturze k -drzew”, Journal of Combinatorics, Information and System Sciences , 11 (2–4): 57–64, MR 0966069 .
Rose, D.; Lueker, George; Tarjan, Robert E. (1976), „Algorytmiczne aspekty eliminacji wierzchołków na grafach”, SIAM Journal on Computing , 5 (2): 266–283, doi : 10.1137/0205021 , MR 0408312 .
Seymour, PD ; Weaver, RW (1984), „Uogólnienie wykresów akordowych”, Journal of Graph Theory , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR 0742878 .
Szwarcfiter, JL ; Bornstein, CF (1994), „Kliki wykresów akordów i ścieżek”, SIAM Journal on Discrete Mathematics , 7 (2): 331–336, doi : 10.1137/s0895480191223191 , hdl : 11422/1497 .

Linki zewnętrzne