Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
2
33
34
5
5 5
5 5y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
2
33
34
5
5 5
5 5y y y
y
y y y
v1 v2 v3
v4
v6
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
y y y
y
y y y
v2
m = 0
B={ }
W ={ v2
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
3
5
5 5y y y
y
y y y
v1 v2 v3
v4
v6
m = 0
B={ }
W ={ v2
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
3
5
5 5y y y
y
y y y
v1 v2 v3
v4
v6
m = 0
B={ }
W ={ v2
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
3
y y y
y
y y y
v2
v6
m = 1
B={{2,6} }
W ={ v2
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
3
y y y
y
y y y
v2
v6
m = 1
B={{2,6} }
W ={ v2 , v6
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
3
4
5
5
5 5
3
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 1
B={{2,6} }
W ={ v2 , v6
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
3
4
5
5
5 5
3
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 1
B={{2,6} }
W ={ v2 , v6
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
3
y y y
y
y y y
v2
v5 v6
m = 2
B={{2,6} {5,6} }
W ={ v2 , v6
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
3
y y y
y
y y y
v2
v5 v6
m = 2
B={{2,6} {5,6} }
W ={ v2 , v6 , v5
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
33
4
5
5
5 5
1
3
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 2
B={{2,6} {5,6} }
W ={ v2 , v6 , v5
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
33
4
5
5
5 5
1
3
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 2
B={{2,6} {5,6} }
W ={ v2 , v6 , v5
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
3
1
3
y y y
y
y y y
v2
v4
v5 v6
m = 3
B={{2,6} {5,6} {4,5} }
W ={ v2 , v6 , v5
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
3
3
y y y
y
y y y
v2
v4
v5 v6
m = 3
B={{2,6} {5,6} {4,5} }
W ={ v2 , v6 , v5 , v4
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
4
5
5
5 5
1
3
3
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 3
B={{2,6} {5,6} {4,5} }
W ={ v2 , v6 , v5 , v4
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
4
5
5
5 5
1
3
3
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 3
B={{2,6} {5,6} {4,5} }
W ={ v2 , v6 , v5 , v4
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
4
1
3
3
y y y
y
y y y
v2 v3
v4
v5 v6
m = 4
B={{2,6} {5,6} {4,5} {3,6} }
W ={ v2 , v6 , v5 , v4
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
3
3
4
y y y
y
y y y
v2 v3
v4
v5 v6
m = 4
B={{2,6} {5,6} {4,5} {3,6} }
W ={ v2 , v6 , v5 , v4 , v3
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
2
5
5
5
1
3
3
4
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 4
B={{2,6} {5,6} {4,5} {3,6} }
W ={ v2 , v6 , v5 , v4 , v3
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
2
5
5
5
1
3
3
4
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 4
B={{2,6} {5,6} {4,5} {3,6} }
W ={ v2 , v6 , v5 , v4 , v3
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
2
1
3
3
4
y y y
y
y y y
v2 v3
v4
v5 v6 v7
m = 5
B={{2,6} {5,6} {4,5} {3,6} {3,7} }
W ={ v2 , v6 , v5 , v4 , v3
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
23
3
4
y y y
y
y y y
v2 v3
v4
v5 v6 v7
m = 5
B={{2,6} {5,6} {4,5} {3,6} {3,7} }
W ={ v2 , v6 , v5 , v4 , v3 , v7
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
5
5
1
23
3
4
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 5
B={{2,6} {5,6} {4,5} {3,6} {3,7} }
W ={ v2 , v6 , v5 , v4 , v3 , v7
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
5
5
1
23
3
4
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 5
B={{2,6} {5,6} {4,5} {3,6} {3,7} }
W ={ v2 , v6 , v5 , v4 , v3 , v7
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
5
1
23
3
4
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 6
B={{2,6} {5,6} {4,5} {3,6} {3,7} {1,4}}
W ={ v2 , v6 , v5 , v4 , v3 , v7
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
23
3
4
5
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
m = 6
Acıclico con n−1 aristas = Arbol buscado
B={{2,6} {5,6} {4,5} {3,6} {3,7} {1,4}}
W ={ v2 , v6 , v5 , v4 , v3 , v7 , v1
Teorıa de Grafos Arboles
Ejemplo 40 Apliquemos el algoritmo de Prim sobre el grafo de los ejemplos anteriores,empezando en el vertice v2 :
1
2
3
34
5
y y y
y
y y y
v1 v2 v3
v4
v5 v6 v7
Prof: Jose Antonio Abia Vian. 57