Ejercicios propuestos — Unidad 5

Para practicar sin mirar soluciones. Intenta justificar cada respuesta con una propiedad (lema del saludo, Euler, etc.).

A) Definiciones y conteos

1. ¿Cuántas aristas tiene \(K_{8}\)? ¿Y \(K_{8,3}\)?
2. En un grafo no dirigido con 10 vértices, la suma de grados es 28. ¿Cuántas aristas hay?
3. ¿Puede existir un grafo no dirigido con grados \(\{4,4,4,1,1,1\}\)? Justifica.

B) Matriz de adyacencia

1. Construye un grafo con 5 vértices cuya matriz de adyacencia tenga exactamente 8 unos fuera de la diagonal. ¿Cuántas aristas tiene?
2. En un grafo simple no dirigido, explica por qué la matriz de adyacencia es simétrica.

C) Conexión, caminos y ciclos

1. Dibuja un grafo no conexo con 7 vértices y 5 aristas. Indica cuántas componentes conexas tiene.
2. Da un ejemplo de circuito que no sea ciclo.

D) Euler y Hamilton

1. Un grafo conexo tiene exactamente dos vértices de grado impar. ¿Qué puedes asegurar sobre recorridos eulerianos?
2. En un grafo simple de 10 vértices, el grado mínimo es 5. ¿Qué puedes afirmar sobre Hamilton?

E) Árboles

1. Un árbol tiene 17 vértices. ¿Cuántas aristas? ¿Cuántas componentes al quitar una arista?
2. Explica por qué un árbol no puede tener ciclos.

F) Redes y algoritmos

1. ¿Por qué Prim y Kruskal son algoritmos voraces (greedy)?
2. ¿En qué condición falla Dijkstra?
3. En una red, si una arista tiene peso 0, ¿Dijkstra sigue siendo válido?

Consejo

Si te atascas, vuelve a las páginas:

• Euler/Hamilton: euler-hamilton.md
• Árboles: arboles-dfs-bfs.md
• Redes: redes-mst-dijkstra.md