Subgrafos

.1.3. Subgrafos

Un subgrafo de G = (V, A) es otro grafo H = (V’, A’) tal que V’  V y A’  A. Si V’ = V, se dice que H es un subgrafo generador.

El subgrafo inducido por un subconjunto de vértices W  V es el grafo cuyo conjunto de vértices es W y cuyas aristas son todas las de G cuyos extremos están en W.

En la siguiente figura se muestra:

• un grafo G

• un subgrafo G1 de G inducido por el subconjunto de vértices {a, b, c, e}

• un subgrafo generador G2 de G

Figura 3: Un grafo G y dos subgrafos G1 y G2 de G

Si x es un vértice del grafo G = (V, A), se indica por G – {x}, o simplemente G – x, al subgrafo de G que tiene como conjunto de vértices V – {x} y como aristas todas las de G menos las incidentes con x.

Si e es una arista de G = (V, A), se indica por G – {e}, o simplemente G – e, al subgrafo de G que tiene como conjunto de vértices V y A – {e} como conjunto de aristas.

En la siguiente figura se muestra:

• un grafo G

• el subgrafo G – e, donde e es un vértice de G

• el subgrafo G – be, donde be es una arista de G

En el caso de G – e se puede observar que, al haberse eliminado el vértice e, también se han eliminado las aristas be, de y df.

Figura 4: El resultado de eliminar un vértice o una arista

Aclararemos además, para que se entiendan más fácilmente algunos algoritmos que veremos más adelante, que:

• si x es un vértice del grafo G = (V, A) y H = (V’, A’) es un subgrafo de G tal que x  V’, se indica por H + {x}, o simplemente H + x, al subgrafo de G que tiene como conjunto de vértices V’ + {x} y A’ como conjunto de aristas

• si e = uv es una arista de G = (V, A) y H = (V’, A’) es un subgrafo de G tal que e  A’, se indica por H + {e}, o simplemente H + e, al subgrafo de G que tiene como conjunto de vértices V’  {u, v} y A’ + {e} como conjunto de aristas

...