Ejercicios de grafos

´ DEPARTAMENTO DE CIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL Curso 2007/2008 ´ MATEMATICA DISCRETA Bloque 1 ´ INTRODUCCION A LA TEOR´ DE IA GRAFOS Problemas

Lecci´n 1. Grafos: Fundamentos. o 1 Plantea dos situaciones reales en las que se vea la utilidad de un grafo dirigido y no dirigido respectivamente. Dibuja tales grafos y estudia los conceptos de incidencia y adyacencia. 2 Daejemplos, distintos de los vistos en clase, de grafo simple, multigrafo, grafo bipartido, grafo bipartido completo, tanto para el caso dirigido como no dirigido. Calcula para dichos ejemplos el grado de cada v´rtice y comprueba que se cumple el teorema que aparece en el e apartado 3. 3 Da ejemplos de grafos con v´rtices x, y, z que cumplan las siguientes propiedades: e 1. Hay un ciclo que utiliza losv´rtices x e y. e 2. Hay un ciclo que utiliza los v´rtices y y z. e 3. Ning´n ciclo utiliza los v´rtices x y z. u e 4 Un sistema de carreteras comunica siete pueblos a, b, c, d, e, f, g como sigue: a1 comunica a y c pasando por b. a2 comunica c y d y despu´s pasa por b hasta llegar a f . e a3 comunica d y a pasando por e. a4 comunica f y b pasando por g. a5 comunica g y d. (a) Utilizando v´rticespara representar los pueblos y arcos, para los tramos de carretera que e los unen, dibuja un grafo dirigido que ilustre la situaci´n. o (b) Obt´n el grado de entrada y salida de cada v´rtice. e e 1

(c) L´ los caminos de g a a. ısta (d) ¿Cu´l es el menor n´mero de tramos de carretera que tendr´ que cerrarse para interruma u ıan pir el paso de b a d? (e) ¿Es posible salir de c y regresar a ´lvisitando una s´la vez los dem´s? e o a 5 Consid´rese el grafo de la figura e

1. ¿Cu´les de las siguientes sucesiones de v´rtices describen caminos: a e stuvwxyz; tvwzyx; stus; tuss; vwvwvwv; wvustvw. 2. ¿Cu´les son cadenas cerradas y cu´les ciclos? a a 3. Obt´n en este grafo los caminos de menor longitud que conecten los siguientes pares de e v´rtices, dando la longitud. e s, v; s, z; u, y; v, w.6 Consid´rese el grafo de la figura e

1. Obt´n un subgrafo generador. ¿Es unico? e ´ 2. Da ejemplos de cadena no simple y que no sea camino. 3. Da ejemplos de cadena simple. 4. Da ejemplos de cadena cerrada. 5. Da ejemplos de ciclos. 6. ¿El grafo es conexo? ¿Por qu´? e 2

7 Escribe la matriz de adyacencia, la matriz de incidencia y la tabla de incidencia correspondiente para los siguientesgrafos:

8 Responde a las siguientes cuestiones: (i) Sea G un grafo con matriz de adyacencia A. Con qu´ se correspone de el elemento (i, j) de la matriz Ar , r ≥ 1. (ii) Sea G un grafo no dirigido. Con qu´ se corresponde la suma de los e elementos de cada fila de la matriz de incidencia.

(iii) Sea G un grafo no dirigido. A qu´ es e igual la suma de los elementos de cada columna de la matriz deincidencia. (iv) Sea G un grafo dirigido sin bucles. A qu´ es igual la suma de los elemene tos de cada columna de la matriz de incidencia.

Lecci´n 2. Accesibilidad y Conectividad. o 9 Calcula las matrices de accesibilidad y acceso del grafo del problema 4. Obt´n las compoe nentes conexas mediante los dos m´todos conocidos. e 10 Obt´n las componentes conexas de los grafos del problema 7. e 11Consideremos los siguientes grafos

(a) Describe un camino euleriano para estos grafos o explica por qu´ no hay uno. e 3

(b) Describe un tour euleriano para estos grafos o explica por qu´ no hay uno. e 12 ¿Es posible para un insecto caminar por las aristas de un cubo, de manera que pase por cada arista exactamente una vez? Expl´ ıquese. 13 Construye un grafo con conjunto de v´rtices {0, 1}3 ycon una arista entre los v´rtices v y e e w si v y w difieren en exactamente dos coordenadas. (a) ¿Cu´ntas componentes conexas tiene el grafo? a (b) ¿Cu´ntos v´rtices de cada grado tiene el grafo? a e (c) ¿Tiene el grafo un tour euleriano? 14 Construye un grafo dirigido con m´s de 10 v´rtices en el que de (v) = ds (v) para todo a e v´rtice v. ¿Es euleriano? Utiliza la modificaci´n del algoritmo de...