Representação com matrizes

A um $(p,q)$-grafo ${\cal{G}}$ podemos associar, de forma única, uma matriz $p\times p$, $A_G=A({\cal{G}})$, denominada matriz de adjacÃ^ancia de ${\cal{G}}$, cujas linhas e colunas estão indexadas da mesma forma a uma ordenação dos elementos de ${\cal{V}}$, definida por

onde $u,v\in {\cal{V}}$.

Claro que ao apenas considerarmos grafos ao invés de multigrafos, então as entradas da matriz de adjacência podem apenas tomar os valores 0 e $1$.

Considere os grafos

$\xymatrix{ \ar@(ul,ur)u \ar@{-}[r]\ar@{-}[rd] \ar@{-}[d]& v\ar@{-}[d] \\ x \ar@{-}[r] & w}$

$\xymatrix{ a \ar@(ul,ur)\ar@{-}[r] \ar@{-}[rd]\ar@{-}[rdd]& b\ar@{-}[d]\\ & c\ar@{-}[d] \\ & d }$

Ordenando os vértices do primeiro grafo da forma $(u,v,w,x)$, a matriz de adjacência é

$$A=\left[\begin{array}{cccc} 1&1&1&1\\ 1&0&1&0\\ 1&1&0&1\\ 1&0&1&0\end{array}\right].$$

Como exercício, calcule a matriz de adjacência do segundo grafo, ordenando os vértices como $(a,b,c,d)$.

Como é óbvio, a matriz de adjacência de um grafo (não dirigido) é simétrica.

Vejamos agora o caso dos digrafos.

Nas mesmas condições da definição para grafos, a matriz de adjacÃ^ancia de um digrafo ${\cal{D}}=({\cal{V}},{\cal{A}})$ é a matriz $A_D$ definida por

onde $u,v\in {\cal{V}}$.

Como exemplo, $\left[\begin{array}{cccc}1&1&1&1 1&0&1&0 0&0&1&0 0&0&1&0\end{array}\right]$ é a matriz de adjacência do digrafo

$$\xymatrix{ \ar@(ul,ur)u \ar@/_/[r]\ar[rd] \ar[d]& \ar@/_/[l]v\ar[d] \\ x \ar[r] & \ar@(rd,ru) w}$$

considerando a ordenação dos vértices como $(u,v,w,x)$.

Repare que a linha correspondente ao vértice $u$ diz-nos que de $u$ é extremidade inicial de todas as arestas, e que a coluna correspondente ao vértice $w$ diz-nos que $w$ é extremidade final de todas as arestas. Voltaremos mais tarde a esta noção de alcance.

A um grafo ${\cal{G}}$ podemos associar uma matriz, a matriz de incidÃ^ancia, para uma certa ordenação dos vértices (a que se farão corresponder as linhas) e das arestas (a que se farão corresponder as colunas) fixa previamente, da seguinte forma:

$$I_{\cal{G}}[v,e]=\left\{ \begin{array}{ll} 0 & \text{se $e$ não ... ...não é lacete em $v$}\\ 2 & \text{se $e$ é lacete em $v$} \end{array}\right.$$

onde $v\in {\cal{V}}$ e $e\in {\cal{A}}$.

Calculemos a matriz de incidência do grafo já visto anteriormente, ordenando os vértices como $(u,v,w,x)$ e as arestas como $(a,b,c,d,e,f)$:

$\xymatrix{ \ar@(ul,ur)^a u \ar@{-}[r]^b\ar@{-}[rd]^d \ar@{-}[d]_f& v\ar@{-}[d]^c \\ x \ar@{-}[r]_e & w}$

$I_{\cal{G}}=\left[\begin{array}{cccccc} 2& 1 & 0 &1 &0&1\\ 0&1&1&0&0&0\\ 0&0&1&1&1&0\\ 0&0&0&0&1&1\end{array}\right]$

Como é fácil de verificar, uma outra ordenação dos vértices leva a troca de linhas da matriz de incidência, e uma outra ordenação das arestas a troca de colunas da matriz de incidência.

Proposição 3.1   A soma das entradas de uma qualquer linha da matriz de incidência é igual ao grau do vértice respectivo.

Considere um vértice $v$ do grafo de forma arbitrária, bem como as arestas das quais $v$ é extremidade, mas que não são lacete em $v$ Estas são em número igual $\partial(v)$, que iguala o número de 1's na linha correspondente ao vértive $v$ na matrix de incidência. Ora um lacete $f$ (caso exista) contribui com 2 unidades no cálculo de $\partial(v)$, e 2 é a entrada na linha correspondente ao vértice $v$ e na coluna correspondente à aresta $f$.

Proposição 3.2   A soma das entradas de uma qualquer coluna da matriz de incidência é igual a 2.

Se a aresta $e$ incide em dois vértices distintos, digamos $u$ e $v$, então as entradas correspondentes a $u,e$ e $v,e$ são iguais a 1. Uma aresta incide no máximo em dois vértices, pelo que as outras entradas dessa coluna valem 0. Se $e$ é lacete, então incide num só vértice e a entrada correspondente é 2, sendo as restantes nulas.

A matriz de incidência de um digrafo é definida de forma análoga. Dado o digrafo ${\cal{D}}=({\cal{V}},{\cal{A}})$, e para uma ordenação dos elementos de ${\cal{V}}$ e dos elementos de ${\cal{A}}$ fixa previamente, a matriz de incidência $I_{\cal{D}}$ de ${\cal{D}}$ é dada por

$$I_{\cal{D}}[v,e]=\left\{ \begin{array}{cl} 0 & \text{se $e$ não ... ...não é lacete em $v$}\\ 2 & \text{se $e$ é lacete em $v$} \end{array}\right.$$

onde $v\in {\cal{V}}$ e $e\in {\cal{A}}$.

Por exemplo, no digrafo seguinte, ordenando os vértices como $(u,v,w,x)$ e as arestas como $(a,b,c,d,e,f,g,h)$,

$\xymatrix{ \ar@(ul,ur)^a u \ar@/_/[r]_c\ar[rd]_f \ar[d]_h & \ar@/_/[l]_b v\ar[d]^d \\ x \ar[r]_g & \ar@(rd,ru)_e w}$

$I_{\cal{D}}=\left[\begin{array}{cccccccc} 2& 1 & -1 &0 &0&-1&0&-1\\ 0&-1&1&-1&0&0&0&0\\ 0&0&0&1&2&1&1&0\\ 0&0&0&0&0&0&-1&1\end{array}\right]$

Proposição 3.3   Num digrafo sem lacetes, a soma das entradas de uma coluna da matriz de incidência é zero.

Exercício.