otimizacao de rede, nocoes basicas e grafos

1. Introdução

Muitos problemas práticos da otimização podem ser mais bem analisados utilizando uma estrutura especial denominada grafo ou rede. Problemas de otimização em redes aparecem em diversas aplicações e em diversas formas. Como por exemplo transportes ou fluxo de um item ou itens de um nó a outro dentro da rede com um determinado objetivo.As aplicações são realizada na transmissão de mensagens em redes de comunicação de dados,no envio de água de uma rede de distribuição de água.Iremos elaborar alguns problemas que exibem uma estrutura especial,que pode ser explorada para o desenvolvimento de métodos mais eficientes de resolução.Em muitos problemas podemos identificar conjuntos de elementos fundamentais,os quais mantém uma relação entre si,como,por exemplo,um conjunto de cidades e um conjunto de estradas que interligam uma cidade diretamente,ou um conjunto de reservatórios e bairros em uma cidade.

2. Grafos e redes

Seja N um conjunto finito, cujos elementos são chamados de nós(ou vértices) e E um conjunto de pares de nós, cujos elementos(i,j)são chamados de arestas.O par G=(N,E)é chamado grafo.Uma rede é um grafo cujo nós e/ou arestas tem valores associados.Ou seja,um grafo é definido como sendo um par ordenado(V,A).Os elementos de V são denominados vértices ou nós do grafo e os pares ordenados de A,denominados de arestas do grafo. Um problema típico de transporte consiste em encontrar uma rota, partindo de uma origem para um destino, considerando que entre esses pontos existem diversas rotas alternativas e que se necessita minimizar ou maximizar alguma medida associada às arestas e/ou nós.

2.2 Aspectos importantes

Quando um arco é incidente a um único vértice, é denominado “laço”.
Dois vértices são considerados “adjacentes” se eles são interligados por uma aresta.
Uma “cadeia” é uma seqüência de arestas (orientados ou não).