Grafos

1. GRAFOS

De acordo com Lucchesi (1979) muitas situações podem ser descritas através de diagramas que consistem de um conjunto de pontos, juntamente com linhas que ligam alguns pares destes pontos. Podendo estes pontos representar pessoas, e as linhas pares de amigos; os pontos também podem representar centros de comunicações, as linhas ligações entre os centros. A abstração matemática de situações desse tipo é chamada de grafo G (V,A), onde um grafo G consiste de um conjunto finito V de elementos chamados vértices, um conjunto finito A de elementos chamados arestas, podendo ser representados por diagramas, onde cada vértice é representado por um ponto e cada aresta por uma linha ligando os pontos que representam seus extremos.

Em resumo Grafo: é uma noção simples, abstrata e intuitiva, usada para representar a idéia de alguma espécie de relação entre os objetos. Graficamente, aparece representado por uma figura com nós ou vértices, significando os objetos, unidos por um traço denominado aresta configurando a relação imaginada.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou dígrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial. Existem também outros tipos de grafos como: Grafo simples que não contém laços nem duas ligações distintas com o mesmo par de extremos; grafo completo é um grafo simples em que quaisquer dois vértices distintos são adjacentes; triângulo é um grafo completo com três vértices.

Um grafo é representado matematicamente por: G = (V,A)

Onde V é o conjunto de vértices e A é o conjunto de arestas ou ligações entre os vértices. (|V| = n, |A| = m).

Onde: n = |V| é a ordem do grafo

m = |A| é o tamanho do grafo.

Se m = 0 o grafo é dito trivial.

Exemplo 1:

A figura acima mostra o grafo G (V, A). Observe que laços (self-loops) são permitidos pela definição. Múltiplas linhas não são permitidas. Neste exemplo, V = {1, 2, 3, 4, 5, 6} e A = {{1,3}, {2,3} {3,4}, {3,5}, {6,6}}. É comum a utilização da variável vi ou xi, i = 1, 2, ..., n para a distinção dos nós (vértices). |V| = 6, |E| =5.

Exemplo 2:

Seja o grafo G(V,A) dado por:

V = { p | p é uma pessoa}

A = { (u,v) | < u é amigo de v > }

Seja o exemplo:

V = {Maria, Pedro, Joana, Luiz}

A = {(Maria, Pedro), (Joana, Maria), (Maria, Luiz), (Pedro, Luiz), (Joana, Pedro)}

Construa o grafo do exemplo acima.

No cotidiano, os grafos são utilizados em diferentes áreas do conhecimento, tais como Administração, Economia, Informática, Física, Química, entre outras. Assim suas aplicações vão desde a definição de redes de distribuição de mercadorias, onde as vértices são os pontos de entrega e as arestas (com pesos) são estradas, organização de roteiros com menor custo; definição de horários ou de sequencias de tarefas, ou seja, é usado para encontrar soluções ótimas para as mais variadas situações.

2. PROBLEMA DO CAMINHO MINIMO

O problema do caminho mínimo consiste basicamente: dado um grafo com pesos nas arestas, obter o caminho de menor custo entre dois vértices x e y. Como muitas vezes o peso representa a distância entre os vértices este problema passou a ser conhecido como problema do caminho mínimo.

O valor do caminho mínimo dentre dois vértices quaisquer x e y pode passar também por outros vértices, sendo que, para se chegar a y vindo de x com um custo mínimo primeiramente temos que chegar de x a estes vértices que se encontram no meio do caminho também com o custo mínimo. Exemplificando, sabe-se que a menor distância para se chegar de Belo Horizonte a Curitiba passa por Campinas, então o caminho dentre Belo Horizonte e Campinas também é o menor possível, assim como o caminho de Campinas a Curitiba.

Portanto concluímos que para se resolver o problema do menor caminho dentre dois vértices x e y primeiro precisamos resolver todos os “subproblemas” de se chegar de x a algum vértice dentre x e y, armazenando seus custos. Esta é a abordagem utilizada pelo algoritmo de Floyd-Warshall, primeiramente resolvemos todos os subproblemas para então encontrarmos um resultado para o problema em si. Este princípio também é uma das características de uma técnica de programação conhecida como Programação Dinâmica.

Pode-se dizer também que num dígrafo com custos nos arcos, o custo de um caminho é a soma dos custos dos arcos do caminho. Um caminho B é mais barato que um caminho C se tiver custo menor que o de C. Dizemos que um caminho C tem custo mínimo se nenhum caminho com a mesma origem e o mesmo término que C for mais barato que C.

Exemplo: O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância