Matriz de adyacencia e
incidencia
Matriz de Adyacencia:
Es un matriz de orden nxn, es decir cuadrada.
Los elementos internos de la matriz son números binarios. Esto indica
la existencia y no de las aristas en el grafo.
La construcción de la matriz es a partir de un grafo G = (N, A) no vacío;
finalmente, se obtiene una matriz que representa el número de aristas
(relaciones) entre cada par de nodos (elementos).
Ejemplo: 2 5
1 4 G = (6, 7)
3 6!
calculo.cc.(s.f).
Ejemplo de aplicación
Su matriz queda de la siguiente forma:
! Nodo
! NODO 1 2 3 4 5 6
!
! 1 0 1 1 0 0 0
! 2 1 0 0 1 0 0
!
! 3 1 0 0 1 0 0
! 4 0 1 1 0 1 0
!
! 5 0 0 0 1 0 1
! 6 0 0 1 0 1 0
!
!
El uno (1) significa la existencia del arco (arista) y el cero (0)
ausencia de la arista (arco). El grafo anterior es un grafo no dirigido.!
calculo.cc.(s.f).
Ahora se puede construir una matriz de adyacencia a partir de un
grafo dirigido:
2
!
1
3 G = (7, 8)
!
6!
4!
5!
!
!
!
7!
La matriz de adyacencia estará conformada por ceros y unos (Ver
diapositiva siguiente)!
Ejemplo de aplicación
La matriz queda así:
!
!
Nodo
! NODO 1 2 3 4 5 6 7
! 1 0 1 0 1 0 0 0
!
! 2 0 0 1 0 0 0 0
! 3 0 0 0 1 1 0 0
!
! 4 0 0 0 0 1 0 0
! 5 0 0 0 0 0 1 0
!
! 6 0 0 0 0 0 0 1
! 7 0 0 0 0 0 0 0
!
!
El uno (1) significa la existencia del arco (arista) dirigido y el cero
(0) ausencia de la arista (arco) dirigida. El grafo anterior es un grafo
dirigido.!
Matriz de incidencia. Es un matriz de orden mxn, es decir m filas y n
columnas. Los elementos internos de la matriz son números binarios: 1 y 0,
cuando es un grafo no dirigido. En cambio, cuando el grafo es dirigido, los
elementos de ella son 1, -1 y 0.
3 4
5!
1!
!
2 6!
G = (6, 7), grafo no dirigido !
!
(Ver matriz de incidencia). !
Su matriz queda de la siguiente forma:
!
Arco
! NODO 1-2 1-3 2-4 2-6 3-4 4-5 5-6
! 1 1 1 0 0 0 0 0
!
! 2 1 0 1 1 0 0 0
! 3 0 1 0 1 1 0 0
!
! 4 0 0 1 0 1 1 0
! 5 0 0 0 0 0 1 1
!
! 6 0 0 0 1 0 0 1
!
!
El uno (1) significa la existencia del arco (arista) y el cero (0)
ausencia de la arista (arco). El grafo anterior es un grafo no dirigido.
Incidencias.mws. (s.f). !
3 4
!
1!
!
!
2!
5!
!
!
6!
G = (6, 7), grafo dirigido !
!
(Ver matriz de incidencia). !
Incidencias.mws. (s.f).
Su matriz queda de la siguiente forma:
Arco
NODO 1-2 1-3 2-6 3-4 4-2 4-5 5-6
! 1 1 1 0 0 0 0 0
!
! 2 -1 0 1 0 -1 0 0
! 3 0 -1 0 1 0 0 0
!
! 4 0 0 0 -1 1 1 0
! 5 0 0 0 0 0 -1 1
!
! 6 0 0 0 0 0 0 -1
!
!
Se observa que en cada columna solo aparecen -1, 1 y 0.!
!
Incidencias.mws. (s.f).
Lista Referencia
• calculo.cc.(s.f). Matrices y grafos. Recuperado de:
http://calculo.cc/temas/temas_algebra/matriz/teoría/matriz matriz_grafo.html!
• Incidencias.mws. (s.f). Matrices de incidencia. Ecuaciones y Variables
independientes. Relaciones topológicas en una red. Recuperado de:
http://www2.elo.utfsm.cl/~lsb/elo102/labs/incidencias.htm!
!
