REPRESENTACIÓN DE LOS GRAFOS

1. Representación de grafos por matriz de incidencia. Matriz de adyacencia. Definición 1.4.1. Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que unen los vértices vi y vj.

La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.

2. Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.

La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado

3. Dado un grafo dirigido o dígrafo D = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n×n, A(D)=(aij) donde aij es el número de arcos que tienen a vi como extremo inicial y a vj como extremo final. 

La matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice y el número de unos que aparecen en una determinada columna es igual al grado de entrada del correspondiente vértice.

Cibergrafía:

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_RepresentacionMatrices.pdf