Guía. Matemática Discreta y Autómatas

Guías (2013)

Matemática Discreta y Autómatas

Trabajo práctico 1: Grafos.

Objetivos:

• Adquirir el vocabulario pertinente a teoría de grafos y grafos dirigidos.
• Representar grafos gráficamente y con las matrices de adyacencia y de incidencia.
• Comprender el concepto de árbol y su utilidad para estudiar grafos.
• Adquirir algunas nociones de la complejidad de los algoritmos de ordenación.
• Conocer aplicaciones de grafos ponderados y los algoritmos para resolver los problemas de camino más corto y árboles recubridores minimales.

1.  Para cada uno de los grafos de la figura, indicar:

a. el grado de cada vértice. Verificar la fórmula que relaciona los grados de vértices con el número de aristas.

b. identificar los bucles (si existen)

c. un ciclo en el grafo

d. un camino de a a c de longitud 3, si existe 

e. un ciclo que contenga a g, de longitud par, si existe.

f. los vértices conectados con e

g. todos los caminos simples de e a g.

h. la distancia entre b y cada uno de los vértices

[pic 2]

[pic 3]

1.  ¿Cuántas componentes conexas tienen los grafos G1, G2 y G3? ¿Cuál es el número máximo de aristas que pueden eliminarse de cada uno, manteniendo el número de componentes conexas?
2. a. Escribir la matriz de incidencia de los grafos G1, G2 y G3.

b. Escribir la matriz de adyacencia de los grafos G1, G2 y G3.

1.  Un n-cubo es un grafo en el que los vértices se etiquetan con n-uplas de ceros y unos. Una arista conecta dos vértices u y v si las etiquetas de u y v difieren exactamente en un símbolo.

a. Construir el 2-cubo.

b. Construir el 3-cubo

c. ¿Es conexo el n-cubo? Justificar.

d. Calcular el número de vértices y de aristas del n-cubo.

1. Dada una colección de conjuntos, el grafo de intersección  se define como el que tiene un vértice por cada conjunto, y una arista entre dos vértices que representan conjuntos de intersección no vacía. Representar el grafo de intersección de los conjuntos.

1. A1 = {0,1,2,3,4,5}; A2 = {10, 11, 12}; A3 = {1, 5, 10, 15, 20}; A4 = {3, 12, 19}; A5 = {0, 10, 20, 30, 40}; A6 = N = {números naturales}
2. B1 = {n∈N: n es divisor de 4 mayor que 1} = {2, 4};  B2 = {n∈N: n es divisor de 6 mayor que 1} = {2, 3, 6}; B3 = {n∈N: n es divisor de 11 mayor que 1} = {11}; B4 = {n∈N: n es divisor de 9 mayor que 1} = {3, 9};
3. C1 = {n∈N: n es múltiplo de 4} = {4, 8, 12, ...};  C2 = {n∈N: n es múltiplo de 6} = {6, 12, 18, ...}; C3 = {n∈N: n es múltiplo de 11} = {11, 22, 33, ...}; C4 = {n∈N: n es múltiplo de 9} = {9, 18, 27, ...};

1. Para los siguientes grafos dirigidos, indicar:

a. el grado de entrada y de salida de cada vértice. Verificar la fórmula que relaciona los grados de entrada y salida con el número de aristas.

b. un camino dirigido de e a a, si existe

c. un ciclo dirigido, si existe

[pic 4]

1.  a. Escribir la matriz de incidencia de los digrafos G4 y G5.

b. Escribir la matriz de adyacencia de los digrafos G4 y G5.

1.  Dada una lista de sentencias a ejecutar por un programa, un grafo de precedencias es el grafo dirigido donde cada vértice representa una sentencia, y tiene un arco del vértice i al vértice j si la ejecución de j necesariamente debe realizarse después de la sentencia i (porque j depende del resultado de i, o porque j modifica una variable que se usa antes en i). Representar el grafo dirigido correspondiente a cada una de las listas de sentencias:

¿Puede hallarse un camino cerrado dirigido en los grafos hallados? Justificar la respuesta.

1. Dado el grafo de rutas aéreas G6

[pic 5]

a. Dar el número de caminos con 3 tramos entre Buenos Aires y Tucumán.

b. ¿Hay algún ciclo de longitud 4 que incluya a Buenos Aires?

c. ¿Hay algún ciclo que incluya a Mendoza y Corrientes? ¿En caso afirmativo, dé la longitud de cada ciclo hallado.

d. Dé un circuito que incluya Mendoza y Corrientes de longitud 6.

e. ¿Qué representa el grado de cada nodo?

f. ¿G6 tiene algún punto de articulación?

g. ¿G6 tiene alguna arista de corte?

1. Indicar si existe un grafo regular con las siguientes características (dar un ejemplo o justificar la no existencia):

a. 7 vértices y 7 aristas

b. 7 vértices y 16 aristas

c. 3 vértices, 6 aristas, sin lazos

d. 4 vértices, 6 aristas, sin lazos

1. Indicar para qué valores de n es regular:

1. el grafo completo Kn
2. el ciclo de n vértices, Cn
3. la rueda de n+1 vértices, Wn
4. la estrella con n+1 vértices, Sn
5. el n-cubo
6. el grafo lineal Ln

1. Hallar la matriz de adyacencia de los grafos: K6 , C6, W5, S5 , L6.
2. Describir las matrices de adyacencia de Kn , Cn, Wn, Sn , Ln dando el valor de cada componente aij en función de i, j y n..
3. Si A es la matriz de adyacencia de un grafo, Ak es una matriz cuyo elemento (i,j) es el número de caminos de longitud k que hay en el grafo entre los vértices i y j. ¿Cómo se puede usar este resultado para probar si un grafo es conexo?
4. En la figura se muestra el trazado de un barrio (los espacios en blanco indican calles, los grises propiedad privada). El cartero debe repartir correspondencia, pasando por todas las calles del barrio. ¿Es posible hacerlo pasando una y sólo una vez por cada cuadra? Dar el recorrido en caso afirmativo, o justificar en caso negativo.

[pic 6]

1.  Suponga que en el barrio anterior se pueden construir nuevas calles públicas (expropiando terrenos, si fuera necesario). ¿Cuál es la mínima cantidad de calles nuevas necesarias para que el cartero pueda recorrer el barrio pasando una y sólo una vez por cada cuadra? (no es necesario que termine el recorrido en el punto donde lo inició)
2. Indicar para qué valores de n los siguientes grafos admiten un circuito euleriano: Kn  Cn, Wn, Sn , Ln
3.  ¿Cuál de los grafos G1, G2 o G3 es un árbol? Indicar los vértices colgantes (hojas). ¿Cuántos caminos distintos hay entre  cada par de vértices?
4. Hallar árboles recubridores para cada una de las componentes conexas de los grafos del problema 1.
5. Hallar un árbol recubridor del grafo G6.
6. Considere el árbol dirigido con raíz G7.

a. Indicar el vértice raíz.

b. ¿Cuántos niveles tiene?

c. Indicar los descendientes de c.

d. Indicar los ascendientes de los vértices del nivel 3.

e. Ordenar los vértices en orden previo.

f. Ordenar los vértices en orden posterior.

[pic 7]

1. Considerar el grafo dado por la matriz de adyacencia

[pic 8]

Determinar si es conexo, construyendo un árbol recubridor con un algoritmo de búsqueda (sin graficar el grafo).

...