Subgrafo inducido

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
A partir del conjunto de vértices {000, 001, 011, 111 y 110}, es posible construir el subgrafo inducido destacado en azul.

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[editar]

Formalmente, sea G=(V, E) un grafo y SV 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[editar]

  1. Diestel, Reinhard (2006). Graph Theory. Graduate texts in mathematics 173. Springer-Verlag. pp. 3-4. ISBN 9783540261834.