Osłona krawędzi - Edge cover
W teorii wykres An pokrywa krawędź z wykresu jest zestaw krawędzi tak, że każdy wierzchołek wykresu pada na co najmniej jednej krawędzi zestawu. W informatyce , minimalna pokrywa krawędź problemem jest problem ze znalezieniem osłonę krawędzi minimalnej wielkości. Jest to problem optymalizacyjny, który należy do klasy problemów pokrywających i można go rozwiązać w czasie wielomianowym .
Definicja
Formalnie osłonę krawędzi grafu G jest zestaw krawędzi C tak, że każdy wierzchołek w G padającego z co najmniej jednej krawędzi, C . Zestaw C, mówi się, że pokrycie wierzchołki G . Poniższy rysunek przedstawia przykłady pokrycia krawędzi na dwóch wykresach.
Obejmujących co najmniej krawędź jest krawędzią pokrycia możliwie najmniejszej wielkości. Liczba krawędzi pokrycia jest mniejsza od minimalnej pokrycie krawędzi. Poniższy rysunek przedstawia przykłady minimalnego pokrycia krawędzi.
Zwróć uwagę, że rysunek po prawej stronie to nie tylko okładka krawędzi, ale także dopasowanie . W szczególności, jest to doskonałe dopasowanie : Dopasowanie M , w którym każdy wierzchołek jest zbieżna się dokładnie na jednej krawędzi w M . Idealne dopasowanie (jeśli istnieje) to zawsze minimalne pokrycie krawędzi.
Przykłady
- Zbiór wszystkich krawędzi to otulina krawędzi, przy założeniu, że nie ma wierzchołków 0 stopni.
- Zakończeniu wykres dwudzielny K m , n ma krawędź obejmującą maksymalna liczba ( m , n ).
Algorytmy
Najmniejsze pokrycie krawędzi można znaleźć w czasie wielomianowym , znajdując maksymalne dopasowanie i łapczywie rozszerzając je tak, aby pokryć wszystkie wierzchołki. Na poniższym rysunku maksymalne dopasowanie zaznaczono na czerwono; dodatkowe krawędzie, które zostały dodane w celu zakrycia niedopasowanych węzłów, są zaznaczone na niebiesko. (Rysunek po prawej stronie pokazuje wykres, na którym maksymalne dopasowanie jest idealnym dopasowaniem ; dlatego obejmuje już wszystkie wierzchołki i nie były potrzebne żadne dodatkowe krawędzie).
Z drugiej strony powiązany problem znalezienia najmniejszej otuliny wierzchołka jest problemem NP-trudnym .
Zobacz też
- Osłona wierzchołka
- Zbiór otuliny - problem otuliny krawędzi jest szczególnym przypadkiem problemu zadanej otuliny: elementy wszechświata są wierzchołkami, a każdy podzbiór obejmuje dokładnie dwa elementy.