Ejercicio 11 Practico 9

Ejercicio 11 Practico 9

de Valentina Pereira Ciaffone -
Número de respuestas: 2

Buenas, tengo una duda de letra con la parte d:

d. Sean e1 y e2 las artistas fa; cg y fa; dg respectivamente del grafo G. Trace los siguientes subgrafos

de G: (i) (G - e1) - e2; (ii) (G - e2) - e1; (iii) G - (e1; e2)

Puede ser que los tres subgrafos sean enrealidad el mismo, porque en realidad estoy sacando las mismas dos aristas (en distinto orden).

Y tengo tambien dudas con las ultimas 3:

g. >Cuantos subgrafos recubridores tiene G?

h. >Cuantos de los subgrafos anteriores son conexos?

i. >cuantos subgrafos de la parte h. tienen el vertice a como vertice aislado?

Si estoy entendiendo bien la letra, la parte h me pide los grafos recubridores (que contengan todos los vertices de g) y a su vez conexos (que exista un camino simple que pase por todos los vertices), pero con las dos definiciones me da que no habria subgrafos que cumplan estas condiciones.

Por lo que la parte i tambien me daria 0, es mas la parte i  me daria 0 sin calcular las otras porque un grafo conexo no puede tenes al vertice a como aislado, a no ser que yo este interpretando mal la definicion.

Saludos!

En respuesta a Valentina Pereira Ciaffone

Re: Ejercicio 11 Practico 9

de Claudio Qureshi -

Hola Valentina.

d. Sean e1 y e2 las artistas fa; cg y fa; dg respectivamente del grafo G. Trace los siguientes subgrafos de G: (i) (G - e1) - e2; (ii) (G - e2) - e1; (iii) G - (e1; e2)

Puede ser que los tres subgrafos sean enrealidad el mismo, porque en realidad estoy sacando las mismas dos aristas (en distinto orden).

Si, son iguales. Es simplemente para verificar que entendieron la definición. 

Y tengo tambien dudas con las ultimas 3:

g. >Cuantos subgrafos recubridores tiene G?

h. >Cuantos de los subgrafos anteriores son conexos?

i. >cuantos subgrafos de la parte h. tienen el vertice a como vertice aislado?

Si estoy entendiendo bien la letra, la parte h me pide los grafos recubridores (que contengan todos los vertices de g) y a su vez conexos (que exista un camino simple que pase por todos los vertices), pero con las dos definiciones me da que no habria subgrafos que cumplan estas condiciones.

Si, por ejemplo el propio G es un subgrafo recubridor y conexo. También el subgrafo G-e donde e es la arista que conecta a y d. Hay otros dos.

Por lo que la parte i tambien me daria 0, es mas la parte i  me daria 0 sin calcular las otras porque un grafo conexo no puede tenes al vertice a como aislado, a no ser que yo este interpretando mal la definicion.

Exacto, el únco subgrafo conexo que contiene al vértice a como vértice aislado es el subgrafo que tiene a ese vértice como único vértice y no tiene arista. Pero ese grafo no es recubridor asi que la respuesta es 0.