14 Representacion matricial de grafos

Dado un grafo simple $G=(V,E)$ , para construir una de sus matrices de adyacencias, necesitamos ordenar sus vertices. Si el grafo tiene $n$ vertices, $|V|=n$ , y los ordenamos como $V=\left\{v_{1},v_{2},\ldots,v_{n}\right\}$ , la matriz de adyacencias de $G$ con respecto a esa ordenacion de los vertices es la matriz $A=(a_{ij})$ de $n$ filas y $n$ columnas determinadas por la siguiente condicion:

a_{ij}=\begin{dcases}1\text{ si }\left\{v_{i},v_{j}\right\}\in E\\ 0\text{ si }\left\{v_{i},v_{j}\right\}\not\in E\end{dcases}

\begin{pmatrix}&a&b&c&d&e\\ a&0&1&1&1&1\\ b&1&0&1&0&0\\ c&0&1&0&1&0\\ d&1&0&1&0&1\\ e&1&0&0&1&0\\ \end{pmatrix}

Remark 14.1.

Las matrices de adyacencias tambien se pueden utilizar para representar grafos no dirigidos con lazos y aristas multiples. Asi, un lazo en el vertice $v_{i}$ viene representado por un $1$ en la posicion $a_{ii}$ de la matriz de adyacencia. Si se trata de multigrafos, en la posicion $a_{ij}$ de la matriz colocaremos el numero de aristas que conectan el vertice $v_{i}$ y el $v_{j}$ . Asi, si tenemos 3 aristas entre el vertice $v_{i}$ y el $v_{j},$ pondremos $a_{ij}=3$ . En cualquier caso, todos los grafos no dirigidos tienen asociadas matrices simetricas.

Remark 14.2.

En el caso de los grafos dirigidos la situacion es similar. En la posicion $a_{ij}$ aparecera un 1 si hay una arista dirigida cuyo vertice inicial es $v_{i}$ y cuyo vertice final es $v_{j}$ y un cero en caso contrario. Observese que las matrices de adyacencias asociadas a grafos dirigidos no son necesariamente simetricas.

Para dar un grafo basta con dar su matriz de adyacencia y muchas propiedades del grafo se pueden obtener directamente de propiedades de sus matrices de adyacencia, como por ejemplo:

•

El numero de vertices de un grafo es el numero de filas (o columnas) de sus matrices de adyacencia.
•

El grado de un vertice es la suma de los elementos de la fila (o columna) correspondiente de la matriz de adyacencia.
•

Un grafo es no dirigido si su matriz de adyacencia es simetrica.
•

Un grafo contiene lazos si algun elemento de la diagonal de la matriz de adyacencia es no nulo.
•

Un grafo tiene mas de una arista entre dos vertices si alguno de los elementos de su matriz de adyacencia es mayor que $1$ .
•

Si el grafo es no dirigido y no contiene lazos, usando el Teorema de Euler, el numero de aristas es la mitad de la suma de todos los elementos de su matriz de adyacencia.
•

…