Teoria dos Grafos → Representação Computacional

Matriz de Incidência

Seja \(G=(V,A)\) um grafo com \(V=\{v_1,v_2,\dots,v_n\}\) e \(A=\{a_1,a_2,\dots,a_m\}\). A matriz de incidência de \(G\) é a matriz \[ B=(b_{ij}) \in \mathbb{R}^{n \times m}, \] onde as linhas representam arestas (ou arcos) e as colunas representam vértices.

Grafo não orientado

b_{ij} = \begin{cases} -1, & \text{se } a_i \text{ sai de } v_j, \\ \phantom{-}1, & \text{se } a_i \text{ chega em } v_j, \\ 0, & \text{caso contrário.} \end{cases}

Cada coluna da matriz possui exatamente dois valores 1, correspondentes aos dois vértices ligados pela aresta.

Grafo orientado (mais usado em computação)

b_{ij} = \begin{cases} -1, & \text{se } a_j \text{ sai de } v_i, \\ \phantom{-}1, & \text{se } a_j \text{ chega em } v_i, \\ 0, & \text{caso contrário.} \end{cases}

\(-1\) indica o vértice de origem do arco
\(+1\) indica o vértice de destino do arco
\(0\) indica que o vértice não participa daquele arco

Exemplo Matriz de Incidência com grafo orientado G

Ordem dos vértices: (A, B, C, D, E)

\begin{array}{c|ccccc} & A & B & C & D & E \\\hline q & -1 & 1 & 0 & 0 & 0 \\ w & -1 & 0 & 1 & 0 & 0 \\ r & -1 & 0 & 0 & 1 & 0 \\ t & 0 & -1 & 1 & 0 & 0 \\ y & 0 & 0 & -1 & 1 & 0 \\ u & 0 & -1 & 0 & 0 & 1 \\ i & 0 & 0 & 0 & -1 & 1 \end{array}

Cada coluna representa um vértice e cada linha representa uma aresta (arco).

Matemática Discretapara Engenheiros

Matriz de Incidência

Grafo não orientado

Grafo orientado (mais usado em computação)

Exemplo Matriz de Incidência com grafo orientado G