Grafos (2017)

Apunte Español
Universidad Universidad Complutense de Madrid (UCM)
Grado Matemáticas y Estadística - 1º curso
Asignatura Elementos
Año del apunte 2017
Páginas 8
Fecha de subida 15/07/2017
Descargas 0
Subido por

Descripción

ejercicios resueltos de grafos

Vista previa del texto

Ejercicios de Grafos (Lección 5) 1) Sea G  V , A  un grafo de orden n .
1.- ¿Cuál es el mínimo número de aristas de G si tiene dos componentes conexas? 2.- Si G tuviese m componentes conexas, ¿cuál sería el mínimo número de aristas de G en función de m ? Solución: Si V  n , el número mínimo de aristas necesarias para que G sea simple y conexo es A  n  1 (esto es, G es un árbol).
1.- Para que G tenga dos componentes conexas basta con eliminar una arista, es decir, n  2 es el número mínimo de aristas.
2.- Razonando como en el caso anterior, si m son las componentes conexas de G , el número de aristas mínimo es A  n  1   m  1  n  m .
2) Sea G  V , A  un grafo de orden 10 y sea T un árbol generador de G .
Sabiendo que T tiene p vértices de grado 3 y q hojas, calcula p y q .
Solución: Sabiendo que el conjunto de vértices de T es el conjunto de vértices de G , aplicando el Lema del Apretón de Manos se obtiene que p  4 y q  6 3) Dibuja dos árboles generadores para cada uno de los grafos siguientes Solución: 1 Apuntes descargados de wuolah.com 4) 1.- Dar un ejemplo de un árbol con 7 vértices y a) exactamente 2 vértices de grado 1 b) exactamente 4 vértices de grado 1 c) exactamente 6 vértices de grado 1 2.- Usar el Lema del Apretón de Manos para probar que todo árbol con n vértices, con n  2 , tiene al menos dos hojas.
Solución: 1.- 2.- Sea T un árbol con n vértices y como máximo un vértice de grado 1. Entonces debe tener n  1 vértices de grado mayor o igual que 2. La suma de los grados de los vértices es como mínimo 2  n  1  1 pero por el Lema del Apretón de Manos el número de aristas es mayor o igual que  n  1  1 lo que contradice que T tenga 2 exactamente n  1 aristas, luego hay como mínimo 2 vértices de grado 1.
5) Usar los dos métodos estudiados para obtener un árbol generador de K 5 Solución: 6) Obtener tres árboles generadores del grafo de Petersen 2 Solución: 7) Aplicar el algoritmo DFS, búsqueda en profundidad, para encontrar un árbol generador del grafo G Solución: Partiendo del vértice i , se construye el camino con la longitud mayor, representado en G1 Se retrocede al origen de la última arista e, f  , vértice e , y partiendo de ese origen se construye el camino más largo posible, el e, h (ver grafo G2 ) 3 Se retrocede de nuevo al vértice e y desde él al b y así sucesivamente hasta el g , pasando por todos los d , a y c , todos los cuales ya han sido visitados.
Desde a no puede volverse a b por la arista a, b porque este último vértice ya fue visitado. Al llegar al g , será necesario visitar el vértice j , con lo que quedará formado el árbol maximal pedido.
Árbol máximal de G 8) Aplicar el procedimiento BFS , búsqueda por anchura, para encontrar un árbol generador en el grafo G .
Solución: Elegido un vértice cualquiera, el a , se visitan todos sus adyacentes que, en orden léxicográfico, son b , f y g  G1  . Se selecciona uno por uno esos tres visitados y se toma cada uno de ellos como inicial para repetir el proceso de visitar sus adyacentes. Se toma primero el b , luego el f y por último el g .
Se llegará  G2  , respectivamente, a los c, e, h, l y m . Por último, partiendo del c se visitarán i y d  G3  .
Desde el vértice c se visitarán d e i ; desde el e , el k ; desde los h, l , m ya no podrá visitarse ningún vértice adyacente porque todos ellos ya han sido visitados; desde el i se visitará el j  G4  T  4 9) Representar los siguientes grafos y aplicar el método de búsqueda en profundidad  DFS  a cada uno de los siguientes grafos, definidos por sus listas de adyacencias, para obtener un árbol generador de cada una de sus componentes.
a b d h b a c d e c b d g d a b c G1 e b f g g c f h h a g a e i b d g h c e f i d b g h G2 e a c f f c e i g b d h b d i a c f G3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 0 1 11 0 11 0 1 10 9 4 1 0 4 5 8 5 12 14 2 14 5 12 12 6 3 2 6 7 13 7 13 14 9 5 11 13 10 7 Solución: Grafo G1 5 Empezamos la búsqueda en el vértice a . Desde él se alcanza b . Partiendo de b , se alcanza c y desde éste, d . Así los primeros pasos en la búsqueda son: Al considerar d como vértice de partida, todos sus vecinos ya han sido visitados por lo que se retrocede al vértice anterior c y se mira en su lista de adyacencia si queda algún vecino por alcanzar. Así es, es el vértice g , que pasa a ser el inicial. Desde g se alcanza f , que de nuevo no tiene vecinos que visitar. Se retrocede al vértice anterior g y se mira si todos sus vecinos han sido visitados. Falta por marca h que se convierte en vértice de partida. Los pasos descritos en este párrafo son: Como h tiene todos los vecinos visitados, retrocedemos en el árbol hasta encontrar un vértice con vecinos no visitados o marcados. En b sí tenemos un vecino sin marcar, que es el vértice e . Así obtenemos el árbol de búsqueda Como se han alcanzado todos los vértices el proceso ha terminado.
6 Grafo G2 Empezando en el vértice a accedemos a los vértices e, c, f , i sucesivamente, obteniendo el árbol de búsqueda Ninguno de estos vértices tiene vecinos no marcados o visitados, lo que significa que el grafo G2 no es conexo. La búsqueda en profundidad continúa eligiendo un vértice nuevo b , y siguiendo con el proceso. Desde b se alcanza d y desde éste el vértice g . Ahí se debe retroceder a d pues g tiene ya todos los vértices marcados. Desde d se alcanza h con lo que quedan marcados todos los vértices. El resultado de la búsqueda es ahora un bosque con dos árboles que corresponden a las dos componentes conexas de G2 Grafo G3 Con la búsqueda en profundidad detectamos que G3 tiene 3 componentes conexas.
Los árboles que resultan del proceso son 7 10) Cuestiones Señala en cada caso la respuesta correcta: 1.- Sea G  V , A  un grafo simple y conexo con V  5 y A  4 . ¿Es G un árbol?  No  Sí 2.- Sean G1  V1 , A1  y G2  V2 , A2  dos grafos tales que V1  V2   6y consideremos el grafo G obtenido a partir de G1 y G2 añadiendo las aristas v1, v2  y w1, w2 siendo v1, w1 V1 y v2 , w2 V2 . Si G G1 y G2 ?  No necesariamente  es un árbol, ¿lo son Sí, siempre 3.- Sea G un grafo simple y conexo. Entonces:  G  G  G admite sólo un árbol generador admite puede no admitir árboles generadores admite al menos un árbol generador Solución: 1.- Sí 2.- No necesariamente 3.- G admite al menos un árbol generador 8 ...

Tags:
Comprar Previsualizar