Listado de Ejercicios Nº2

de Grafos Y Algoritmos
Bienvenidos a Grafos y Algoritmos

 

PROBLEMA Nº1. Responder cada pregunta (5 Puntos cada una), con V(verdadero) o F(falso). Si es F entonces justificar en una línea.

      1. En el siguiente grafo es posible encontrar un ciclo Euleriano.

        2.  

         

      2. Si un grafo posee mas de dos vértices impares, no es un ciclo Euleriano.

        3.  

      3. Un ciclo Euleriano es un camino continuo que pasa por cada arista una y sólo una vez.

        4.  

      4. Los 2 grafos siguientes no poseen ciclo Euleriano.

        5.   

      5. K1 es un grafo completo.

        6.  

      6. La siguiente figura corresponde a una floresta.

        7.  

         

         

      7. En los siguientes grafos los vértices tipo c tienen grado 1.

        8.  

          

      8. La siguiente figura corresponde a un árbol.

 

 

Problema Nº 2 (10 puntos)

Para el grafo de la figura, se pide: i) Encontrar dos conjuntos independientes de vértices. ii) Encontrar un conjunto de vértices maximal.

 

  

 

 

Problema Nº 3 (10 puntos) En el siguiente grafo, determine y responda: i) El Nº de aristas. Ii) Si el grafo fuera dirigido existiría un camino hamiltoneano?.

 

 Problema Nº4 (10 puntos)

Para cada uno de los grafos presentados a continuación determine el número cromático.

 

Problema Nº5 (10 puntos)

En los árboles que a continuación se presentan responda: i) nivel de cada vértice, a) altura del árbol y iii) todos los descendientes del vértice b.

 

Problema N° 6 (20 puntos)

Considerando la Búsqueda en Profundidad y Anchura, "bosqueje" una solución para el problema que tiene un vendedor, que debe recorrer varias ciudades (saliendo y regresando a su ciudad) y pasando exactamente una sola vez por cada una.

En el siguiente grafo aparecen las ciudades y costos de aristas que debe encontrar el vendedor.

Obviamente el vendedor esta interesado en la ruta de mínimo costo.

 

 
Bienvenidos a Grafos y Algoritmos
 
Menú Principal