A Introdução à Teoria de Grafos

Introdução à Teoria dos Grafos

Um grafo é um par ordenado G = (V, E), no qual V seriam os conjuntos vértices e E os conjuntos de arestas. Essa determinação facilita a modelagem de alguns problemas como exemplificado na aula pela 7 pontes de Königsberg, essas modelagens podem ser feitas de diversas maneiras, formando assim alguns tipos de grafos com certas propriedades, como grafo simples, não direcionado, não ponderado, direcionado, ponderado e multigrafo, sendo estas propriedades de como o grafo se porta, entretanto, há as propriedades como ordem, sendo esta o número de vértices; tamanho, número de arestas; diâmetro, o maior caminho entre os caminhos mais curtos que unem cada par de vértices; conectividade de vértices, o menor número de vértices que se removidas desconectam o grafo; conectividade de arestas, o menor número de arestas que se removidas desconectam o grafo; grau do vértice, número de arestas de um determinado vértice. A importância dessas propriedades é de muita importância, visto que com essas informações é possível encontrar a robustez da rede à ataques ou falhas.

[pic 1]

A aplicação de grafos é capaz de otimizar alguns problemas como o caminho mais curto entre alguns pontos, captar o caminho mais rápido entre pontos, como por exemplo o problema clássico do caixeiro viajante. É possível modelar esses problemas com grafos ponderados, utilizando como peso o tempo ou distância entre os vértices, sendo estes as cidades. Por subsequente é possível calcular o número de rotas possíveis para n cidades, isto é R(n) = (n - 1)!, entretanto o tempo de processamento cresce exponencialmente com o número de cidades, contudo existem aproximações mais rápidas chamadas de heurísticas. O fluxo máximo de canais também podem ser modelados em grafos, como por exemplo um rede de drenagem subterrânea para evitar inundações, o tráfego de um website para evitar sobrecarregamento entre outros, evidenciando a importância e qualidade da utilização de grafos para fazer análises de risco ou conectividade.

        Para a utilização de grafos em algum sistema computacional é necessário que os grafos sejam representados de alguma maneira na memória do computador, não pode ser apenas uma figura. Dessa forma, há duas técnicas básicas para representar grafos, a matriz de adjacências e a lista de adjacências. Para a formação da matriz de adjacência é formado uma matriz (n,n) e as conexões são entre os vértices é assinalada pelo bit 1, já a ausência de conexão pelo bit 0. A lista de adjacências é o encadeamento dos n vértices e as suas respectivas conexões em forma de lista, como representado na figura abaixo.

[pic 2] 

  Quando se trata de grafos simples, sem direcionamento entre os vértices, uma matriz A(i,j) é igual a uma matriz A(j,i), entretanto em grafos direcionados há a diferença entre essas matrizes.

[pic 3]                           [pic 4]
[pic 5]