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 todos los bordes que conectan pares de vértices en ese subconjunto.
Definición
Formalmente, deja ser cualquier gráfico, y dejar ser cualquier subconjunto de vértices de G . Entonces el subgrafo inducido es el gráfico cuyo conjunto de vértices es y cuyo conjunto de bordes consta de todos los bordes en que tienen ambos extremos en . [1] Es decir, para dos vértices cualesquiera, y son adyacentes en si y solo si son adyacentes en . La misma definición que funciona para grafos no dirigidos , gráficos dirigidos , e incluso multigrafos .
El subgrafo inducido también puede llamarse el subgrafo inducido en por , o (si el contexto hace la elección de inequívoco) el subgrafo inducido de .
Ejemplos de
Los tipos importantes de subgrafos inducidos incluyen los siguientes.
- Los caminos inducidos son subgrafos inducidos que son caminos . La ruta más corta entre dos vértices cualesquiera en un gráfico no ponderado es siempre una ruta inducida, porque cualquier borde adicional entre pares de vértices que podría hacer que no se induzca también haría que no sea más corta. Por el contrario, en los gráficos de distancia hereditaria , cada camino inducido es un camino más corto. [2]
- Los ciclos inducidos son subgrafos inducidos que son ciclos . La circunferencia de un gráfico se define por la longitud de su ciclo más corto, que siempre es un ciclo inducido. De acuerdo con el teorema del grafo perfecto fuerte , los ciclos inducidos y sus complementos juegan un papel crítico en la caracterización de grafos perfectos . [3]
- Las camarillas y los conjuntos independientes son subgráficos inducidos que son gráficos completos o gráficos sin bordes, respectivamente .
- 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 subgrafo inducido es una forma del problema de isomorfismo de subgrafo en el que el objetivo es probar si un grafo se puede encontrar como subgrafo inducido de otro. Debido a que incluye el problema de la camarilla como un caso especial, es NP-completo . [4]
Referencias
- ^ Diestel, Reinhard (2006), Teoría de grafos , Textos de posgrado en matemáticas, 173 , Springer-Verlag, págs. 3-4, ISBN 9783540261834.
- ^ Howorka, Edward (1977), "Una caracterización de gráficos hereditarios a distancia", The Quarterly Journal of Mathematics , Second Series, 28 (112): 417–420, doi : 10.1093 / qmath / 28.4.417 , MR 0485544.
- ^ Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del gráfico fuerte perfecto", Annals of Mathematics , 164 (1): 51-229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , MR 2233847.
- ^ 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.