5.2 Representación de los grafos

5.2 Representación de los grafos

Matriz de adyacencia

1. Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
2. 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 (elementos).

Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.

Matriz de incidencia

1. Las columnas de la matriz representan las aristas del grafo.
2. Las filas representan a los distintos nodos.
3. Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros (0).

ejemplo:

SAUCEDO, F. E. (s.f.). Matematicas Discretas. Obtenido de Matematicas Discretas : https://sites.google.com/site/matedicreta/6-2-representacion-de-los-grafos