Drzewo kwitnące (teoria grafów)
W badaniu grafów planarnych drzewa kwitnące to drzewa z dodatkowymi skierowanymi połówkami krawędzi. Każde drzewo kwitnące jest powiązane z osadzeniem grafu planarnego. Drzewa kwitnące mogą być używane do próbkowania losowych grafów planarnych.
Opis
Drzewo kwitnące jest zbudowane z ukorzenionego drzewa osadzonego w płaszczyźnie poprzez dodanie otwierających i zamykających łodyg do wierzchołków. Liczba łodyg otwierających i zamykających musi się zgadzać. Niektórzy autorzy wymagają, aby kwitnące drzewa były ukorzenione i stawiają warunki, jakie mogą mieć łodygi. Terminy liście i kwiaty są czasami używane do otwierania i zamykania łodyg.
Związek z grafami planarnymi
Osadzony graf planarny można zbudować z kwitnącego drzewa, łącząc każdą otwierającą łodygę z zamykającą łodygą. Odwiedza się pół-krawędzie, przechodząc wokół wykresu zgodnie z ruchem wskazówek zegara, zaczynając od otwierającej łodygi. Jeśli drzewo jest zakorzenione, zwykle zaczyna się od korzenia. Algorytm jest analogiczny do dopasowywania nawiasów i używa stosu . każdym etapie, jeśli typ bieżącej połowy krawędzi sam, jak połowa krawędzi na szczycie stosu, wypychana na stos. Jeśli kolory się różnią, stos jest pęknięty, a dwie połówki krawędzi są połączone. Jeśli ustawimy dodane krawędzie od otwarcia do zamknięcia łodygi, nie mamy krawędzi przeciwnych do ruchu wskazówek zegara. Proces ten wymaga czasu liniowego.
Podobnie osadzanie ukorzenionego grafu planarnego można zakodować jako kwitnące drzewo. Jeśli pierwiastek znajduje się w rogu, można to zrobić w czasie liniowym. Krawędzie ukorzenionego grafu planarnego można zorientować tak, aby istniała ścieżka od korzenia do dowolnego wierzchołka, ale nie ma cykli przeciwnych do ruchu wskazówek zegara. W takim przypadku można użyć opartego na głębi , aby przekształcić go w kwitnące drzewo. Zaczynając od wierzchołka korzenia, spójrz na każdą incydentną z nim krawędź. Jeśli wskazuje od naszego obecnego wierzchołka, odetnij go, oznaczając zewnętrzną półkrawędź jako trzon zamykający, a wewnętrzną półkrawędź jako trzon otwierający. Jeśli wskazuje na nasz obecny wierzchołek, zaznacz go jako zachowany i ustaw jego drugi koniec jako nasz bieżący wierzchołek. Kontynuuj, aż wszystkie krawędzie zostaną uwzględnione. Jeśli mapa nie jest zakorzeniona w kącie, zbudowanie kwitnącego drzewa zajmuje kwadratowy czas.
Użyj w teorii węzłów
Drzewa kwiatowe są również używane do losowego generowania dużych diagramów węzłów . Węzły mogą być reprezentowane przez 4-regularne grafy planarne, w których każdy węzeł jest oznaczony jako przecięcie lub przecięcie. Drzewa kwiatowe mogą być używane do generowania losowych 4-regularnych grafów planarnych. Jednak nie zawsze dają one schematy węzłów, ponieważ może istnieć więcej niż jeden element. Można to sprawdzić w czasie sześciennym .