Problema de fluxo em redes

CAPÍTULO 7

Problemas de Fluxo em Redes

1. Conceitos fundamentais de grafos
Em muitos problemas que nos surgem, a forma mais simples de o descrever, é representá-lo em forma de grafo, uma vez que um grafo oferece uma representação visual que trará vantagens na construção de um modelo matemático com vista à resolução do problema.
Um grafo é uma estrutura constituída por dois conjuntos finitos : de vértices (nós ou nodos) e de arestas (arcos ou ramos). Um grafo pode ser representado por G = (N, A), em que N = {1, ..., n} e A
= {1, ..., m} são os conjuntos de vértices e arestas, respectivamente, em que (A ⊆ N×N).
Cada aresta é representado por um par (i, j), com i ≠ j e i, j ∈ N, em que i é o vértice origem e j o vértice destino. Uma aresta (i, j) diz-se não dirigida (não orientada), se (j, i) ∈ A e diz-se dirigida
(orientada), se (j, i) ∉ A.
Existem 3 tipos de grafos :
• orientado (dirigido)  todas as arestas são dirigidas,
• não orientado (não dirigido)  todas as arestas são não dirigidas e,
• misto  algumas arestas são dirigidas e outras são não dirigidas.

Um grafo diz-se completo, se entre quaisquer dois vértices existir uma aresta dirigida (grafos dirigidos) ou não dirigida (grafos não dirigidos).
A densidade de um grafo é a razão entre a quantidade de arestas do grafo e a quantidade de arestas do grafo completo com o mesma quantidade de vértices.
Dois vértices são adjacentes (vizinhos), se estiverem ligados por uma aresta. Duas arestas são adjacentes se forem ambas incidentes relativamente ao mesmo vértice. Um vértice é de ordem k, se tiver k arestas a ele adjacente.

90

Conceitos fundamentais de redes
Considere-se dois vértices, S e T, do grafo G. Um caminho de S para T, é uma sucessão de

vértices e arestas, p = [S = n1, (n1, n2), n2, ..., (nh-1, nh), nh = T]. No entanto, aquele caminho também pode ser representado apenas pela sucessão de vértices (p = [S = n1, n2, ..., nh-1, nh = T]) ou de arestas
(p = [(S, n2), ...,