Idealnie uporządkowany wykres

W teorii grafów grafem doskonale uporządkowanym jest graf, którego wierzchołki można uporządkować w taki sposób, że algorytm zachłannego kolorowania z tym uporządkowaniem optymalnie koloruje każdy indukowany podgraf danego grafu. Grafy doskonale uporządkowane stanowią szczególny przypadek grafów doskonałych i obejmują grafy akordowe , grafy porównywalności i grafy dziedziczne od odległości . Jednak testowanie, czy graf jest doskonale uporządkowany, jest NP-zupełne .

Definicja

Algorytm zachłannego kolorowania, zastosowany do określonej kolejności wierzchołków grafu G , uwzględnia wierzchołki grafu w kolejności i przypisuje każdemu wierzchołkowi jego pierwszy dostępny kolor, minimalną wykluczoną wartość dla zestawu kolorów używanych przez jego sąsiadów. Różne uporządkowania wierzchołków mogą spowodować, że ten algorytm będzie używał różnej liczby kolorów. Zawsze istnieje uporządkowanie, które prowadzi do optymalnego zabarwienia - dotyczy to na przykład uporządkowania określonego na podstawie optymalnego zabarwienia poprzez sortowanie wierzchołków według ich koloru - ale znalezienie go może być trudne. Grafy doskonale uporządkowane definiuje się jako takie, dla których istnieje uporządkowanie optymalne dla algorytmu zachłannego nie tylko dla samego grafu, ale dla wszystkich jego podgrafy indukowane .

mówi się, że graf G jest doskonale uporządkowany, jeśli istnieje uporządkowane π wierzchołków G , takie że każdy indukowany podgraf G jest optymalnie pokolorowany przez algorytm zachłanny wykorzystujący podsekwencję π indukowaną przez wierzchołki podgrafu . Uporządkowanie π ma tę właściwość dokładnie wtedy, gdy nie istnieją cztery wierzchołki a , b , c i d dla których abcd jest ścieżką indukowaną, a pojawia się przed b w kolejności, a c pojawia się po d w kolejności.

Złożoność obliczeniowa

Grafy doskonale uporządkowane są NP-zupełne do rozpoznania. Łatwo jednak sprawdzić, czy określone uporządkowanie jest idealnym uporządkowaniem grafu. W związku z tym znalezienie idealnego uporządkowania grafu jest również NP-trudne, nawet jeśli wiadomo już, że graf jest doskonale uporządkowany.

Powiązane klasy wykresów

Każdy graf doskonale uporządkowany jest grafem doskonałym .

Wykresy akordowe są doskonale uporządkowane; idealne uporządkowanie wykresu akordowego można znaleźć, odwracając idealną kolejność eliminacji dla wykresu. Zatem zastosowanie zachłannego kolorowania do idealnego uporządkowania zapewnia wydajny algorytm optymalnego kolorowania wykresów akordowych. Grafy porównywalności są również doskonale uporządkowane, przy czym doskonałe uporządkowanie daje topologiczne uporządkowanie przechodniej orientacji wykresu. Wykresy dopełnienia wykresów tolerancji są doskonale uporządkowane.

Inną klasę doskonale uporządkowanych grafów dają grafy G takie, że w każdym podzbiorze pięciu wierzchołków z G przynajmniej jeden z tych pięciu ma domknięte sąsiedztwo , które jest podzbiorem (lub jest równe) domkniętemu sąsiedztwu innego z pięć wierzchołków. Równoważnie, są to grafy, w których częściowy porządek zamkniętych sąsiedztw, uporządkowany według włączenia zbioru, ma szerokość co najwyżej cztery. Wykres cyklu 5 wierzchołków ma sąsiedztwo częściowego rzędu szerokości pięć, więc cztery to maksymalna szerokość, która zapewnia doskonałą uporządkowalność. Podobnie jak w przypadku wykresów akordowych (i ogólnie w przeciwieństwie do wykresów doskonale uporządkowanych), wykresy o szerokości cztery są rozpoznawalne w czasie wielomianowym.

Koncepcją pośrednią między idealnym uporządkowaniem eliminacji grafu akordowego a doskonałym uporządkowaniem jest półdoskonałe uporządkowanie eliminacji : w uporządkowaniu eliminacji nie ma ścieżki indukowanej trzema wierzchołkami , w której środkowy wierzchołek jest pierwszym z trzech do wyeliminowania, aw semidoskonałym porządku eliminacji nie ma ścieżki indukowanej czterema wierzchołkami, w której jeden z dwóch środkowych wierzchołków jest eliminowany jako pierwszy. Odwrotność tego uporządkowania spełnia zatem wymagania idealnego uporządkowania, więc grafy z półdoskonałymi porządkami eliminacji są doskonale uporządkowane. W szczególności to samo leksykograficzny algorytm przeszukiwania wszerz używany do znajdowania doskonałych rzędów eliminacji grafów akordowych może być używany do znajdowania półdoskonałych rzędów eliminacji grafów dziedzicznych od odległości , które w związku z tym są również doskonale uporządkowane.

Grafy, dla których każde uporządkowanie wierzchołków jest uporządkowaniem doskonałym, to kografy . Ponieważ kografy są grafami bez ścieżki indukowanej czterema wierzchołkami, nie mogą naruszać wymogu uporządkowania ścieżek w przypadku idealnego uporządkowania.

Znanych jest kilka dodatkowych klas doskonale uporządkowanych grafów.

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Perfectly_orderable_graph&oldid=1136192565 ”