Moc wykresu
W teorii grafów , gałęzi matematyki, k -ta potęga G k grafu nieskierowanego G jest innym grafem, który ma ten sam zestaw wierzchołków , ale w którym dwa wierzchołki sąsiadują ze sobą, gdy ich odległość w G wynosi co najwyżej k . Potęgi grafów są określane przy użyciu terminologii podobnej do potęgowania liczb : G 2 nazywa się kwadratem G , G 3 nazywamy sześcianem G itd .
Potęgi grafów należy odróżnić od iloczynów samego grafu, które (w przeciwieństwie do potęg) generalnie mają o wiele więcej wierzchołków niż graf oryginalny.
Nieruchomości
Jeśli graf ma średnicę d , to jego d -ta potęga jest grafem pełnym . Jeśli rodzina grafów ma ograniczoną szerokość kliki , to jej d -te potęgi są również ograniczone dla dowolnego ustalonego d .
Kolorowanie
Kolorowanie wykresów na kwadracie wykresu może służyć do przydzielania częstotliwości uczestnikom bezprzewodowych sieci komunikacyjnych, tak aby żadni dwaj uczestnicy nie kolidowali ze sobą u żadnego ze wspólnych sąsiadów, oraz do znajdowania rysunków wykresów o wysokiej rozdzielczości kątowej .
Zarówno liczba chromatyczna, jak i degeneracja k - tej potęgi płaskiego wykresu maksymalnego stopnia Δ to O (Δ ⌊ k /2⌋ ) , gdzie granica degeneracji pokazuje, że do pokolorowania wykresu tym można zastosować algorytm zachłannego kolorowania wiele kolorów. W szczególnym przypadku kwadratu wykresu planarnego Wegner przypuszczał w 1977 r., Że liczba chromatyczna kwadratu wykresu planarnego wynosi co najwyżej max ( Δ + 5, 3 Δ / 2 + 1) , a wiadomo, że liczba chromatyczna wynosi co najwyżej 5Δ / 3 + O (1) . Mówiąc bardziej ogólnie, dla dowolnego wykresu o degeneracji d i maksymalnym stopniu Δ , degeneracja kwadratu wykresu wynosi O ( d Δ) , więc wiele typów rzadkich wykresów innych niż grafy planarne ma również kwadraty, których liczba chromatyczna jest proporcjonalna do Δ .
Chociaż liczba chromatyczna kwadratu grafu nieplanarnego o maksymalnym stopniu Δ może być proporcjonalna do Δ 2 w najgorszym przypadku, jest mniejsza dla grafów o dużym obwodzie , będąc w tym przypadku ograniczona przez O (Δ 2 / log Δ) .
Określenie minimalnej liczby kolorów potrzebnych do pokolorowania kwadratu grafu jest NP-trudne , nawet w przypadku planarnym.
hamiltonowość
Sześcian każdego spójnego wykresu koniecznie zawiera cykl Hamiltona . Niekoniecznie jest tak, że kwadrat połączonego wykresu jest hamiltonowski, a określenie, czy kwadrat jest hamiltonowski, jest NP-zupełne . Niemniej jednak, zgodnie z twierdzeniem Fleischnera , kwadrat grafu połączonego z dwoma wierzchołkami jest zawsze hamiltonowski.
Złożoność obliczeniowa
K - tą potęgę grafu o n wierzchołkach i m krawędzi można obliczyć w czasie O ( mn ) , przeprowadzając najpierw przeszukiwanie wszerz , zaczynając od każdego wierzchołka w celu określenia odległości do wszystkich pozostałych wierzchołków, lub nieco szybciej, stosując bardziej wyrafinowane algorytmy. Alternatywnie, jeśli A jest macierzą sąsiedztwa Ak dla wykresu, zmodyfikowaną tak, aby zawierała niezerowe wpisy na jego głównej przekątnej, to niezerowe wpisy dają macierz sąsiedztwa k potęgi wykresu, z czego wynika, że konstruowanie k potęg można wykonać w czasie mieszczącym się w logarytmicznym czynniku czasu mnożenia macierzy .
K - te potęgi drzew można rozpoznać w czasie liniowo w rozmiarze grafu wejściowego.
Biorąc pod uwagę graf, rozstrzygnięcie, czy jest on kwadratem innego grafu, jest NP-zupełne . Co więcej, NP-zupełnym jest ustalenie, czy graf jest k -tą potęgą innego grafu dla danej liczby k ≥ 2 , czy też jest k -tą potęgą grafu dwudzielnego , dla k > 2 .
Podgrafy indukowane
Półkwadrat grafu dwudzielnego G jest podgrafem G 2 indukowanym przez jedną stronę dwudzielnego podziału G . Wykresy mapy to półkwadraty grafów planarnych , a grafy sześcienne o połowę to półkwadraty grafów hipersześcianu .
Potęgi liści to podgrafy potęg drzew indukowanych przez liście drzewa. Potęga k -liść to potęga liścia, której wykładnikiem jest k .