Subgrafo inducido
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Snake_in_the_box.svg/220px-Snake_in_the_box.svg.png)
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.
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
- ↑ Diestel, Reinhard (2006). Graph Theory. Graduate texts in mathematics 173. Springer-Verlag. pp. 3-4. ISBN 9783540261834.
Datos: Q24743362