Podwykres indukowany - Induced subgraph

W teorii wykres An wywołane subgraph wykresu inny wykres, utworzone z podzbioru wierzchołków grafu i wszystkich krawędzi (z oryginalnego wykresu), łączący pary wierzchołków tego podzbioru.

Definicja

Formalnie niech będzie dowolnym grafem i niech będzie dowolnym podzbiorem wierzchołków G . Następnie indukowany podgraf jest grafem, którego zbiór wierzchołków jest i którego zbiór krawędzi składa się ze wszystkich krawędzi w , które mają oba punkty końcowe w . Oznacza to, że dla dowolnych dwóch wierzchołków , a sąsiadują w wtedy i tylko wtedy, gdy są one w sąsiedztwie . Ta sama definicja pracuje undirected wykresy , graf skierowany , a nawet multigraphs . ${\ Displaystyle G = (V, E)}$${\ Displaystyle S \ podzbiór V}$${\displaystyle G[S]}$${\displaystyle S}$${\ Displaystyle E}$${\displaystyle S}$${\ Displaystyle u, v \ w S}$${\ Displaystyle u}$${\displaystyle v}$${\displaystyle G[S]}$${\ Displaystyle G}$

Indukowane subgraph może być również nazywany podgrafu indukowane w przez , lub (jeśli kontekst sprawia, że wybór jednoznaczne) indukowane podgrafu się . ${\displaystyle G[S]}$${\ Displaystyle G}$${\displaystyle S}$${\ Displaystyle G}$${\displaystyle S}$

Przykłady

Do ważnych typów podgrafów indukowanych należą:

Problem węża w pudełku dotyczy najdłuższych ścieżek indukowanych w grafach hipersześcianowych

• Ścieżki indukowane to indukowane podgrafy, które są ścieżkami . Najkrótsza ścieżka między dwoma wierzchołkami w nieważonej wykresie zawsze indukowane droga, ponieważ dodatkowe krawędzie między parami wierzchołków, które mogą spowodować, że nie są indukowane również spowodować, że nie jest najkrótsza. I odwrotnie, w grafach dziedzicznych na odległość każda indukowana ścieżka jest najkrótszą ścieżką.
• Cykle indukowane to indukowane podgrafy, które są cyklami . Obwód wykresu jest określona przez długość jego najkrótszego cyklu, co jest zawsze indukowane cyklu. Zgodnie z twierdzeniem o silnych grafach doskonałych , cykle indukowane i ich uzupełnienia odgrywają kluczową rolę w charakterystyce grafów doskonałych .
• Kliki i zbiory niezależne są indukowanymi podgrafami, które są odpowiednio kompletnymi grafami lub grafami bez krawędzi .
• Indukowane dopasowania to indukowane podgrafy, które są dopasowaniami .
• Okolica od wierzchołka jest indukowanego subgraph wszystkich wierzchołków przyległych do niego.

Obliczenie

Wywołane problemem subgraph Izomorfizm jest forma problemu subgraph izomorfizmu , w której celem jest, aby sprawdzić, czy jeden wykres można znaleźć jako wywołaną podgrafu drugiego. Ponieważ obejmuje problem kliki jako przypadek szczególny, jest on NP-zupełny .

Bibliografia