Algoritmos de Grafos: Prim, Dijkstra, Kruskal y Fleury

Esta clase esta mal ordenada, deberia ir al final de los algoritmos

Ejercicios:
![](

![](

Clase mal ordenada

EJERCICIOS DE PRACTICA

PRACTICA 1 DIJKSTRA

PRACTICA 2 KRUSKAL

PRACTICA 3 FLEURY
afcbacdfea

PRACTICA 4 FLUJO MAXIMO

Acá mis ejercicios:

Flujo máximo de a a b: 8
Flujo máximo de a a d: 12

Dijkstra: abde 11
Kruskal: 27
Fleury: abcdfaefca

Comprobando mis resultados coinciden todos con los que hizo DaneSanchz, pero el ejercicio 3 (El camino de euler) me dio EABCAFCDFE, está bien?

respuestas:

• 1: coste: 11
• 2: coste: 27
• 3: afdcbacfea
• 4: de a hasta b el flujo máximo es 8:
• 5: de a hasta d es 12:

Ejercicios resueltos:

En el ejercicio 3 no se puede hacer un ciclo Eureliano, porque se tiene que pasar tres veces por el nodo inicial y eso incumpliria las reglas para que se de un ciclo Eureliano. Creo que lo hizo para que quedaramos con la duda y después hicieramos el curso de algoritmos, muy crack 😃

1. Algoritmo Dijkstra: Coste de 11.
2. Algoritmo Kruskal: Coste total 27.
3. Ciclo: acfcbacdfea.
4. Flujo máximo de 12

1. abde = 11
2. a-b, b-d, d-c, d-f, d-e = 27
3. Ciclo 1: FEAF - FEAF //// Ciclo 2: ABCA – FEABCAF //// CICLO 3: CFDC - FEABCFDCAF
4. CAMINO 1: AFED – SE RECIBEN 4 //// CAMINO 2: ABCD - SE RECIBEN +4 (TOTAL 8) //// CAMINO 3: ABGED – SE RECIBEN +2 (TOTAL 10) //// CAMINO 4: ABGHD – SE RECIBEN +2 (TOTAL 12)

Hola,

Aquí subo la primera parte de los ejercicios

Hola,
La segunda parte

1. Algoritmo de Dijkstra: ABDE con un costo de 11.
2. Algoritmo de Kruskal: e d b a
   c
   f
   con un costo de 27.
3. Algoritmo de Fleury: AFCDFEABCA
4. Algoritmo de Flujo maximo: de A hasta B de 8.

Aquí la solución al reto de flujo máximo.

He visto que muchos compañeros han colocado como respuesta 12, usando los camino ABGHD, ABGED, AFED y ABCD. Resulta que la arista del punto A a B tiene un costo de 8, entonces al camino **ABC ** tendría un costo de 5. ABGH tendría un costo de 2 y por ABGE un costo de 2, en total daría 9 y eso sobrepasa el costo de AB que es 8

![](

Este es el resultado de los ejercicios:

Resultados:

1. A > B > D > E = 11
2. E > D, D > B, D > C, B > A, D > F = 27
   o
   E > D, D > C, D > B, B > A, D > F = 27
3. ACFDCBAFEA
4. Flujo máximo 12

1)11
2)27
3)AFDCBACFEA
4)Flujo máximo = 12
Caminos
1) AFED = 4
2) ABCD = 5
3) ABGHD = 2
4) ABGED = 1

HAY BANCO DE PREGUNTAS ???

Cordial saludo,
aquí mis ejercicios, el cuarto estoy tratando de comprender como hacerlo (FLUJO MAXIMO), si alguien que me colabore lo agradezco,
![](

!
![](

![](

![](

gracias

Hola, envío mis respuestas

Prim:
capa 0: d
capa 1: c b f
capa 2: a g e
costo mínimo: 18

Dijkstra:
ruta mínima: abde
costo ruta: 11

Kruskal:
expansión mínima: 27
capa 0: d
capa 1: c b e f
capa 2: a

Fleury:
feabcfdcaf
Nota: a pesar de que f tiene 4 conexiones, la mitad es 2 y aún así
me salieron 3 efes en la ruta

Flujo Máximo: 12
ruta 1: abcd = 5
ruta 2: afed = 4
ruta 3: abgh = 2
ruta 4: abged = 1

1. Ejercicio #1
   Coste: 11 | Camino: ABDE
   

   

2. Ejercicio #2
   Coste total: 27
   

   

3. Ejercicio #3
   Camino de euler: a f c b a c d f e a

4. Ejercicio #4
   Flujo máximo: 12
   camino 1 - a b c d = 5
   camino 2 - a f e d = 4
   camino 3 - a b g h d = 2
   camino 4 - a b g e d = 1
   

   

Mis respuestas:

Aquí mis respuestas

1. DIJKSTRA = 11
2. KRUSKAL = 27
3. FLEURY = afacdfeabca
   camino euler = cdf
4. FLUJO MAXIMO = 12

1. Encuentre el camino de menor coste para ir desde a hasta e utilizando el algoritmo de Dijkstra. ¿Cuál es el coste?
   
   
   Coste: 11
2. Encuentre el árbol de expansión mínima utilizando el algoritmo de kruskal:
   
   
3. Encuentre un camino de Euler utilizando el algoritmo de Fleury:
   
   
   Encuentre el flujo Máximo desde a hasta b:
   
   
   Flujo:8