Teoria dos Grafos → Representação Computacional

Seja \(G = (V, A)\) um grafo com \(V = \{v_1, v_2, \dots, v_n\}\). A matriz de adjacência de \(G\) é a matriz

\[ M = (m_{ij}) \in \mathbb{R}^{n \times n} \] definida por

m_{ij} = \begin{cases} 1, & \text{se existe uma aresta (ou arco) de } v_i \text{ para } v_j, \\ 0, & \text{caso contrário.} \end{cases}

Cada entrada \(m_{ij}\) indica se os vértices \(v_i\) e \(v_j\) estão adjacentes no grafo.

Arcos no grafo (pela figura):

A → B (q) A → C (w) A → D (r) B → C (t) B → E (u) C → D (y) D → E (i)

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

Seja G = (V, A) com V = {A, B, C, D, E}. A matriz de adjacência de G é:

M= \begin{pmatrix} 0&1&1&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&0&0&0 \end{pmatrix}

Cada entrada \(m_{ij}\) indica se existe um arco do vértice \(v_i\) para o vértice \(v_j\):

Exemplos (batem com o grafo):
\(m_{AB}=1\) indica o arco A → B (q).
\(m_{EA}=0\) indica que não existe arco E → A.

Matemática Discretapara Engenheiros