k - wykres krawędziowy - k-edge-connected graph
W teorii wykres , podłączony wykres jest K -edge połączone jeśli pozostaje on połączony , gdy mniej niż k krawędzie są usuwane.
Krawędzi łączność z wykresu jest największa k , dla której wykres jest K -edge połączone.
Łączność krawędź i wyliczenie z k -edge połączone wykresach badano przez Camille Jordan w 1869 roku.
Formalna definicja
Niech będzie dowolnym wykresem. Jeśli subgraph podłączony jest dla wszystkich , gdzie , następnie G znaczy k -edge połączone. Łączność krawędzi jest maksymalną wartością k taką, że G jest k -połączone krawędziowo. Najmniejszy zbiór X, którego usunięcie odłącza G, jest minimalnym cięciem w G .
Wersja twierdzenia Mengera o łączności krawędzi zapewnia alternatywną i równoważną charakterystykę, pod względem ścieżek rozłącznych krawędzi w grafie. Wtedy i tylko wtedy, gdy na dwa wierzchołki z G tworzą punkty końcowe k ścieżki, na których nie ma dwóch podzielić krawędzi ze sobą, po czym G jest k -edge połączone. W jednym kierunku jest to łatwe: jeśli istnieje taki system ścieżek, to każdy zbiór X mający mniej niż k krawędzi jest rozłączny od co najmniej jednej ze ścieżek, a para wierzchołków pozostaje ze sobą połączona nawet po usunięciu X . W drugą stronę istnienie układu ścieżek dla każdej pary wierzchołków w grafie, których nie można rozłączyć przez usunięcie kilku krawędzi, można udowodnić za pomocą twierdzenia max-flow min-cut z teorii przepływów sieciowych .
Pojęcia pokrewne
Minimalny stopień wierzchołka daje trywialną górną granicę połączenia krawędzi. Oznacza to, że jeśli graf jest połączony krawędzią k , to konieczne jest, aby k ≤ δ( G ), gdzie δ( G ) jest minimalnym stopniem dowolnego wierzchołka v ∈ V . Oczywiście usunięcie wszystkich krawędzi przychodzących do wierzchołka v spowoduje odłączenie v od grafu.
Łączność krawędzi jest pojęciem dualnym do obwodu , długości najkrótszego cyklu w grafie, w tym sensie, że obwód grafu płaskiego jest połączeniem krawędzi jego podwójnego grafu i na odwrót. Koncepcje te są ujednolicone w teorii matroid przez obwód matroid , rozmiar najmniejszego zależnego zbioru w matroid. W przypadku matrycy graficznej obwód matroidu jest równy obwodowi grafu bazowego, podczas gdy w przypadku matrycy kograficznej jest równy łączności krawędzi.
Wykresy dwukrawędziowe mogą również charakteryzować się brakiem mostków , istnieniem rozkładu ucha lub twierdzeniem Robbinsa, zgodnie z którym są to dokładnie te grafy, które mają silną orientację .
Aspekty obliczeniowe
Algorytm jest wielomianem w czasie w celu określenia największego k , dla której wykres G jest k -edge połączone. Algorytm będzie prosta dla każdej pary (u, v) , określenia przepływu maksymalnego ze u do v o pojemności wszystkich krawędziach w G ustawione na 1 dla obu kierunków. Wykres jest połączony krawędziowo przez k wtedy i tylko wtedy, gdy maksymalny przepływ od u do v wynosi co najmniej k dla dowolnej pary (u,v) , więc k jest najmniejszym przepływem uv spośród wszystkich (u,v) .
Jeśli n jest liczbą wierzchołków grafu, ten prosty algorytm wykona iteracje problemu maksymalnego przepływu, który można rozwiązać w czasie. Stąd złożoność opisanego powyżej prostego algorytmu jest całkowita.
Ulepszony algorytm rozwiąże problem maksymalnego przepływu dla każdej pary (u,v), gdzie u jest arbitralnie ustalone, podczas gdy v zmienia się we wszystkich wierzchołkach. Zmniejsza to złożoność i jest rozsądne, ponieważ jeśli istnieje ograniczenie pojemności mniejsze niż k , to musi oddzielić u od jakiegoś innego wierzchołka. Można go dodatkowo ulepszyć algorytmem Gabowa, który działa w najgorszym przypadku .
Wariant Kargera-Steina algorytmu Kargera zapewnia szybszy algorytm randomizowany do określania łączności z oczekiwanym czasem działania .
Powiązany problem: znalezienie minimalnego podgrafu łączącego k krawędzią G (to znaczy: wybierz jak najmniej krawędzi w G, które są k -połączone krawędziowo) jest NP-trudne dla .
