Buenas, no entiendo la diferencia entre grafos inducidos y grafos recubridores.
En respuesta a Florencia Cosentino Gonzalez
Re: grafos inducidos y recubridores.
Según lo que entiendo la diferencia es que en un grafo recubridor se pueden tener aristas que no perteneces al grafo original, o pueden faltar aristas que estaban en el original. Además un grafo recubridor tiene que tener todos los vértices del grafo original pero en el inducido pueden faltar vértices.
Por ejemplo, si mi grafo original es G = (V, E) con V = {1, 2, 3, 4} y E = {{1, 2}, {2,3}, {3,4}}
un grafo recubridor G' = (V', E') es cualquiera en el que V' = V (sin importar E') Por lo que puedo tener E = {{1,2}, {2,4}}. Este grafo es recubridor pero no inducido porque la arista {2,4} no estaba en el grafo original y además la arista {2,3} no está en G' mientras que los vértices 2 y 3 sí están.
Un grafo G'' = (V'', E'') en el que V'' = {1, 2, 4} y E'' = {{1,2}} es inducido porque V'' está incluido en V y todas las aristas de E'' están en E y ninguna arista de E'' no está en E.
Si tuvieses G''' = (V''', E''') con V''' = {1, 2, 4} y E''' = {{2,4}} no sería ni recubridor (porque falta el vértice 3) ni inducido porque tiene la arista {2,4} que no está en el grafo original y le falta la arista {1,2} que sí está en el original.
Esto es a mi entender, puede haber algún error.
Por ejemplo, si mi grafo original es G = (V, E) con V = {1, 2, 3, 4} y E = {{1, 2}, {2,3}, {3,4}}
un grafo recubridor G' = (V', E') es cualquiera en el que V' = V (sin importar E') Por lo que puedo tener E = {{1,2}, {2,4}}. Este grafo es recubridor pero no inducido porque la arista {2,4} no estaba en el grafo original y además la arista {2,3} no está en G' mientras que los vértices 2 y 3 sí están.
Un grafo G'' = (V'', E'') en el que V'' = {1, 2, 4} y E'' = {{1,2}} es inducido porque V'' está incluido en V y todas las aristas de E'' están en E y ninguna arista de E'' no está en E.
Si tuvieses G''' = (V''', E''') con V''' = {1, 2, 4} y E''' = {{2,4}} no sería ni recubridor (porque falta el vértice 3) ni inducido porque tiene la arista {2,4} que no está en el grafo original y le falta la arista {1,2} que sí está en el original.
Esto es a mi entender, puede haber algún error.
Los conceptos propuestos aquí están esencialmente bien, solo que inducido y recubridor, en la mayor parte de la literatura se usa para SUBGRAFO. O sea, subgrafo inducido o subgrafo recubridor. Con lo cual algunos de los ejemplos de arriba no se ajustan al concepto de subgrafo. Solo ese detalle.
Saludos
Marcelo
Saludos
Marcelo