Algoritmo de Potencia para Matriz de Caminho

Vista previa del material en texto

UNIVERSIDAD TECNOLÓGICA DE PANAMÁ 
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES 
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS 
LICENCIATURA EN DESARROLLO DE SOFTWARE 
ESTRUCTURA DE DATOS II 
 
 
 
Laboratorio No.4 
 
 
Prof. Doris Cueto Integrantes: 
 Aparicio, Michael 
 Rivera, Ruben 
 Vasquez, Gabriel 
 Grupo: 
 
 
 
31/05/2023 
 
 
Enunciado: 
Para el siguiente Grafo aplicar el algoritmo de Potencia para encontrar la matriz de camino P. 
Mostrar lo siguiente: 
1. Las matrices de cláusulas transitivas (A, A2, ..,An) a partir de la matriz de Adyacencia. 
2. La matriz B, que es la resultante de suma de matrices (A, A2, ..,An) 
3. La para matriz de camino P, generada mediante el algoritmo de Potencias de matrices. 
4. De existir mencione los nodos sumideros y fuentes en la matriz resultante P. 
FUENTE 1, SUMIDERO 4 
Grafo G 
 
Pasos para hallar la matriz de camino por el método de Potencia: 
1. Obtener la matriz de adyacencia A del grafo G 
 1 2 3 4 
1 0 1 1 0 
2 0 0 0 1 
3 0 1 0 0 
4 0 0 0 0 
 
2. Obtener las potencias de la matriz de adyacencia: A2,A3.. An (n es el número de nodos del grafos 
 
A*A 
 
 
A2= 
 
 
 
 
 
A2*A 
 
A3= 
 
 
 
 
 
 
A3*A 
 
A4= 
 
 
 
 
 
 
 
3. Luego obtener la suma de las matrices B= A + A2,A3.. An (n es el número de nodos del grafos) 
B= 
0 2 1 2 
0 0 0 1 
0 1 0 1 
0 0 0 0 
 
 
 
 
0 1 0 1 
0 0 0 0 
0 0 0 1 
0 0 0 0 
0 0 0 1 
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
 
 
4. Transformar en uno ( 1 ) todas las entradas positivas de B 
 P= 
0 1 1 1 
0 0 0 1 
0 1 0 1 
0 0 0 0