Un Grafo se puede representar mediante una matriz. Es la forma mas sencilla de representar un grafo. 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 ubicacion 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 numero de aristas (relaciones) entre cada par de nodos (elementos).
existe una matriz de adyacencia unica para cada grafo ( sin considerar las permutaciones de filas o columnas), y viceversa
EJEMPLO DE UNA MATRIZ DE ADYACENCIA
Dado un grafo G=(V,E) con n vértices {V1, ..., Vn} su matriz de adyacencia es la matriz de orden nxn, A(G)= (Aij) donde Aij es el número de aristas que unen los vértices Vi y Vj
EJEMPLO DE UN GRAFO NO DIRIGIDO
La matriz de adyacenncia para el grafo no dirigido
EJEMPLO DE UN GRAFO DIRIGIDO
La matriz de adyacencia para el grafo dirigido
No hay comentarios:
Publicar un comentario