Teoria de Redes ou Grafos. Conceitos Básicos

Teoria de Redes ou Grafos. Conceitos Básicos
 

Diversos problemas de programação Linear podem ser modelados como problemas de fluxo de redes.

Definição 1:

Um grafo (rede) linear consiste em diversos nós, ou pontos, sendo que cada nó deve estar conectado a um ou mais nós por arcos.

Definição 2:

Um grafo directo ( ou rede directa) é um grafo em que o fluxo ao longo de um arco pode ser efectuado em apenas num sentido.

Nota: Pode-se substituir um arco com fluxo nos dois sentidos, por dois arcos em sentidos opostos. Desta forma podemos utilizar redes directas sem que o modelo esteja perdendo a sua generalidade.

Definição 3:

Um grafo bipartido é um grafo directo onde os nós são divididos em dois subconjuntos, onde todos os arcos do grafo ligam um nó de um subconjunto a um nó do outro. Ou seja, todos os arcos ligam nós das origens a nós dos destinos.

Definição 4:

Um caminho ou um canal é um conjunto ordenado de arcos que conectam dois nós através de nós intermédios, cada um dos quais estando exactamente em dois arcos do canal.

Definição 5:

Um grafo conectado é um grafo no qual existe caminho entre qualquer par de nós. O exemplo de um grafo conectado é o grafo da figura 1.

Definição 6:

Um laço é um canal que conecta um nó a ele mesmo.

.

Definição 7:

Uma árvore é um grafo conectado que não contém laços.

Problema do Fluxo Máximo

Um problema de rede usual é a determinação do fluxo máximo entre dois pontos em uma rede. Considere o seguinte exemplo:

“ Um produtor de gás natural tem uma rede de tubagem conforme é apresentada na figura abaixo. As capacidades de cada parte da rede estão representadas em bilhões de litros por dia. Um problema ocorreu no ponto T, de modo que deseja-se fornecer a maior quantidade de gás possível da produção ao ponto T.

Por tanto, o problema é encontrar a máxima capacidade da rede entre o ponto S e T de modo que a máxima quantidade seja fornecida de S para T.”

Problema do Caminho Mínimo

Um problema bastante comum envolvendo a teoria dos grafos é o problema da rota mais curta, ou caminho mínimo.

Para cada arco de um grafo, define-se a distância que ele representa. O objectivo deste tipo de problema é encontrar o caminho mais curto entre dois nós.

O problema do caminho mínimo pode ser utilizado também para representar custos ou tempos mínimos, em vez de distâncias.

O algoritmo para a solução de problemas de caminho mínimo que será estudado, é o algoritmo de Dijkstra: Este algoritmo determina a distância mínima entre o vértice de origem (S) e os demais vértices.

Para melhor apresentar o algoritmo de Dijkstra vamos analisar o grafo da seguinte figura:

                                           

BIBLIOGRAFIA

- TAHA, Hamdy A. (2008) Pesquisa Operacional: Uma Visão Geral. 8ª Edição. São Paulo. Pearson Prentice Hall.

- Hillier F. S., Lieberman G. J. (2010) Introdução à Pesquisa Operacional. 8ª Edição. Editoras Mc Graw Hill e bookman.

- GOLDBARG, M.C. LUNA, H.P.L. (2005) Otimização Combinatória e Programação Linear. Modelos e Algoritmos. 2ª Edição. Editora Campus.