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.[1] La misma definición se puede aplicar para grafos dirigidos, no dirigidos, e incluso para multigrafos.

Referencias
  1. Diestel, Reinhard (2006). Graph Theory. Graduate texts in mathematics 173. Springer-Verlag. pp. 3-4. ISBN 9783540261834.
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.