Matrices Asociadas A Grafos

1.4. Representación de grafos. 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 esla matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que
unen los vértices vi y vj.
Ejemplo 1.4.2.

La matriz de adyacencia de un grafo es simétrica. Si unvé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 yunos (matriz binaria) y la
diagonal esta compuesta sólo por ceros.

Definición 1.4.3. 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.
Ejemplo 1.4.4.

La matriz deincidencia 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 apareceen cada fila es igual al grado del vértice correspondiente.
Una fila compuesta sólo por ceros corresponde a un vértice aislado.
Definición 1.4.5. Dado un grafo dirigido odí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 inicialy a vj como extremo final.
Ejemplo 1.4.6.

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 igualal 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.