MATRIZ DE ADYACENCIA
La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.
Construcción de la matriz a partir de un grafo
Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.
Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.
Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos.
Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.
EJEMPLOS
Propiedades de la matriz de adyacencia
- Para un grafo no dirigido la matriz de adyacencia es simétrica.
- El número de caminos Ci,j(k), atravesando k aristas desde el modo i al modo j, viene dado por un elemento de la potencia k-ésima de la matriz de adyacencia:
![C_{i,j}(k) =
[\mathbf{A}^k]_{ij}](https://upload.wikimedia.org/math/b/4/2/b42414b8ad5c2c076e14df663015703b.png)
PRESENTADO POR:
DANIEL FELIPE SUAREZ MONTILLA
GUSTAVO ADOLFO ACERO MARTINEZ
JHON ALDEMAR GARCIA ARIAS
YEIN FREIMAN MUÑOZ BARRETO
CINDY PAOLA ARAGON ORTIZ
No hay comentarios:
Publicar un comentario