Subgrafo inducido

En teoría de grafos, un subgrafo inducido de un grafo es otro grafo, conformado a partir de un subconjunto de vértices y de todas las aristas incidentes a pares de vértices de dicho conjunto.

A partir del conjunto de vértices {000, 001, 011, 111 y 110}, es posible construir el subgrafo inducido destacado en azul.

Definición

Formalmente, sea G=(V, E) un grafo y S⊂V un subconjunto de vértices de G. El subgrafo inducido en G por S, denotado G[S], es el grafo cuyo conjunto de vértices es S y cuyo conjunto de aristas son todas las aristas en E que inciden por ambos lados en vértices de S.​ La misma definición se puede aplicar para grafos dirigidos, no dirigidos, e incluso para multigrafos.

Referencias

• Datos: Q24743362