Spójny zestaw dominujący

W teorii grafów spójny zbiór dominujący i drzewo o maksymalnym rozpiętości liści to dwie blisko spokrewnione struktury zdefiniowane na grafie nieskierowanym .

Definicje

Spójny dominujący zbiór grafu G to zbiór D wierzchołków o dwóch właściwościach:

  1. Każdy węzeł w D może dotrzeć do dowolnego innego węzła w D ścieżką, która pozostaje całkowicie w D . Oznacza to, że D indukuje spójny podgraf G .
  2. Każdy wierzchołek w G albo należy do D , albo sąsiaduje z wierzchołkiem w D. Oznacza to, że D jest dominującym zbiorem G .

Minimalny spójny dominujący zbiór grafu G jest spójnym dominującym zbiorem o najmniejszej możliwej liczności spośród wszystkich spójnych dominujących zbiorów G . Spójna liczba dominacji G to liczba wierzchołków w minimalnym spójnym zbiorze dominującym .

Każde drzewo rozpinające T grafu G ma co najmniej dwa liście, wierzchołki, które mają incydentną tylko jedną krawędź T. Maksymalne drzewo rozpinające to drzewo rozpinające, które ma największą możliwą liczbę liści spośród wszystkich drzew rozpinających G . Maksymalna liczba liści G to liczba liści w maksymalnym drzewie obejmującym liście.

Komplementarność

Jeśli d jest spójną liczbą dominacji grafu n -wierzchołkowego G , gdzie n > 2 , a l jest jego maksymalną liczbą liści, to trzy wielkości d , l i n podlegają prostemu równaniu

Jeśli D jest spójnym zbiorem dominującym, to istnieje drzewo rozpinające w G , którego liście zawierają wszystkie wierzchołki, które nie należą do D : tworzą drzewo rozpinające podgrafu indukowanego przez D , wraz z krawędziami łączącymi każdy pozostały wierzchołek v , który nie jest w D do sąsiada v w D . To pokazuje, że l ≥ n - re .

W przeciwnym kierunku, jeśli T jest dowolnym drzewem rozpinającym w G , to wierzchołki T , które nie są liśćmi, tworzą spójny dominujący zbiór G . To pokazuje, że n - l ≥ re . Połączenie tych dwóch nierówności dowodzi równości n = d + l .

Dlatego w każdym grafie suma połączonej liczby dominacji i maksymalnej liczby liści jest równa całkowitej liczbie wierzchołków. Obliczeniowo oznacza to, że określenie połączonej liczby dominacji jest równie trudne, jak znalezienie maksymalnej liczby liści.

Algorytmy

Sprawdzanie, czy istnieje spójny zbiór dominujący o rozmiarze mniejszym niż dany próg, jest NP -zupełne, lub równoważnie sprawdzanie, czy istnieje drzewo rozpinające z co najmniej określoną liczbą liści. Dlatego uważa się, że problemu minimalnego spójnego zbioru dominującego i problemu maksymalnego drzewa rozpinającego liście nie można rozwiązać w czasie wielomianowym.

Patrząc pod kątem algorytmów aproksymacji, połączona dominacja i drzewa o maksymalnej rozpiętości liści nie są tym samym: przybliżenie jednego do danego współczynnika przybliżenia nie jest tym samym, co przybliżenie drugiego do tego samego współczynnika. Istnieje przybliżenie dla minimalnego połączonego zbioru dominującego, które osiąga współczynnik 2 ln Δ + O(1) , gdzie Δ jest maksymalnym stopniem wierzchołka w G. Problem drzewa rozpinającego maksymalny liść jest trudny MAX-SNP , co implikuje, że żaden schemat aproksymacji czasu wielomianowego nie jest prawdopodobny. Można go jednak przybliżyć z dokładnością do współczynnika 2 w czasie wielomianowym.

Oba problemy można rozwiązać na grafach n -wierzchołkowych w czasie O (1,9 n ) . Problem z maksymalnym liściem jest możliwy do rozwiązania ze stałymi parametrami , co oznacza, że ​​można go rozwiązać w czasie wykładniczym w liczbie liści, ale tylko wielomianowym w rozmiarze grafu wejściowego. Wartość klam tych algorytmów (intuicyjnie liczba liści, do których problem można rozwiązać w rozsądnym czasie) stopniowo wzrastała, wraz z poprawą algorytmów dla problemu, do około 37 i sugerowano, że co najmniej 50 powinno być osiągalne.

W grafach o maksymalnym stopniu trzecim problem połączonego zbioru dominującego i jego komplementarnego maksymalnego drzewa rozpinającego liście można rozwiązać w czasie wielomianowym , przekształcając je w przypadek problemu parzystości matroidów dla matroidów liniowych .

Aplikacje

Połączone zbiory dominujące są przydatne w obliczaniu tras dla mobilnych sieci ad hoc . W tej aplikacji mały połączony zestaw dominujący jest używany jako szkielet komunikacji, a węzły, które nie należą do tego zestawu, komunikują się, przekazując komunikaty przez sąsiadów znajdujących się w zestawie.

Maksymalna liczba liści została wykorzystana do opracowania algorytmów o stałych parametrach : kilka NP-trudnych problemów optymalizacyjnych można rozwiązać w czasie wielomianowym dla wykresów o ograniczonej maksymalnej liczbie liści.

Zobacz też

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