Final del 06/09/10 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1[editar]

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

Ejercicio 2[editar]

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[editar]

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[editar]

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[editar]

Preguntas sobre P y NP, nada del otro mundo.