Drzewo gąsienicowe
W teorii grafów gąsienica lub drzewo gąsienicowe to drzewo , w którym wszystkie wierzchołki znajdują się w odległości 1 od centralnej ścieżki .
Gąsienice zostały po raz pierwszy zbadane w serii artykułów Harary'ego i Schwenka. Nazwę zasugerował Arthur Hobbs . Jak Harary i Schwenk (1973) : „Gąsienica to drzewo, które przekształca się w ścieżkę, gdy usunie się z niego kokon punktów końcowych”.
Równoważne charakterystyki
Wszystkie poniższe charakterystyki opisują drzewa gąsienicowe:
- Są to drzewa, dla których usunięcie liści i przypadkowych krawędzi tworzy wykres ścieżki .
- Są to drzewa, w których istnieje ścieżka zawierająca każdy wierzchołek stopnia drugiego lub wyższego.
- Są to drzewa, w których każdy wierzchołek stopnia co najmniej trzeciego ma co najwyżej dwóch sąsiadów niebędących liśćmi.
- Są to drzewa, które nie zawierają jako podgrafu wykresu utworzonego przez zastąpienie każdej krawędzi grafu gwiazdy K 1,3 ścieżką o długości dwa.
- Są to połączone grafy, których wierzchołki można narysować na dwóch równoległych liniach, z krawędziami przedstawionymi jako nie przecinające się odcinki linii, które mają jeden punkt końcowy na każdej linii.
- Są to drzewa, których kwadrat jest grafem Hamiltona . Oznacza to, że w gąsienicy istnieje cykliczna sekwencja wszystkich wierzchołków, w której każda sąsiednia para wierzchołków w sekwencji znajduje się w odległości jednego lub dwóch od siebie, a drzewa, które nie są gąsienicami, nie mają takiej sekwencji. Cykl tego typu można uzyskać, rysując gąsienicę na dwóch równoległych liniach i łącząc sekwencję wierzchołków na jednej prostej z odwrotnością sekwencji na drugiej.
- Są to drzewa, których wykresy liniowe zawierają ścieżkę Hamiltona ; taką ścieżkę można uzyskać poprzez uporządkowanie krawędzi w dwuliniowym rysunku drzewa. Mówiąc bardziej ogólnie, liczba krawędzi, które należy dodać do wykresu liniowego dowolnego drzewa, aby zawierał on ścieżkę hamiltonowską (rozmiar jego dopełnienia hamiltonowskiego), jest równa minimalnej liczbie rozłącznych krawędziowo gąsienic, które krawędzie drzewa mogą rozkładać się na.
- Są to połączone grafy o szerokości ścieżki jeden.
- Są to połączone grafy przedziałów bez trójkątów .
- Są to grafy n-wierzchołków, których macierze sąsiedztwa można zapisać w taki sposób, że te z górnej trójkątnej części tworzą ścieżkę o długości n-1, rozpoczynającą się w prawym górnym rogu i biegnącą w dół lub w lewo.
Uogólnienia
K - drzewo jest grafem akordowym z dokładnie n − k maksymalnymi klikami , z których każda zawiera k + 1 wierzchołków; w k -drzewie, które samo w sobie nie jest ( k + 1)-kliką , każda maksymalna klika albo rozdziela graf na dwa lub więcej składowych, albo zawiera pojedynczy wierzchołek liścia, wierzchołek należący tylko do jednej maksymalnej kliki. K - ścieżka to k -drzewo z co najwyżej dwoma liśćmi, a k -gąsienica to k -drzewo, które można podzielić na k -ścieżkę i kilka k -liści, z których każdy przylega do separatora k -kliki k -ścieżka. W tej terminologii 1-gąsienica to to samo, co drzewo gąsienicowe, a k -gąsienice to grafy krawędziowo-maksymalne o szerokości ścieżki k .
homara to drzewo , w którym wszystkie wierzchołki znajdują się w odległości 2 od centralnej ścieżki .
Wyliczenie
Gąsienice stanowią jeden z rzadkich problemów z wyliczaniem grafów , dla których można podać dokładny wzór: gdy n ≥ 3, liczba gąsienic z n nieoznaczonymi wierzchołkami wynosi
Dla n = 1, 2, 3, ... liczba gąsienic n -wierzchołków wynosi
- 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (sekwencja A005418 w OEIS ) .
Złożoność obliczeniowa
Znalezienie rozpiętej gąsienicy na grafie jest NP-zupełne . Powiązanym problemem optymalizacji jest problem minimalnej gąsienicy (MSCP), w którym wykres ma podwójne koszty na swoich krawędziach, a celem jest znalezienie drzewa gąsienicy, które obejmuje graf wejściowy i ma najmniejszy całkowity koszt. Tutaj koszt gąsienicy jest zdefiniowany jako suma kosztów jej krawędzi, gdzie każda krawędź pobiera jeden z dwóch kosztów w zależności od jej roli jako krawędzi liścia lub wewnętrznej. Nie ma algorytmu aproksymacji f(n) dla MSCP, chyba że P = NP . Tutaj f ( n ) jest dowolną obliczalną funkcją n w czasie wielomianowym , liczbą wierzchołków wykresu.
Istnieje sparametryzowany algorytm, który znajduje optymalne rozwiązanie dla MSCP w grafach o ograniczonej szerokości drzewa . Tak więc zarówno Spanning Caterpillar Problem, jak i MSCP mają liniowe algorytmy czasu, jeśli graf jest grafem zewnętrznym, szeregowo-równoległym lub grafem Halina .
Aplikacje
Drzewa gąsienicowe były używane w teorii grafów chemicznych do przedstawiania struktury cząsteczek węglowodorów benzenoidowych . W tym przedstawieniu tworzy się gąsienicę, w której każda krawędź odpowiada sześciowęglowemu pierścieniowi w strukturze molekularnej, a dwie krawędzie schodzą się w wierzchołku, gdy odpowiednie pierścienie należą do sekwencji pierścieni połączonych końcami w Struktura. El-Basil (1987) pisze: „To zdumiewające, że prawie wszystkie grafy, które odegrały ważną rolę w tym, co obecnie nazywa się„ chemiczną teorią grafów ”, mogą być związane z drzewami gąsienicowymi”. W tym kontekście drzewa gąsienicowe są również znane jako drzewa benzenoidowe i drzewa Gutmana , po pracach Ivana Gutmana na tym obszarze.