MULTIGRAFO

Es un grafo que consta de segmentos multiples y lazos. Es un grafo que esta facultado para tener aristas multiples ; es decir, aristas que relacionan los mismos nodos.

De esta forma, dos nodos pueden estar conectados por mas de una arista.

Algunos autores permiten que los multigrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo.

Un multigrafo es un grafo dirigido que esta facultado para tener aristas multiples, es decir, aristas con los mismos nodos iniciales y finales

MATRIZ DE ADYACENCIA

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