Subgrafo inducido

En teoría de grafos , un subgrafo inducido de un grafo es otro grafo, formado a partir de un subconjunto de los vértices del grafo y todas las aristas del grafo original, que conectan pares de vértices en ese subconjunto.

Formalmente, dejemos${\displaystyle G=(V,E)}$Sea cualquier grafo, y sea${\displaystyle S\subseteq V}$Sea cualquier subconjunto de vértices de G. Entonces el subgrafo inducido${\displaystyle G[S]}$es el grafo cuyo conjunto de vértices es${\displaystyle S}$y cuyo conjunto de aristas consta de todas las aristas en${\displaystyle E}$que tienen ambos puntos finales en${\displaystyle S}$. ^{[ 1 ]} Es decir, para cualesquiera dos vértices${\displaystyle u,v\in S}$,${\displaystyle u}$y${\displaystyle v}$son adyacentes en${\displaystyle G[S]}$si y solo si son adyacentes en${\displaystyle G}$La misma definición funciona para grafos no dirigidos , grafos dirigidos e incluso multigrafos .

El subgrafo inducido${\displaystyle G[S]}$También puede llamarse el subgrafo inducido en${\displaystyle G}$por${\displaystyle S}$, o (si el contexto hace que la elección de${\displaystyle G}$inequívoco) el subgrafo inducido de${\displaystyle S}$.

Entre los tipos importantes de subgrafos inducidos se incluyen los siguientes.

• Los caminos inducidos son subgrafos inducidos que son caminos . El camino más corto entre dos vértices cualesquiera en un grafo no ponderado es siempre un camino inducido, porque cualquier arista adicional entre pares de vértices que pudiera hacer que no fuera inducido también haría que no fuera el más corto. Por el contrario, en los grafos hereditarios de distancia , todo camino inducido es un camino más corto. ^{[ 2 ]}
• Los ciclos inducidos son subgrafos inducidos que son ciclos . La circunferencia de un grafo se define por la longitud de su ciclo más corto, que siempre es un ciclo inducido. Según el teorema del grafo perfecto fuerte , los ciclos inducidos y sus complementos desempeñan un papel fundamental en la caracterización de los grafos perfectos . ^{[ 3 ]}
• Las camarillas y los conjuntos independientes son subgrafos inducidos que son, respectivamente, grafos completos o grafos sin aristas .
• Los emparejamientos inducidos son subgrafos inducidos que son emparejamientos .
• La vecindad de un vértice es el subgrafo inducido de todos los vértices adyacentes a él.

El problema del isomorfismo de subgrafos inducidos es una forma del problema del isomorfismo de subgrafos cuyo objetivo es comprobar si un grafo puede encontrarse como subgrafo inducido de otro. Dado que incluye el problema de la camarilla como caso particular, es NP-completo . ^{[ 4 ]}