Resultados da teoria de grafos

Alguns resultados da teoria de grafos para o problema de redes.

A especialização do algoritmo simplex primal de George Dantzig para o problema de fluxo em rede com custo mínimo PL é de grande importância, pois o método simplex primal pode ser realizado diretamente na rede eliminando o peso computacional na atualização da inversa da matriz básica.
Antes da formulação para problema PL especializado, alguns conceitos de rede serão apresentados.
Uma rede pode ser representada por um grafo G que consiste de um conjunto finito [] de nós e arcos respectivamente.
Uma rede contendo nós e arcos deve possuir nós e arcos ordenados de forma que exista uma correspondência biunívoca entre os nós da rede e os números inteiros, com 1,.., . A mesma correspondência biunívoca deve existir para os arcos da rede, com 1,.., .
A estrutura da rede é ilustrada através da figura III-1, onde os nós são representados por círculos e os arcos por segmentos de linha orientados que conectam dois nós. A seta no segmento de linha indica a direção de fluxo no arco da rede. Por exemplo, o primeiro arco está direcionado a partir do nó 1 na direção do nó 5.

2
3
1
5
4
1
8 2
7
6
5
4
3
2
3
1
5
4
1
8 2
7
6
5
4
3

Figura III-1 – Representação de uma rede através de um grafo G.

A estrutura da rede pode também ser descrita por uma mátria A de dimensão Ix, definida como segue

A matriz A definida acima é chamada de matriz de incidência nó-arco. A matriz de incidência A, correspondente à rede da figura III-1, é mostrada a seguir: 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
Nós
Nós Arcos Arcos

A =

A característica dessa matriz é que cada coluna possui exatamente duas entradas não nulas, uma entrada (+1) e a outra (-1).
As definições de