En este grupo En todos

Foro de Algoritmos



Algoritmo demostracion en complejidad y correctes.

Luis
Distrito Federal, Mé...
Escrito por Luis Reyes Sanchez
el 14/10/2011

Alguien me puede ayudar a resolver este problemas con su complejidad y correctez en detalle.


Demuestra que el algoritmo de Prim satisface la propiedad del corte (sin

Suponer que ya se demostró que el algoritmo encuentra el árbol generador

De menor peso). Es decir, que si se ejecuta sobre una gráfica G = (V;E)

Con pesos distintos c en las aristas, y S < V , e* la arista de menor peso

Con exactamente un extremo en S, entonces el árbol que encuentra el

Algoritmo incluye a e*.