Actividad-8 Formas de representar grafos y árboles - Ejercicios PDF

Preview

Summary

Actividad-8 Formas de representar grafos y árboles - Ejercicios...

Description

Harold Ducon Abril Actividad 02 Formas de representar grafos y árboles

1. Dibujar modelos de grafos, especificando el tipo de grafo utilizado para representar un sistema de rutas aéreas en el que cada día hay cuatro vuelos de Boston a Newark, dos vuelos de Newark a Boston, tres vuelos de Newark a Miami, dos vuelos de Miami a Newark, un vuelo de Newark a Detroit, dos vuelos de Detroit a Newark, tres vuelos de Newark a Washington, dos vuelos de Washington a Newark y un vuelo de Washington a Miami, de modo que: a.

Hay una arista conectando cada par de vértices que representan ciudades para las que hay un vuelo de la una a la otra (en cualquiera de los dos sentidos)

b.

Hay una arista conectando dos ciudades por cada vuelo que opere entre las dos ciudades (en cualquiera de los dos sentidos)

c.

Hay una arista conectando dos ciudades por cada vuelo que opere entre las dos ciudades (en cualquiera de los dos sentidos) más un

buble que representa una excursión turística que despega y aterriza en Miami.

d.

Hay una arista que sale de cada vértice asociado a una ciudad de la que despega algún vuelo y que llega al vértice correspondiente a la ciudad en que aterriza el vuelo

e.

Hay una arista por cada vuelo que sale del vértice que representa a

la ciudad en que inicia el vuelo y llega al vértice que representa a la ciudad en que aterriza.

2. En los siguientes grafos determina si estos son grafos simples, un multígrafo, un seudografo, un grafo dirigido o un multígrafo dirigido.

a.

no hay flechas en los bordes que conectan los vértices. no hay aristas que conecten un vértice del gráfico consigo mismo. no hay un par de vértices en el gráfico que tenga más de un borde entre ellos, por esto es un grafico simple. b.

no hay flechas en los bordes que conectan los vértices. no hay aristas que conecten un vértice del gráfico consigo mismo. existe al menos un par de vértices en el gráfico que tiene más de un borde entre ellos. especialmente a d b, y b y d tienen múltiples aristas entre ellos. por esto es un multígrafo. c.

no hay flechas en los bordes que conectan los vértices. hay algunos bordes que conectan un vértice del gráfico consigo mismo, especialmente, a, b y d tienen bucles propios. existe al menos un par de vértices en el gráfico que tiene más de un borde entre ellos. especialmente a d b, y b y d, y c y d tienen múltiples aristas entre ellos. por esto es un seudografo. d.

hay flechas en los bordes que conectan los vértices. c y d no tienen varios bordes entre ellos, ya que la dirección de los dos bordes entre ellos es opuesta. para tener varios bordes en un gráfico dirigido, la dirección de los múltiples bordes debe ser la misma. Hay algunas aristas que conectan un vértice del gráfico consigo mismo en este gráfico c y e tienen bucles. Por esto es un grafo dirigido.

e.

hay flechas en los bordes que conectan los vértices. Algunos vértices tienen más de un borde en la misma dirección entre ellos. en este gráfico, hay múltiples aristas entre b y c, e y d. hay algunas aristas que conectan un vértice del mismo gráfico consigo mismo. en este gráfico, d y f tienen bucles. 3. En un torneo de todos contra todos, los Tigers vencieron a los Blue Jays, los Tigers vencieron a los Cardinals, los Tigers vencieron a los Orioles, los Blue Jays vencieron a los Cardinals, los Blue Jays vencieron a los Orioles y los Cardinals vencieron a los Orioles. Representar los resultados usando un grafo dirigido.

4. En los grafos dirigidos 1-3 hallar el número de vértices, el número de aristas y el grado de cada vértice. Identifique todos los vértices aislados y las hojas.

1. Numero de vértices: 6 Numero de aristas: 6 Grado(a)= 2 Grado(b)= 4

Grado(c)= 1 Grado(d)= 0 Grado(e)= 2 Grado(f)= 3 Vértices aislados: d Hojas: c

2. Numero de vértices: 5 Numero de aristas: 13 Grado(a)= 6 Grado(b)= 6 Grado(c)= 6 Grado(d)= 5 Grado(e)= 3 Vértices aislados: No hay Hojas: No hay

3. Numero de vértices: 9 Numero de aristas: 12 Grado(a)= 3 Grado(b)= 2 Grado(c)= 4 Grado(d)= 0 Grado(e)= 6 Grado(f)= 0 Grado(g)= 4 Grado(h)= 2 Grado(i)= 3 Vértices aislados: d, f Hojas: No hay 5. Para los grafos 1-4 utilizar una lista de adyacencia para representarlos.

1. Vértice A B C D

Vértice adyacente B, c, d A, d A, d A, b, c

Vértice A B C D E

Vértice adyacente B, d A, d, e D, e A, b, c B, c

Vértice A B C D

Vértice adyacente A, b, c, d D A, b B, c, d

Vértice A B C D E

Vértice adyacente B, d A, c, d, e B, c A, e C, e

2.

3.

4.

6. Para las matrices de adyacencia a-c dibujar el grafo que le corresponda.

a.

b.

C.

7. Utilizar una matriz de incidencia para representar los grafos A-E mostrados a continuación.

a.

b.

c.

d.

8. Determinar si par de grafos correspondiente es o no isomorfo.

a. Si es isomorfo

b. Si es isomorfo

c. No es isomorfo

Grado de secuencia: 3, 3, 3, 3, 2

Grado de secuencia: 4, 3, 3, 2, 2

9. Un árbol binario es propio o lleno si cada nodo interno tiene dos subárboles. Pruebe que un árbol binario lleno no vacío, el número de nodos terminales es igual al número de nodos internos más 1. La prueba es por inducción sobre el número total n de nodos en el ´árbol T. Si n = 1 (caso base) entonces ese nodo es un terminal y no hay nodos internos, por lo tanto, se satisface la afinación. Si n > 1 entonces la raíz tiene 2 subárboles T1 y T2 cada uno de los cuales es lleno. Sean i1, i2 y t1, t2 los números de nodos internos y terminales en los dos árboles respectivamente. Por hipótesis de inducción t1 = i1+ 1 y t2= i2 + 1. Los nodos terminales de T son los terminales de t1 y los terminales de t2. Por lo tanto, el número t de nodos terminales en T es t = t1 + t2 . En cuanto a nodos internos, T tiene uno adicional, la raíz. Por lo tanto, el número i de nodos internos de T es i = i1+ i2 + 1. Entonces i = i1+ i2 + 1= (t1− 1) + (t2− 1) + 1 = (t1+ t2) − 1 = t − 1. Por lo tanto, la misma relación entre t e i se satisface para T. Esto completa la prueba por inducción. 10. Contestar las siguientes preguntas relativas al árbol raíz que se muestra a continuación.

a. ¿Cuál es el vértice raíz? A b. ¿Cuáles son los vértices internos? B, C, D c. ¿Cuáles vértices son hojas? E, L, M, N, G, O, P, I, K, S, U, R d. ¿Cuáles vértices son hijos de j? Q, R e. ¿Qué vértice es padre de h? C f.

¿Qué vértices son hermanos de o? P

g. ¿Cuáles son los antecesores de m? F, B, A h. ¿Cuáles son los descendientes de b? E, F, L, M, N...