Subgrafo inducido

Gráfico creado a partir de un subconjunto de los nodos de otro gráfico y sus aristas

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.

Definición

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]}$ ${\displaystyle S}$ ${\displaystyle E}$ ${\displaystyle S}$ ${\displaystyle u,v\in S}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G[S]}$ ${\displaystyle 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]}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$

Ejemplos

Los tipos importantes de subgrafos inducidos incluyen los siguientes.

El problema de la serpiente en la caja se refiere a las trayectorias inducidas más largas en los gráficos de hipercubos.

• 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.

Cálculo

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]

Referencias

1. Diestel, Reinhard (2006), Teoría de grafos, Textos de posgrado en matemáticas, vol. 173, Springer-Verlag, págs. 3-4, ISBN 9783540261834.
2. Howorka, Edward (1977), "Una caracterización de los grafos hereditarios de distancia", The Quarterly Journal of Mathematics , Segunda serie, 28 (112): 417–420, doi :10.1093/qmath/28.4.417, MR  0485544.
3. Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte", Anales de Matemáticas , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, MR  2233847.
4. Johnson, David S. (1985), "La columna de completitud NP: una guía continua", Journal of Algorithms , 6 (3): 434–451, doi :10.1016/0196-6774(85)90012-4, MR  0800733.