Ejercicios - Algoritmos

39/40

Lectura

Ejemplo:

Encuentre el árbol de expansión mínima y su coste total utilizando el algoritmo de Prim:

Captura de pantalla 2018-07-24 a la(s) 15.09.34.png

Solución

Captura de pantalla 2018-07-24 a la(s) 15.09.59.png

Ejercicios de práctica:

Después de mirar el ejemplo, resuelve los siguientes ejercicios y comenta en el sistema de discusiones tus respuestas.

1. Encuentre el camino de menor coste para ir desde a hasta e utilizando el algoritmo de Dijkstra. ¿Cuál es el coste?

Captura de pantalla 2018-07-24 a la(s) 15.10.49.png

2. Encuentre el árbol de expansión mínima utilizando el algoritmo de kruskal:

Captura de pantalla 2018-07-24 a la(s) 15.11.20.png

3. Encuentre un ciclo Euleliano utilizando el algoritmo de Fleury:

Captura de pantalla 2018-07-24 a la(s) 15.11.51.png

4. Encuentre el flujo Máximo desde a hasta b:

Captura de pantalla 2018-07-24 a la(s) 15.12.36.png

Aportes 44

Preguntas 1

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.




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

Clase mal ordenada

EJERCICIOS DE PRACTICA

PRACTICA 1 DIJKSTRA

PRACTICA 2 KRUSKAL

PRACTICA 3 FLEURY
afcbacdfea

PRACTICA 4 FLUJO MAXIMO

Ejercicios:
![](
![](

otra vez subieron cualquier cosa, pregunta cosas que todavía no vimos

Resultados:

  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

Ejercicios resueltos:

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

![](

  1. Algoritmo Dijkstra: Coste de 11.
  2. Algoritmo Kruskal: Coste total 27.
  3. Ciclo: acfcbacdfea.
  4. Flujo máximo de 12
  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

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




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 ???

Hola,

Aquí subo la primera parte de los ejercicios

Hola,
La segunda parte

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

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

Dijkstra: abde 11
Kruskal: 27
Fleury: abcdfaefca

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

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:
  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.

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

Este es el resultado de los ejercicios:

  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)





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 😃

Acá mis ejercicios:

  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