14 Representacion matricial de grafos

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

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

\displaystyle\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}

Observación.

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

Observación.

En el caso de los grafos dirigidos la situacion es similar. En la posicion $\displaystyle a_{ij}$ aparecera un 1 si hay una arista dirigida cuyo vertice inicial es $\displaystyle v_{i}$ y cuyo vertice final es $\displaystyle 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 $\displaystyle 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.
…