Wykres obojętności

Wykres obojętności utworzony ze zbioru punktów na prostej rzeczywistej przez połączenie par punktów, których odległość wynosi co najwyżej jeden

W teorii grafów , gałęzi matematyki, wykres obojętności jest grafem nieskierowanym zbudowanym przez przypisanie liczby rzeczywistej do każdego wierzchołka i połączenie dwóch wierzchołków krawędzią, gdy ich liczby znajdują się w odległości jednej jednostki od siebie. Wykresy obojętności są również wykresami przecięcia zbiorów przedziałów jednostkowych lub odpowiednio zagnieżdżonych przedziałów (przedziałów, z których żaden nie zawiera żadnego innego). W oparciu o te dwa typy reprezentacji interwałowych, wykresy te są również nazywane wykresami przedziałów jednostkowych lub odpowiednie wykresy interwałowe ; tworzą podklasę grafów interwałowych .

Równoważne charakterystyki

Zakazane indukowane podgrafy dla grafów obojętności: pazur, słońce i sieć (góra, lewa – prawa) oraz cykle o długości czterech lub więcej (dół)

Skończone wykresy obojętności można równoważnie scharakteryzować jako

• Wykresy przecięcia przedziałów jednostkowych ,
• Wykresy przecięcia zestawów przedziałów, z których żadne dwa nie są zagnieżdżone (jeden zawiera drugi),
• Wykresy przedziałów bez pazurów ,
• Grafy, które nie mają podgrafu indukowanego , izomorficznego z pazurem K _1,3 , net (trójkąt z wierzchołkiem stopnia pierwszego przylegającym do każdego z wierzchołków trójkąta), słońce (trójkąt otoczony trzema innymi trójkątami, z których każdy ma wspólny krawędź ze środkowym trójkątem) lub otwór (cykl o długości czterech lub więcej),
• Grafy nieporównywalności półrzędów , _
• Nieskierowane wykresy, które mają taki porządek liniowy , że dla każdych trzech uporządkowanych wierzchołków $-$ v $\ displaystyle v}$ w $w}$$\ displaystyle$ , jeśli , to tak są ${\ displaystyle uv}$ i ${\ displaystyle vw}$
• Grafy bez trójki astralnej , z trzema wierzchołkami połączonymi parami ścieżkami, które omijają trzeci wierzchołek, a także nie zawierają dwóch kolejnych sąsiadów trzeciego wierzchołka,
• Wykresy, w których każdy połączony komponent zawiera ścieżkę, w której każda maksymalna klika komponentu tworzy ciągłą ścieżkę podrzędną,
• Grafy, których wierzchołki można ponumerować w taki sposób, że każda najkrótsza ścieżka tworzy ciąg monotoniczny ,
• Grafy, których macierze sąsiedztwa można uporządkować w taki sposób, że w każdym wierszu i każdej kolumnie wartości niezerowe macierzy tworzą ciągły przedział sąsiadujący z główną przekątną macierzy.
• Podgrafy indukowane potęg dróg bez cięciwy.
• Moce liści posiadają korzeń liścia, który jest gąsienicą.

W przypadku grafów nieskończonych niektóre z tych definicji mogą się różnić.

Nieruchomości

Ponieważ są to szczególne przypadki wykresów interwałowych , wykresy obojętności mają wszystkie właściwości wykresów interwałowych; w szczególności są one szczególnym przypadkiem grafów akordowych i grafów doskonałych . Są one również szczególnym przypadkiem wykresów kołowych , co nie dotyczy bardziej ogólnie wykresów interwałowych.

W modelu grafów losowych Erdősa – Rényiego wykres wierzchołków, którego liczba krawędzi jest znacznie mniejsza niż $displaystyle$$n ^ {2/3}},$ wykresem obojętności o wysokiej prawdopodobieństwo, podczas gdy wykres, którego liczba krawędzi jest znacznie większa niż ${\ displaystyle n ^ {2/3}},$ nie będzie wykresem obojętności z dużym prawdopodobieństwem.

Szerokość pasma dowolnego wykresu $o$ jeden mniejsza niż rozmiar maksymalnej kliki na wykresie obojętności, który zawiera $podrzędny i jest$ wybrany tak, aby zminimalizować rozmiar maksymalnej kliki. Właściwość ta odpowiada podobnym relacjom między wykresami szerokości ścieżki i wykresami interwałowymi oraz między wykresami szerokości drzewa i wykresami akordowymi . Słabsze pojęcie szerokości, szerokość kliki , może być dowolnie duża na wykresach obojętności. Jednak każda właściwa podklasa grafów obojętności, która jest zamknięta pod grafami indukowanymi, ma ograniczoną szerokość kliki.

Każdy spójny graf obojętności ma ścieżkę Hamiltona . Graf obojętności ma cykl Hamiltona wtedy i tylko wtedy, gdy jest podwójnie spójny .

Grafy obojętności są zgodne z hipotezą rekonstrukcji : są jednoznacznie określone przez ich podgrafy z usuniętymi wierzchołkami.

Algorytmy

Podobnie jak w przypadku grafów dysków jednostkowych o większej liczbie wymiarów, możliwe jest przekształcenie zestawu punktów w ich wykres obojętności lub zestawu przedziałów jednostkowych w ich wykres przedziałów jednostkowych, w czasie liniowym mierzonym rozmiarem wykresu wyjściowego. Algorytm zaokrągla punkty (lub środki przedziałów) w dół do najbliższej mniejszej liczby całkowitej, używa tablicy mieszającej , aby znaleźć wszystkie pary punktów, których zaokrąglone liczby całkowite mieszczą się w obrębie jednego drugiego ( problem stałego promienia w pobliżu sąsiadów ) i filtruje wynikowe lista par dla tych, których niezaokrąglone wartości również mieszczą się w obrębie jednej drugiej.

Można sprawdzić, czy dany wykres jest wykresem obojętności w czasie liniowym, używając drzew PQ do skonstruowania reprezentacji przedziałowej grafu, a następnie sprawdzając, czy uporządkowanie wierzchołków wyprowadzone z tej reprezentacji spełnia właściwości wykresu obojętności. Możliwe jest również oparcie algorytmu rozpoznawania grafów obojętności na grafów akordowych . Kilka alternatywnych algorytmów liniowego rozpoznawania czasu jest opartych na przeszukiwaniu wszerz lub leksykograficznym przeszukiwaniu wszerz raczej niż na relacji między wykresami obojętności a wykresami interwałowymi.

Po posortowaniu wierzchołków według wartości liczbowych opisujących wykres obojętności (lub według sekwencji przedziałów jednostkowych w reprezentacji przedziałów) można zastosować tę samą kolejność, aby znaleźć optymalne kolorowanie wykresów dla tych wykresów, rozwiązać problem najkrótszej ścieżki , oraz do konstruowania ścieżek hamiltonowskich i maksymalnych dopasowań , wszystko w czasie liniowym. Cykl Hamiltona można znaleźć na podstawie właściwej reprezentacji przedziałowej wykresu w czasie ${\ displaystyle O (n \ log n)}$ , ale gdy sam wykres jest podany jako dane wejściowe, ten sam problem dopuszcza rozwiązanie w czasie liniowym, które można uogólnić na wykresy przedziałowe.

Kolorowanie listy pozostaje NP-zupełne, nawet jeśli jest ograniczone do wykresów obojętności. Jednak jest on możliwy do zastosowania ze stałymi parametrami , gdy jest sparametryzowany przez całkowitą liczbę kolorów na wejściu.

Aplikacje

W psychologii matematycznej wykresy obojętności powstają z funkcji użyteczności poprzez skalowanie funkcji w taki sposób, że jedna jednostka reprezentuje różnicę w użyteczności na tyle małą, że można założyć, że jednostki są na nią obojętne. W tej aplikacji pary przedmiotów, których użyteczności mają dużą różnicę, mogą być częściowo uporządkowane według względnej kolejności ich użyteczności, dając semiorder .

W bioinformatyce problem powiększania kolorowego wykresu do odpowiednio pokolorowanego wykresu przedziałów jednostkowych może być wykorzystany do modelowania wykrywania fałszywie ujemnych wyników w składaniu sekwencji DNA z kompletnych trawień .

Zobacz też

• Graf progowy , graf, którego krawędzie są określone przez sumy etykiet wierzchołków, a nie różnice etykiet
• Graf trywialnie doskonały , wykresy przedziałowe, dla których każda para przedziałów jest zagnieżdżona lub rozłączna, a nie prawidłowo przecinająca się
• Wykres dysku jednostkowego , dwuwymiarowy odpowiednik wykresów obojętności

Linki zewnętrzne

• System informacyjny na wykresie Inkluzje klas : wykres interwału jednostkowego