Grafo Direcionado (Dígrafo)
Um dígrafo D(V,E) é um conjunto finito não vazio V (vértices) e um conjunto E (arestas) de pares ordenados de vértices distintos.
Cada aresta (v,w) possui uma única direção de v para w.
(v,w) é divergente de v e convergente a w.
grau de entrada de v: número de arestas convergentes a v
grau de saída de v: número de arestas divergentes de v
sumidouro: um vértice com grau de saída nulo
fonte: um vértice com grau de entrada nulo
Grafo subjacente de um dígrado D é o grafo obtido pela retirada das direções das arestas
Dígrafo Fortemente Conexo
Quando para todo par de vértices v, w pertencente a V existir em D um caminho de v para w e também de w para v.
Se existir pelo menos um desses caminhos, D é chamado unilateralmente conexo. O dígrafo D é fracamente conexo ou desconexo, conforme seu subgrado adjacente seja conexo ou desconexo, respectivamente.
Então, um dígrafo que é fortemente conexo também é unilateralmente e fracamente conexo.
Dígrafo Acíclico
Não possui ciclos. Observe que o grafo subjacente a um dígrafo acíclico não é necessariamente acíclico, mas, se o grafo subjacente é acíclico, seu dígrafo também o é.
Árvore Direcionada Enraizada
Matriz de Adjacências
n - número de vértices
A matriz de adjacências representa um grafo sem ambiguidade.
R é simétrica para um grafo não direcionado.
Uma matriz de adjacências caracteriza unicamente um grafo, contudo a um mesmo grafo G podem corresponder várias matrizes diferentes.
Matriz de Adjacências para Dígrafos
Matriz de Incidências
bij = 1 se vértice vi e aresta ej forem incidentes
A matriz de adjacências representa univocamente um grafo, mas este último pode ser representado, em geral, por várias matrizes de incidências diferentes.
Note que cada coluna de B tem exatamente dois 1's.
Colunas da Matriz de Adjacências:
Estrutura de Adjacências
Todo dígrafo acíclico possui pelo menos uma fonte e um sumidouro.
É um dígrafo D tal que exatamente um vértice r possui grau de entrada nulo, enquanto todos os demais vértices possuem grau de entrada igual a um.
Representação de Grafos
Dado um grafo G, a matriz de adjacências r=(rij) é uma matriz n x n tal que:
rij = 1 se (vi,vj) pertence a E
rij = 0 cc
ou seja, rij = 1 quando os vértices vi, vj forem adjacentes e rij = 0 caso contrário.
O número de 1's é igual a 2m, onde m é o número de vértices
Tomando rij=1 se (vi,vj) for aresta divergente de vi e convergente a vj; e rij=0, caso contrário a matriz não é mais (necessariamente) simétrica e o número de 1's é exatamente igual a m (número de arestas).
Seja G(V,E) um grafo, define-se a matriz de incidências B=(bij) uma matriz n x m tal que:
bij = 0 caso contrário
(1,2) (1,3) (1,6) (1,5)
(2,3) (2,6)
(3,5) (3,6)
(4,5)
(5,6)
(4,6)
(3,4)
A estrutura de adjacências A de G(V,E) é um conjunto de n listas A(v), uma para cada vértice v pertencente a V. Cada lista A(v) é denominada lista de adjacências do vértice v e contém os vértices w adjacentes a v em G, ou seja:
A(v)={w / (v,w) pertence a E}
Árvore m-ária
Coloração em Grafos