Representación de los grafos

                          

El uso de matrices para representar sistemas de ecuaciones, relaciones  o grafos permite una rápida y clara manipulación de la información, así como el determinar algunas propiedades de los grafos que de otra manera serían más difíciles de obtener. Además de esto se tiene que en la computadora es más fácil el manejo de matrices, ya que se pueden tratar como arreglos o listas doblemente ligadas.

A continuación se describen las representaciones matriciales de los grafos.

•          Matriz de adyacencia (Ma)

Es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz. Se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.

•          Matriz de incidencia (Mi)

En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.

Representación Matemática y Computacional de los grafos

En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de las gráficas estudia las propiedades de los grafos (también llamados graficas) Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas. 

Matemáticamente, la representación de un grafo G (V, A) es a través de una matriz M, de n x n con lo cual representamos el valor ponderado de la aristas a_ij en la entrada (i, j) de la matriz M. 

Computacionalmente un grafo se representa como una matriz de ceros y unos. Donde un cero en la posición (i, j) representa que hay camino del vértice i al vértice j y un uno, que si hay camino. En programación, una matriz se representa como un arreglo bidimensional.

Referencias:

MURILLO, J. A. (2009). Grafos. In J. A. MURILLO, Matemáticas para la computación (pp. 292-294). México: Alfaomega.

Ramírez, M. (2005, Septiembre 01). Retrieved from http://www.cimat.mx/~amor/Omi/Entrenamiento/Grafos/Capitulo1.htm