Nombre del alumno: Ulises Manzano Hernández

Matricula: ES1921005869

Grupo: MT – MMDI – 2001 – B1 – 003

Materia: Matemáticas Discretas

Carrera: Licenciatura en Matemáticas

Nombre de la Actividad: Evidencia de Aprendizaje de la Unidad 3 “(Aplicación)

Problema Prototipico”

Nombre de la escuela: Universidad Abierta y a Distancia de México

Nombre del profesor: Jose Eduardo García Mendiola

Fecha de entrega: 21 al 22 de Marzo de 2020

Ejercicios
1. A partir de la siguiente matriz encuentra el camino mínimo entre los vértices
3 y 4.

Se realiza el grafo de la siguiente matriz de acuerdo a su vertice indicado:

1 2 3 4 5 6
1 0 3 5 1 ∞ ∞
2 3 0 ∞ ∞ 9 ∞
3 7 1
𝐴= 5 ∞ 0 7
4 1 ∞ 7 0 ∞ 4
5 ∞ 9 7 ∞ 0 ∞
6 [∞ ∞ 1 4 ∞ 0 ]

2
3 9

1 4 6
1 4 5
7
5 1
7
3
Aplicando el algoritmo de Floyd – Warshall, se va a realizar 2 matrices : una
de distancias y otra de recorridos:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 ∞ ∞
2 3 0 ∞ ∞ 9 ∞
3 5 ∞ 0 7 7 1
4 1 ∞ 7 0 ∞ 4
5 ∞ 9 7 ∞ 0 ∞
6 ∞ ∞ 1 4 ∞ 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 5 6
2 1 - 3 4 5 6
3 1 2 - 4 5 6
 4 1 2 3 - 5 6
5 1 2 3 4 - 6
6 1 2 3 4 5 -
Y se realiza las opraciones de las 2 tablas para que te den la distancia minima:
Primer columna y primera fila:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 ∞ ∞
2 3 0 8 4 9 ∞
3 5 8 0 6 7 1
4 1 4 6 0 ∞ 4
5 ∞ 9 7 ∞ 0 ∞
6 ∞ ∞ 1 4 ∞ 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 5 6
2 1 - 1 1 5 6
3 1 1 - 1 5 6
4 1 1 1 - 5 6
5 1 2 3 4 - 6
6 1 2 3 4 5 -
Segunda columna y segunda fila:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 12 ∞
2 3 0 8 4 9 ∞
3 5 8 0 6 7 1
4 1 4 6 0 13 4
5 12 9 7 13 0 ∞
6 ∞ ∞ 1 4 ∞ 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 2 6
2 1 - 1 1 5 6
3 1 1 - 1 5 6
4 1 1 1 - 2 6
5 2 2 3 2 - 6
6 1 2 3 4 5 -
Tercer columna y tercer fila:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 12 6
2 3 0 8 4 9 9
3 5 8 0 6 7 1
4 1 4 6 0 13 4
5 12 9 7 13 0 8
6 6 9 1 4 8 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 2 3
2 1 - 1 1 5 3
3 1 1 - 1 5 6
4 1 1 1 - 2 6
5 2 2 3 2 - 3
6 3 3 3 4 3 -
Cuarta columna y cuarta fila
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 12 5
2 3 0 8 4 9 8
3 5 8 0 6 7 1
4 1 4 6 0 13 4
5 12 9 7 13 0 8
6 5 8 1 4 8 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 2 4
2 1 - 1 1 5 4
3 1 1 - 1 5 6
4 1 1 1 - 2 6
5 2 2 3 2 - 3
6 4 4 3 4 3 -
Quinta columna y quinta fila:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 12 5
2 3 0 8 4 9 8
3 5 8 0 6 7 1
4 1 4 6 0 13 4
5 12 9 7 13 0 8
6 5 8 1 4 8 0
 Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 2 4
2 1 - 1 1 5 4
3 1 1 - 1 5 6
4 1 1 1 - 2 6
5 2 2 3 2 - 3
6 4 4 3 4 3 -
Sexta columna y sexta fila:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 12 5
2 3 0 8 4 9 8
3 5 8 0 5 7 1
4 1 4 5 0 12 4
5 12 9 7 12 0 8
6 5 8 1 4 8 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 2 4
2 1 - 1 1 5 4
3 1 1 - 6 5 6
4 1 1 6 - 6 6
5 2 2 3 6 - 3
6 4 4 3 4 3 -
Por lo tanto, tenemos nuestra matriz de distancias minimas con sus reccorridos
modificados:
Matriz de distancias
1 2 3 4 5 6
1 0 3 5 1 12 5
2 3 0 8 4 9 8
3 5 8 0 5 7 1
4 1 4 5 0 12 4
5 12 9 7 12 0 8
6 5 8 1 4 8 0

Matriz de Recorridos
1 2 3 4 5 6
1 - 2 3 4 2 4
2 1 - 1 1 5 4
3 1 1 - 6 5 6
4 1 1 6 - 6 6
 5 2 2 3 6 - 3
6 4 4 3 4 3 -
Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo
entre 2 vértices cualesquiera del grafo será el obtenido en la matriz final. En
este caso, el camino mínimo entre 3 y 4 vale 5.
Y se meustra durante el grafo: Camino
2 minimo
3 9

1 4 6
1 4 5
5 7 1
3 7

2. Construye la matriz de distancias mínimas entre cualquier par de vértices

para el siguiente grafo.

Se aplica con el algoritmo de Dijkstra, para encontrar la distancia minima de

este grafo dirigido, usando una tabla siguiente:
Vertice Paso 1 Paso 2 Paso 3 Paso 4
A (0, 𝑎) ∆ ∆ ∆
B (5, 𝑎) (4, 𝑐) (4, 𝑐) ∆
C (3, 𝑎) (3, 𝑎) ∆ ∆
D ∞ (7, 𝑐) (6, 𝑏) (6, 𝑏)
Entonces, tenemos nuestra matriz de distancias minimas utilizando este
algoritmo.
Por lo tanto, nuestra distancia minima de este digrafo es: [𝑎 − 𝑐 − 𝑏 − 𝑑] con
una distancia minima de 𝑑 = 6.
Queda resuelto el ejercicio señalando la distancia en el grafo:
 Distancia minima

3. Investiga y redacta el concepto de Matriz de Caminos.

Matriz de Caminos
Sea 𝐺 un grafo no ponderado.
La matriz de cierre transitivo o matriz de caminos, a la que se denotará como
𝐴, de un grafo 𝐺, es una matriz tal que 𝐴[𝑖][𝑗] = true si hay un camino de
longitud mayor que 0 del nodo 𝑖 al nodo 𝑗. En otro caso, 𝐴[𝑖][𝑗] = false.
Debido a la existencia de ciclos en un grafo, se pueden dar caminos de
longitud infinita.
Teorema de cierre transitivo: Sea 𝐺 un grafo con 𝑛 nodos. Si entre dos nodos
de 𝐺, 𝑖 y 𝑗, existe un camino de longitud 𝑚 > 𝑛, entonces debe existir entre
ellos otro camino de longitud ≤ 𝑛, donde la longitud será 𝑛 si y solo si 𝑖 == 𝑗
(es un ciclo).
• En un grafo con 𝑛 nodos, cualquier camino simple está formado como
máximo por 𝑛 − 1 arcos.
• Cualquier ciclo tiene longitud menor o igual que 𝑛.
La matriz de adyacencia, 𝐴𝑑𝑦, de un grafo 𝐺 indica todos los caminos de
longitud 1 en ese grafo.
• 𝐴𝑑𝑦[𝑖][𝑘] = 1, hay un camino de longitud 1 entre 𝑖 y 𝑘.
• 𝐴𝑑𝑦[𝑘][𝑗] = 1, hay camino de longitud 1 entre 𝑘 y 𝑗.
Si 𝐴𝑑𝑦[𝑖][𝑘] AND 𝐴𝑑𝑦[𝑘][𝑗] = 1, entonces hay un camino de longitud 2 de 𝑖 a
𝑗 (el que pasa por 𝑘).
Sea 𝐺 un grafo con 𝑛 nodos. Para cualquier par de nodos 𝑖, 𝑗, existe un camino
de longitud 2 que los une si se cumple:
(𝐴𝑑𝑦[𝑖][1] AND 𝐴𝑑𝑦[1][𝑗]) OR (𝐴𝑑𝑦[𝑖][2] AND 𝐴𝑑𝑦[2][𝑗]) OR ... OR (𝐴𝑑𝑦[𝑖][𝑛]
AND 𝐴𝑑𝑦[𝑛][𝑗])
Esta expresión, para todos los pares 𝑖, 𝑗 de nodos, se calcula como el producto
booleano de la matriz de adyacencia por sí misma:
𝐴2 = 𝐴𝑑𝑦 × 𝐴𝑑𝑦
𝐴2 [𝑖][𝑗] = 1 (ó 𝐴2 [𝑖][𝑗] = true) si existe un camino de longitud 2 desde 𝑖 a 𝑗.
4. Construye la matriz de caminos correspondiente al ejercicio (2).
Se realiza la siguiente matriz de caminos que se realiza la siguiente:
Primero se realiza la matriz de adyecencia:
𝐴 𝐵 𝐶 𝐷
𝐴 0 1 1 1
𝐴 = 𝐵 [ 1 0 1 1]
𝐶 0 1 0 1
𝐷 0 0 1 0
Y para calular la matriz de caminos, se multiplica 2 veces la matriz indicada,
como lo puedes ver la siguienet:
0 1 1 1 2 0 1 1 1 0 1 1 1 1 1 2 2
𝐴2 = [1 0 1 1] = [1 0 1 1] [1 0 1 1] = [0 2 2 2]
0 1 0 1 0 1 0 1 0 1 0 1 1 0 2 1
0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1
Por lo tanto, tenemios nuestra matriz de caminos, que solamente se hace
primero la matriz de adyacencia y al ultimo se multiplica 2 veces la matriz.
1 1 2 2
Por lo tanto, nuestra matriz de caminos es de: [0 2 2 2]
1 0 2 1
0 1 0 1

5. Aplica el Método de la Ruta Crítica (CPM) de acuerdo con la tabla de

actividades siguiente. Calcula la red: tiempos de inicio y terminación;
holguras; y, establece la Ruta Crítica e indícala en la red.

Primero se observa la tabla con sus caracteristicas, que se lleva los siguiente
pasos:
1. Se elabora el grafo con su cantidad de tiempo que serían las semanas:
3 𝑠𝑒𝑚 14 𝑠𝑒𝑚
𝐺
5 𝑠𝑒𝑚 𝐷

𝐴 𝐸 𝐹
0 𝑠𝑒𝑚 0 𝑠𝑒𝑚
E1 𝑠𝑒𝑚
Inicio 𝐶 4 𝑠𝑒𝑚 Fin
𝐼
4 𝑠𝑒𝑚 2 𝑠𝑒𝑚
𝐵 𝐻
6 𝑠𝑒𝑚
12 𝑠𝑒𝑚
 2. Se calculan los términos e inicios lejanos y cercanos.
0 5 3 𝑠𝑒𝑚 5 8 14 𝑠𝑒𝑚
0 5 7 10 𝐺 10 24
0 0 5 𝑠𝑒𝑚 𝐷 5 6 10 24 26 26
0 0 5 6 26 26
𝐴 6 10
0 𝑠𝑒𝑚 5 9 𝐸 𝐹 0 𝑠𝑒𝑚
20 24 E 6 10
Inicio 1 𝑠𝑒𝑚 4 𝑠𝑒𝑚 Fin
0 6 𝐶
6 12 𝐼
4 𝑠𝑒𝑚 𝐻 2 𝑠𝑒𝑚
𝐵
6 18 24 26
6 𝑠𝑒𝑚 12 24 12 𝑠𝑒𝑚 24 26
3. Se calcula la holgura:

ℎ=0 ℎ=2 ℎ=0

14 𝑠𝑒𝑚
ℎ=0
0 5 3 𝑠𝑒𝑚 5 8 10 24
0 5 7 10 𝐺 10 24
0 0 5 𝑠𝑒𝑚 𝐷 5 6
6 10 26 26
0 0 ℎ=0 5 6
𝐴 6 10 26 26
0 𝑠𝑒𝑚 5 9 𝐸 𝐹 ℎ=0
20 24 E
1 𝑠𝑒𝑚
Inicio 0 6 4 𝑠𝑒𝑚 Fin
𝐶
6 12 ℎ = 15 𝐼
4 𝑠𝑒𝑚 𝐻 0 𝑠𝑒𝑚
𝐵 24 26
6 18
24 26 ℎ=0
6 𝑠𝑒𝑚 12 2412 𝑠𝑒𝑚
ℎ=6 ℎ=6 ℎ=0

4. Identifica la ruta crítica: 2 𝑠𝑒𝑚

Por lo tanto, la ruta critica de esta tabla es de: 𝑅𝑢𝑡𝑎 𝐶𝑟𝑖𝑡𝑖𝑐𝑎: 𝐼𝑛𝑖𝑐𝑖𝑜 − 𝐴 − 𝐸 −
𝐹 − 𝐹 − 𝐺 − 𝐼 − 𝐹𝑖𝑛. Con una duración de 26 𝑠𝑒𝑚𝑎𝑛𝑎𝑠
Se muestra la ruta en el grafo:
ℎ=0 ℎ=2
5 8 14 𝑠𝑒𝑚 ℎ = 0
0 5 3 𝑠𝑒𝑚 10 24
ℎ=0 0 5 7 10 𝐺 10 24
0 0 5 𝑠𝑒𝑚 𝐷 5 6
6 10 ℎ=0
0 0 5 6 26 26
𝐴 6 10
0 𝑠𝑒𝑚 5 9 𝐸 𝐹 ℎ=0 26 26
20 24 E ℎ = 0
Inicio 0 6 1 𝑠𝑒𝑚 4 𝑠𝑒𝑚 Fin
𝐶
6 12 ℎ = 15 𝐼 0 𝑠𝑒𝑚
4 𝑠𝑒𝑚 𝐻
𝐵 2 𝑠𝑒𝑚 24 26
6 18 24 26
6 𝑠𝑒𝑚 12 2412 𝑠𝑒𝑚 ℎ=0
ℎ=6 ℎ=6
Queda resuelto el ejercicio.
Conclusiones
En el ejercicio 1, con la matriz de distancias minimas se debe obtener un
camino miino usando el algoritmo de Floyd Warshall, ya que solamente se
hace las operaciones de las matrices, el de distancia y de recorridos, y
obtuvimos un camino corto entre los vertices 3 y 5; en el ejercicio 2 se tiene
que obtener la distancia minima del siguiente grafo dirigido utilizando el
algoritmo de Dijkstra, que solamente se hace las operaciones y obtuvo su
distancia minima de este grafo dirigido; en el ejercicio 3 se hizo una
investigación sobre el concepto de las matrices de caminos, con sus formulas
e explicación de cada una; en el ejercicio 4 con el grafo dirigido del ejercicio 2
se resuelve la matriz de caminos, lo que se tiene que hacer es hacer la matriz
de adyacencia y al ultimo mutiplicarlo 2 veces como la matriz elevada al
cuadrado, y se obtuvo su matriz de caminos; y en el ejercicio 5 por fin es el
ejercicio del metodo de la ruta critica, que solamente es crear el grafo con su
tabla de las caracteristicas, despues se hace los calculos de loa terminos e
inicios lejanos y cercanos de cada vertice, luego los calculos de las holguras,
y al final identificar y ubicar su ruta critica en el grafo y se realizo
completamente.

Bibliografía
Anonimo. (2012). Users. Obtenido de Grafos:
https://users.dcc.uchile.cl/~bebustos/apuntes/cc3001/Grafos/
Badia, J., Martnez, B., Morales, A., & Sanchiz, J. (2016). PDF. Obtenido de
Tema 11 Estructura de Grafos:
http://repositori.uji.es/xmlui/bitstream/handle/10234/119829/tema11.pdf
?sequence=1&isAllowed=y
Bonilla Garzón, A. (4 de Junio de 2017). YouTube. Obtenido de Algoritmo de
Dijkstra: Distancia mínima:
https://www.youtube.com/watch?v=w475Vm1ZgTk
Bustamante, K. (30 de Mayo de 2016). YouTube. Obtenido de CPM -
MÉTODO DE LA RUTA CRITICA:
https://www.youtube.com/watch?v=Fw0jhTu2G2U
Licencia Creative Commons Atribución. (18 de Noviembre de 2019). Wikipedia
La Enciclopedia Libre. Obtenido de Algoritmo de Floyd-Warshall:
https://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall
M, H. (8 de Noviembre de 2016). YouTube. Obtenido de algoritmo de Floyd-
Warshall: https://www.youtube.com/watch?v=h-nmexY9gtA
UnADM. (20 de Enero de 2020). PDF. Obtenido de Unidad 3 "Discretización":
file:///D:/UnADM/Clases%20Universidad/Semestre%202/Matem%C3%
A1ticas%20Discretas/U3_Contenido.pdf