Drzewo opinające — Spanning tree

Drzewo opinające (niebieskie, ciężkie krawędzie) wykresu siatki grid

W matematycznej dziedzinie teorii wykres , A drzewo rozpinające T o nieukierunkowane grafu G jest subgraph czyli drzew , które zawiera wszystkie wierzchołki o G . Ogólnie rzecz biorąc, graf może mieć kilka drzew opinających, ale graf, który nie jest połączony , nie będzie zawierał drzewa opinającego (patrz lasy opinające poniżej). Jeśli wszystkie krawędzie z G są także krawędzie drzewo rozpinające T do G , a G jest drzewem, a także jest identyczny T (to jest drzewo ma unikalną dendrytowego, a ono samo).

Aplikacje

Kilka wyszukiwania ścieżek algorytmy, w tym Algorytm Dijkstry i A * algorytm wyszukiwania , wewnętrznie zbudować drzewo rozpinające jako pośredni krok w rozwiązaniu problemu.

W celu minimalizacji kosztów sieci energetycznych, połączeń okablowania, orurowania, automatycznego rozpoznawania mowy itp. ludzie często stosują algorytmy, które stopniowo budują drzewo rozpinające (lub wiele takich drzew) jako kroki pośrednie w procesie znajdowania minimalnego drzewa rozpinającego .

Internet i wiele innych sieci telekomunikacyjnych posiada łącza transmisyjne, które łączą węzły w topologii siatki zawierającej pewne pętle. Aby uniknąć pętli mostowych i routingu , wiele protokołów routingu zaprojektowanych dla takich sieci — w tym protokół drzewa opinającego , Open Shortest Path First , protokół routingu według stanu łącza , routing oparty na drzewie rozszerzonym itp. — wymaga, aby każdy router pamiętał drzewo opinające.

Specjalny rodzaj drzewa opinającego, drzewo Xuong , jest używany w teorii grafów topologicznych do znajdowania osadzeń grafów z maksymalnym rodzajem . Drzewo Xuong to drzewo opinające, w którym na pozostałym wykresie liczba połączonych komponentów o nieparzystej liczbie krawędzi jest tak mała, jak to możliwe. Drzewo Xuong i związane z nim osadzenie maksymalnego rodzaju można znaleźć w czasie wielomianowym .

Definicje

Drzewo to połączony graf nieskierowany bez cykli . Jest to drzewo opinające grafu G, jeśli obejmuje on G (czyli zawiera każdy wierzchołek G ) i jest podgrafem G (każda krawędź drzewa należy do G ). Drzewo opinające połączonego grafu G można również zdefiniować jako maksymalny zbiór krawędzi G, który nie zawiera cyklu, lub jako minimalny zbiór krawędzi łączących wszystkie wierzchołki.

Cykle podstawowe

Dodanie tylko jednej krawędzi do drzewa opinającego stworzy cykl; taki cykl nazywa się cyklem podstawowym . Dla każdej krawędzi, która nie znajduje się w drzewie opinającym, istnieje odrębny cykl podstawowy; w ten sposób istnieje zależność jeden do jednego między podstawowymi cyklami a krawędziami, które nie znajdują się w drzewie opinającym. Dla połączonego grafu z V wierzchołkami, każde drzewo opinające będzie miało V  − 1 krawędzi, a zatem graf krawędzi E i jedno z jego drzew opinających będzie miał E  −  V  + 1 podstawowe cykle (liczba krawędzi odjęta przez liczbę krawędzie zawarte w drzewie opinającym; z podaniem liczby krawędzi nieuwzględnionych w drzewie opinającym). Dla dowolnego drzewa opinającego zbiór wszystkich  podstawowych cykli E  -  V +1 tworzy bazę cykli , bazę przestrzeni cykli .

Podstawowe cięciaset

Podwójnym pojęciem podstawowego cyklu jest pojęcie fundamentalnego zestawu przekrojowego . Usunięcie tylko jednej krawędzi drzewa opinającego powoduje podział wierzchołków na dwa rozłączne zestawy. Podstawowy zbiór jest zdefiniowany jako zbiór krawędzi, które muszą zostać usunięte z grafu G, aby dokonać tego samego podziału. W ten sposób każde drzewo  opinające definiuje zestaw podstawowych zestawów przekrojów V -1, po jednym dla każdej krawędzi drzewa opinającego.

Dwoistość między podstawowymi przekrojami i podstawowymi cyklami jest ustalana przez zauważenie, że krawędzie cykli, które nie znajdują się w drzewie opinającym, mogą pojawić się tylko w przekrojach innych krawędzi w cyklu; i vice versa : krawędzie w cutset mogą pojawić się tylko w tych cyklach, które zawierają krawędź odpowiadającą cutsetowi. Ta dwoistość może być również wyrażona za pomocą teorii matroidów , zgodnie z którą drzewo opinające jest podstawą matrycy graficznej , cyklem podstawowym jest unikalny obwód w zbiorze utworzonym przez dodanie jednego elementu do podstawy, a podstawowe zestawy przekrojów są zdefiniowane w ten sam sposób z podwójnego matroida .

Lasy opinające

W grafach, które nie są połączone, nie może być drzewa opinającego i zamiast tego należy rozważyć lasy opinające. Oto dwie konkurujące ze sobą definicje:

• Niektórzy autorzy uważają las opinający za maksymalnie acykliczny podgraf danego grafu lub równoważnie graf składający się z drzewa opinającego w każdym połączonym elemencie grafu.
• Dla innych autorów las opinający to las, który obejmuje wszystkie wierzchołki, co oznacza tylko, że każdy wierzchołek grafu jest wierzchołkiem w lesie. W przypadku tej definicji nawet połączony wykres może mieć rozłączony las opinający, taki jak las, w którym każdy wierzchołek tworzy drzewo o jednym wierzchołku.

Aby uniknąć pomyłek między tymi dwiema definicjami, Gross i Yellen (2005) proponują termin „full spanning forest” dla lasu o tej samej łączności, co podany wykres, podczas gdy Bondy i Murty (2008) nazywają ten rodzaj lasu „ maksymalny las rozpiętościowy”.

Liczenie drzew spinających

Wzór Cayleya zlicza liczbę drzew opinających na pełnym wykresie. Są drzewa w , drzewa w , i drzewa w .${\ Displaystyle 2 ^ {2-2} = 1}$${\displaystyle K_{2}}$${\ Displaystyle 3 ^ {3-2} = 3}$${\displaystyle K_{3}}$${\ Displaystyle 4 ^ {4-2} = 16}$${\ Displaystyle K_{4}}$

Liczba t ( G ) drzew spinających w grafie spójnym jest dobrze zbadanym niezmiennikiem .

Na konkretnych wykresach

W niektórych przypadkach łatwo jest obliczyć t ( G ) bezpośrednio:

• Jeśli G jest samo w sobie drzewem, to t ( G ) = 1 .
• Gdy G jest wykresem cyklu C _n z n wierzchołkami, wtedy t ( G ) =  n .
• Dla pełnego grafu z n wierzchołkami, wzór Cayleya podaje liczbę drzew opinających jako n ^{n  − 2} .
• Jeśli G jest kompletnym grafem dwudzielnym , to .${\displaystyle K_{p,q}}$${\ Displaystyle t (G) = p ^ {q-1} q ^ {p-1}}$
• Dla n- wymiarowego grafu hipersześcianowego liczba drzew opinających wynosi .${\ Displaystyle Q_ {n}}$${\ Displaystyle t (G) = 2 ^ {2 ^ {n} - n-1} \ prod _ {k = 2} ^ {n} k ^ {n \ wybierz k}}$

W dowolnych wykresach

Mówiąc ogólniej, dla każdego grafu G liczba t ( G ) może być obliczona w czasie wielomianowym , jak determinanty z matrycy pochodzącej z wykresu przy użyciu macierzy drzewa twierdzenie Kirchhoffa .

W szczególności, aby obliczyć t ( G ), konstruuje się macierz Laplace'a wykresu, macierz kwadratową, w której zarówno wiersze, jak i kolumny są indeksowane przez wierzchołki G . Wpis w wierszu i i kolumnie j jest jedną z trzech wartości:

• Stopień wierzchołka i , jeśli i  =  j ,
• -1, jeśli wierzchołki i i j sąsiadują ze sobą, lub
• 0, jeśli wierzchołki i oraz j różnią się od siebie, ale nie sąsiadują ze sobą.

Otrzymana macierz jest singular , więc jej wyznacznikiem jest zero. Jednak usunięcie wiersza i kolumny dla arbitralnie wybranego wierzchołka prowadzi do mniejszej macierzy, której wyznacznikiem jest dokładnie  t ( G ).

Usunięcie-skrót

Jeśli G jest grafem lub multigrafem, a e jest arbitralną krawędzią G , to liczba t ( G ) drzew opinających G spełnia powtarzalność skrócenia i usunięcia t ( G ) =  t ( G  −  e ) +  t ( G / e ), gdzie G  -  e jest multigraf otrzymać usuwając e i G / e jest skurcz z G poprzez e . Termin t ( G  -  e ) w tym wzorze zlicza drzewa opinające  G , które nie używają krawędzi  e , a termin t ( G / e ) zlicza drzewa opinające  G, które używają  e .

W tym wzorze, jeśli dany graf G jest multigrafem lub jeśli skrócenie powoduje, że dwa wierzchołki są połączone ze sobą wieloma krawędziami, to nadmiarowe krawędzie nie powinny być usuwane, ponieważ prowadziłoby to do błędnej sumy. Na przykład wykres wiązań łączący dwa wierzchołki k krawędziami ma k różnych drzew opinających, z których każdy składa się z jednej z tych krawędzi.

Wielomian Tutte

Tutte wielomian wykresu można zdefiniować jako sumę ponad Spanning drzew wykresu terminów liczonego od „aktywności wewnętrznej” i „zewnętrznej aktywności” drzewa. Jego wartością w argumentach (1,1) jest liczba drzew opinających lub, w grafie rozłączonym, liczba maksymalnych lasów opinających.

Wielomian Tutte można również obliczyć przy użyciu powtarzalności skrócenia usunięcia, ale jego złożoność obliczeniowa jest wysoka: dla wielu wartości jego argumentów obliczenie go dokładnie jest #P-kompletne , a także jest trudne do aproksymacji z gwarantowanym współczynnikiem aproksymacji . Jednym z nielicznych wyjątków jest punkt (1,1), w którym można go oszacować za pomocą twierdzenia Kirchhoffa.

Algorytmy

Budowa

Pojedyncze drzewo opinające grafu można znaleźć w czasie liniowym za pomocą przeszukiwania w głąb lub wszerz . Oba te algorytmy eksplorują dany graf, zaczynając od dowolnego wierzchołka v , przechodząc przez sąsiadów wykrytych wierzchołków i dodając każdego nieodkrytego sąsiada do struktury danych, która ma zostać zbadana później. Różnią się one tym, czy ta struktura danych jest stosem (w przypadku wyszukiwania w głąb), czy kolejką (w przypadku wyszukiwania wszerz). W każdym przypadku można utworzyć drzewo opinające, łącząc każdy wierzchołek, inny niż wierzchołek korzenia v , z wierzchołkiem, z którego został odkryty. To drzewo jest znane jako drzewo wyszukiwania w głąb lub wszerz, zgodnie z algorytmem eksploracji grafów użytym do jego skonstruowania. Drzewa przeszukiwania w głąb są szczególnym przypadkiem klasy drzew opinających zwanych drzewami Trémaux , nazwanych na cześć XIX-wiecznego odkrywcy przeszukiwania w głąb.

Drzewa opinające są ważne w obliczeniach równoległych i rozproszonych, jako sposób utrzymywania komunikacji między zestawem procesorów; zobacz na przykład protokół Spanning Tree używany przez urządzenia warstwy łącza OSI lub Shout (protokół) do przetwarzania rozproszonego. Jednak metody „najpierw w głąb” i „wszerz” służące do konstruowania drzew opinających na komputerach sekwencyjnych nie są dobrze dostosowane do komputerów równoległych i rozproszonych. Zamiast tego naukowcy opracowali kilka bardziej wyspecjalizowanych algorytmów do znajdowania drzew opinających w tych modelach obliczeniowych.

Optymalizacja

W pewnych dziedzinach teorii grafów jest często przydatne do znalezienia minimalnego Spanning Tree o ważonej wykresu . Zbadano również inne problemy optymalizacyjne na drzewach opinających, w tym maksymalne drzewo napinające, minimalne drzewo opinające co najmniej k wierzchołków, drzewo napinające z najmniejszą liczbą krawędzi na wierzchołek , drzewo napinające z największą liczbą liści , drzewo napinające z najmniejszą liczbą liści (ściśle związane z problemem ścieżki hamiltonowskiej ), drzewem opinającym o minimalnej średnicy i drzewie opinającym o minimalnej dylatacji.

Zbadano również optymalne problemy drzewa opinającego dla skończonych zbiorów punktów w przestrzeni geometrycznej, takiej jak płaszczyzna euklidesowa . Dla takich danych wejściowych drzewo opinające to znowu drzewo, którego wierzchołkami są podane punkty. Jakość drzewa mierzy się w taki sam sposób, jak na wykresie, stosując odległość euklidesową między parami punktów jako wagę każdej krawędzi. Tak więc, na przykład, minimalne drzewo rozpinające euklidesowe jest tym samym, co minimalne drzewo rozpinające grafu w kompletnym grafie z euklidesowymi wagami krawędzi. Jednak nie jest konieczne konstruowanie tego grafu w celu rozwiązania problemu optymalizacji; Na przykład problem euklidesowego minimalnego drzewa opinającego można rozwiązać wydajniej w czasie O ( n  log  n ) poprzez skonstruowanie triangulacji Delaunaya, a następnie zastosowanie do wynikowej triangulacji algorytmu minimalnego drzewa opinającego grafu liniowego w czasie .

Randomizacja

Drzewo opinające wybrane losowo spośród wszystkich drzew opinających z jednakowym prawdopodobieństwem nazywane jest jednolitym drzewem opinającym . Algorytm Wilsona może być wykorzystany do wygenerowania jednostajnych drzew spinających w czasie wielomianowym poprzez proces losowego błądzenia na danym grafie i wymazania cykli utworzonych przez ten błądzenie.

Alternatywnym modelem losowego, ale niejednorodnego generowania drzew opinających jest losowe minimalne drzewo opinające . W tym modelu krawędziom grafu przypisuje się losowe wagi, a następnie konstruowane jest minimalne drzewo rozpinające grafu ważonego.

Wyliczenie

Ponieważ graf może mieć wykładniczo wiele drzew opinających, nie jest możliwe wymienienie ich wszystkich w czasie wielomianowym . Wiadomo jednak, że algorytmy wymieniają wszystkie drzewa opinające w czasie wielomianowym na drzewo.

Na nieskończonych wykresach

Każdy skończenie połączony graf ma drzewo opinające. Jednak w przypadku nieskończenie połączonych grafów istnienie drzew opinających jest równoważne aksjomatowi wyboru . Nieskończony wykres jest połączony, jeśli każda para jego wierzchołków tworzy parę punktów końcowych skończonej ścieżki. Podobnie jak w przypadku grafów skończonych, drzewo jest grafem spójnym bez skończonych cykli, a drzewo opinające można zdefiniować albo jako maksymalny acykliczny zbiór krawędzi, albo jako drzewo zawierające każdy wierzchołek.

Drzewa w grafie mogą być częściowo uporządkowane według ich relacji podgrafu, a każdy nieskończony łańcuch w tej częściowej kolejności ma górną granicę (zjednoczenie drzew w łańcuchu). Lemat Zorna , jedno z wielu równoważnych stwierdzeń aksjomatu wyboru, wymaga, aby porządek częściowy, w którym wszystkie łańcuchy są ograniczone od góry, miał element maksymalny; w porządku częściowym na drzewach grafu ten maksymalny element musi być drzewem opinającym. Dlatego, jeśli założymy lemat Zorna, każdy nieskończenie połączony graf ma drzewo opinające.

W przeciwnym kierunku, mając daną rodzinę zbiorów , możliwe jest skonstruowanie grafu nieskończonego w taki sposób, że każdemu drzewu rozpinającemu grafu odpowiada funkcja wyboru rodziny zbiorów. Dlatego, jeśli każdy nieskończenie spójny graf ma drzewo opinające, to aksjomat wyboru jest prawdziwy.

W skierowanych multigrafach

Ideę drzewa opinającego można uogólnić na multigrafy skierowane. Mając wierzchołek v na multigrafie skierowanym G , zorientowane drzewo rozpinające T zakorzenione w punkcie v jest acyklicznym podgrafem G, w którym każdy wierzchołek inny niż v ma stopień wyjściowy 1. Ta definicja jest spełniona tylko wtedy, gdy „gałęzie” T wskazują na v .

Zobacz też

• Algorytm zalewania
• Dobre drzewo opinające – drzewo opinające dla osadzonego grafu planarnego

Bibliografia