Final del 06/09/10 (Algoritmos III)

Ejercicio 1

Si G es un grafo con n vertices, m aristas y k componentes conexas, probar que $m\leq (n-k+1)(n-k)/2$.

Ejercicio 2

Dado un grafo conexo G con pesos en las aristas, probar que si hay una única arista de peso mínimo, entonces todo árbol generador mínimo de G la contiene.

Ejercicio 3

Hacer modificaciones al algoritmo de Dijkstra para resolver los siguientes problemas en un grafo con pesos en las aristas:

• Contar la cantidad de caminos mínimos entre dos vértices.
• De entre todos los caminos mínimos entre dos vértices, encontrar el que contenga menos aristas.

Ejercicio 4

Responda justificando.

• ¿Pueden ser un grafo y su complemento ambos planares?
• Si todos los subgrafos propios de un grafo G son planares, ¿entonces G es planar?
• ¿Cuántas aristas y regiones tiene un grafo maximalmente planar de n vértices?

Ejercicio 5

Preguntas sobre P y NP, nada del otro mundo.