Bramble (teoria grafów) - Bramble (graph theory)

Jeżyna rzędu czwartego w grafie siatkowym 3×3, składająca się z sześciu wzajemnie stykających się połączonych podgrafów

Teoretycznie na wykresie, jeżyny na nieukierunkowane grafu G to rodzina związanych subgraphs z G , że wszystkie stykają się ze sobą: dla każdej pary subgraphs rozłączne, musi istnieć przewagę w G , która ma jeden koniec w każdym podgrafu. Zamówienie z ostu jest najmniejszy rozmiar zestawu uderzania , zbiór wierzchołków G , który ma niepusty przecięcia z każdą z subgraphs. Jeżyny mogą być stosowane do scharakteryzowania treewidth o G .

Szerokość drzewa i schronienia

Haven z rzędu k, na wykresie G jest funkcją β który mapuje każdy zestaw X o mniej niż k wierzchołków do przyłączonego składnika G  -  X , w taki sposób, że każde dwa podzbiory p ( x ) i β ( Y ) dotykowy wzajemnie. Tak więc zbiór obrazów β tworzy w G jeżynę o porządku k . I odwrotnie, każda jeżyna może być użyta do określenia schronienia: dla każdego zbioru X o rozmiarze mniejszym niż rząd jeżyny, istnieje unikalny połączony składnik β ( X ), który zawiera wszystkie podgrafy w jeżynie, które są rozłączne od X .

Jak pokazali Seymour i Thomas, kolejność jeżyny (lub równoważnie raju ) charakteryzuje szerokość drzewa : graf ma jeżynę rzędu k wtedy i tylko wtedy, gdy ma szerokość drzewa co najmniej k − 1 .

Rozmiar jeżyn

Grafy ekspandera o ograniczonym stopniu mają szerokość drzewa proporcjonalną do ich liczby wierzchołków, a zatem mają również jeżyny o liniowym porządku. Jednakże, jak pokazali Martin Grohe i Dániel Marx, w przypadku tych grafów jeżyna tak wysokiego rzędu musi zawierać wykładniczo wiele zbiorów. Silniej, w przypadku tych grafów, nawet jeżyny, których rząd jest nieco większy niż pierwiastek kwadratowy szerokości drzewa, muszą mieć rozmiar wykładniczy. Grohe i Marks wykazali jednak również, że każdy wykres szerokości drzewa k ma jeżynę o wielkości wielomianu i porządku . ${\ Displaystyle \ Omega (k ^ {1/2} / \ log ^ {2} k)}$

Złożoność obliczeniowa

Ponieważ jeżyny mogą mieć rozmiar wykładniczy, nie zawsze jest możliwe skonstruowanie ich w czasie wielomianowym dla grafów o nieograniczonej szerokości drzewa. Jednak gdy szerokość drzewa jest ograniczona, możliwa jest wielomianowa konstrukcja czasu: można znaleźć jeżynę rzędu k , jeśli taka istnieje, w czasie O( n ^{k  + 2} ) gdzie n jest liczbą wierzchołków danego grafu . Jeszcze szybsze algorytmy są możliwe dla grafów z kilkoma minimalnymi separatorami.

Bodlaender, Grigoriev i Koster studiowali heurystykę wyszukiwania jeżyn wysokiego rzędu. Ich metody nie zawsze generują jeżyny rzędu bliskie szerokości drzewa grafu wejściowego, ale dla grafów planarnych dają stały współczynnik aproksymacji . Kreutzer i Tazari dostarczają algorytmów randomizowanych, które na grafach szerokości drzewa k znajdują jeżyny o wielkości wielomianu i porządku w czasie wielomianu, mieszczące się w logarytmicznym czynniku porządku wykazanego przez Grohe i Marksa (2009), który istnieje dla jeżyn o rozmiarze wielomianowym. ${\ Displaystyle \ Omega (k ^ {1/2} / \ log ^ {3}k)}$

Skierowane jeżyny

Pojęcie jeżyny zostało również zdefiniowane dla grafów skierowanych. W skierowanym wykresie D , A jeżyny jest zbiorem silnie związane subgraphs z D , że wszystkie stykają się ze sobą: na każdą parę rozłącznych elementów X , Y z ostu, musi istnieć kątowych D od X do Y i jeden z Y do X . Zamówienie z ostu jest najmniejszy rozmiar zestawu uderzania , zbiór wierzchołków D , który ma niepusty przecięcie ze sobą elementów z ostu. Liczba jeżyny w D to maksymalny rząd jeżyny w D . Liczba jeżyn grafu skierowanego mieści się w stałym współczynniku jego szerokości drzewa skierowanego.

Bibliografia