Final del 06/09/10 (Algoritmos III)

De Cuba-Wiki

Plantilla:Back

Ejercicio 1

Si G es un grafo con n vertices, m aristas y k componentes conexas, probar que .

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.