Saltar al contenido

Diferencia entre un subgrafo y un subgrafo inducido.

Solución:

Un subgrafo $ H $ de $ G $ se llama INDUCIDO, si para dos vértices cualesquiera $ u, v $ en $ H $, $ u $ y $ v $ son adyacentes en $ H $ si y solo si son adyacentes en $ G $.

En otras palabras, $ H $ tiene las mismas aristas que $ G $ entre los vértices de $ H $.

Un subgrafo general puede tener menos aristas entre los mismos vértices que el original.

Entonces, un subgrafo inducido se puede construir eliminando vértices (y con ellos todos los bordes incidentes), pero no más bordes. Si se eliminan bordes adicionales, el subgrafo no se induce.

Para un gráfico original G (V, E), seleccione el conjunto de nodos V ‘de V. Todos los bordes existentes E’ que se conectan entre los nodos en V ‘deben permanecer.

Este subgrafo G ‘se denomina subgrafo inducido.

Si continúa eliminando algunos bordes de E ‘, entonces G’ sigue siendo un subgrafo de G, pero ya no es un subgrafo inducido de G.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *