guía de ejercicios grafos

Ingeniería en Sistemas de Información Matemática discreta y autómatas

Guía de ejercicios: Teoría de Grafos

1. Sea G = (V, E) el grafo de la figura:

a) ¿Cuántos caminos simples hay en G de a a h?

b) ¿Cuántos de estos caminos simples tienen longitud

5?

2. Siete ciudades a, b, c, d, e, f y g están conectadas por un

sistema de rutas como se indica:

a) I-22 va de a a c, pasando por b

b) I-33 va de c a d, luego pasa por b mientras continúa hacia f.

c) I-44 va de d hacia a, a través de e

d) I-55 va de f a b, pasando por g

e) I-66 va de g a d.

a) Utilizando vértices para las ciudades y aristas dirigidas para los segmentos de rutas

que comunican a las ciudades, dibujar un grafo que modelice esta situación.

b) Listar los caminos simples que hay de g a a.

c) Cuál es el menor número de segmentos de ruta que podrían cerrarse de manera

que se pueda viajar de b a d sin interrupciones?

d) Es posible partir de la ciudad c y volver a ella, visitando cada una de las demás

ciudades una sola vez?

e) Cual es la respuesta a la parte d si no se requiere volver a c?

f) Es posible empezar en alguna ciudad y manejar sobre cada una de estas rutas

exactamente una vez? (Está permitido visitar una ciudad más de una vez, y no se

necesita volver a la ciudad de la que se empezó)

3. Dado el grafo G de la siguiente figura, y los subgrafos G1 y G2.

a) Cuántos subgrafos conexos de G tienen 4 vértices e incluyen un ciclo?

Lic. Georgina Rodríguez

Matemática Discreta y Autómatas Página 2

b) Describa el subgrafo G1 como un subgrafo inducido y como obtenido mediante el borrado

de vértices.

c) Describa el subgrafo G2 como un subgrafo inducido y como obtenido mediante el borrado

de vértices.

d) Dibujar el subgrafo inducido por V = {b, c, d, f, i, j}

e) Para G, sea la arista e = {c, f}. Dibujar G-e.

4. Sea G = {V, E} un grafo no dirigido. Sea G1 = {V1, E1}. Bajo qué condiciones G1 no es un subgrafo

inducido? Encontrar un subgrafo que no sea inducido, para el grafo G del ejercicio 5.

5. Para cada par de grafos siguientes,

a) Determinar el grado de cada vértice

b) Determinar si son o no isomorfos

6. Dados los siguientes grafos:

a) Escribir la matriz de adyacencia

b) Escribir la matriz de incidencia

a) b)



c) d)

e) f)

g) h)

7. Escribir el grafo representado por las siguientes matrices de adyacencia:

a)

b)

c)

d)



8. Dibuje los grafos representados por las siguientes matrices de incidencia:

a)

b)

9. En los siguientes pares de grafos, determine si son o no isomorfos. En caso que lo sean,

determine el isomorfismo, en caso contrario, indique un invariante no compartido.

a)

b)

c)

d)



e)

10. En los siguientes grafos, determine si existe algún circuito de Euler

a)

b)

c)

d)

11. Determine si existe un ciclo hamiltoniano en los siguientes grafos:

a) b) c)

Árboles

12. Trace todos los árboles no isomorfos de 6 vértices.

13. Sean T1= (V1, E1) y T2 = (V2, E2) árboles tales que|E1| = 17 y |V2| = 2 |V1|. ¿Cuánto valen |E2|,

|V1| y |V2|?



14. Dé un ejemplo de un grafo G = (V, E) tal que |V| = |E| + 1 pero que no sea un árbol.

15. El grafo no dirigido conexo G = (V, E) tiene 30 aristas.¿ Cuál es el máximo valor que puede

tomar |V|?

16. Considere el árbol de la figura, y responda:

a) ¿Qué vértices son las hojas?

b) ¿Qué vértice es la raíz?

c) ¿Qué vértice es el padre de g?

d) ¿Qué vértices son los descendientes de c?

e) ¿Qué vértices son los hermanos de s?

f) ¿Cuál es el número de nivel del vértice f?

g) ¿Qué vértices tienen número de nivel 4?

h) ¿Cuál es la altura del árbol?

17. Encuentre el árbol recubridor en profundidad para los grafos siguientes si el orden de los

vértices es:

i. a, b, c, d, e, f, g, h

ii. h, g, f, e, d, c, b, a

iii. a, b, c, d, h, g, f, e

a) b) c)

18. Encuentre el árbol recubridor a lo ancho para los grafos y órdenes dados en el ejercicio 19.

19. Sea G = (V, E) un grafo no dirigido con matriz de adyacencia A(G) dada por



Utilice una búsqueda a lo ancho en base a A(G) para determinar si G es conexo.

20. Para el grafo que se encuentra en la figura, determine el árbol recubridor a lo ancho si los

vértices se ordenan como:

i. a, b, c, d, e, f

ii. a, b, e, c, d, f

iii. a, c, d, b, e, f

21. Aplique la ordenación por inserción a cada una de las siguientes listas. Trace los árboles de

separación e inserción para cada aplicación del procedimiento:

a) -1, 0, 2, -2, 3, 6, -3, 5, 1, 4

b) -1, 7, 4, 11, 5, -8, 15, -3, -2, 6, 10, 3

22. Aplique el algoritmo de Dijkstra al grafo ponderado G = (V, E) de la figura y determine la

distancia más corta del vértice a a cada uno de los demás vértices.

23. Aplique los algoritmos de Prim y de Kruskal para determinar árboles recubridores minimales

para el grafo de la siguiente figura:

guía de ejercicios grafos

Documents