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

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

Los tipos importantes de subgrafos inducidos 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 se indujera también haría que no fuera el más corto. Por el contrario, en los grafos hereditarios de distancia , cada 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 de isomorfismo de subgrafos inducidos es una forma del problema de isomorfismo de subgrafos en el que el objetivo es comprobar si un grafo puede encontrarse como un subgrafo inducido de otro. Como incluye el problema de la camarilla como un caso especial, es NP-completo . ^[4]