O que é um grafo?

O que é um grafo? Se você nunca ouviu falar nisso antes, esta é certamente uma pergunta que você deve estar se fazendo. Vamos tentar matar sua curiosidade contando como foi que a teoria dos grafos surgiu.

Figura 1.1: Mapa de Königsberg

A Literatura afirma que a teoria dos grafos começou na cidade de Königsberg em 1736 pelo grande  matemático suíço Leonhard Euler (1707-1783). A cidade era cortada pelo rio Pregel, que possuía duas ilhas (figura 1.1). Como era muito complicado fazer o transporte de cargas e pessoas através de barcos,  algumas pontes foram construídas para auxiliar neste deslocamento entre as ilhas e as duas margens. Após algum tempo as pessoas começaram a se perguntar se era possível sair de sua casa, passar por cada ponte exatamente uma vez e voltar para a segurança de seu lar.

Para resolver o problema, Euler montou um diagrama que representasse o mapa da cidade. Ele o fez da seguinte maneira: A cada ilha e margem ele associou a um ponto que chamaremos de vértice e a cada ponte uma ligação que chamaremos de aresta. Com isso, ele obteve a figura 1.2:

Figura 1.2: Diagrama de Euler

Essa figura com vários pontos (vértices) e algumas ligações (arestas) que denominamos um grafo. Para finalizar seu raciocínio, Euler percebeu que existiam vértices com exatamente três arestas incidentes. Por outro lado, como os moradores queriam atravessar cada ponte apenas uma vez, cada vértice deveria ter um número par arestas. Logo, se tornaria impossível fazer um percurso seguindo as regras impostas pelos moradores.

Grafo

Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as restas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".

Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.

Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade.

Grafos têm sido utilizados para representar o formalismo das redes complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido.

Tipos e Classificações de Grafos

Uma possível definição para grafos: "O grafo propriamente dito é uma representação gráfica das relações existentes entre elementos de dados. Ele pode ser descrito num espaço euclidiano de n dimensões como sendo um conjunto V de vértices e um conjunto A de curvas contínuas (arestas)". Podemos avaliar um grafo através de seu tipo, propriedades e aplicações.

• Grafo simples é um grafo não direcionado, sem laços e que existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

• Grafo completo é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

• Grafo nulo é o grafo cujo conjunto de vértices é vazio.

• Grafo vazio é o grafo cujo conjunto de arestas é vazio.

• Grafo trivial é o grafo que possui apenas um vertice e nenhuma aresta.

• Grafo regular é um grafo em que todos os vértices tem o mesmo grau.

• Multigrafo é um grafo que permite múltiplas arestas ligando os mesmos vértices (arestas paralelas).

• Laço (loop) num grafo ou num digrafo é uma aresta e em E cujas terminações estão no mesmo vértice.

• Pseudografo é um grafo que contém arestas paralelas e laços.

• Ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Umciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.

• Ponto de articulação ou Vértice de corte é um vértice cuja remoção desliga um grafo. Uma ponte é uma aresta cuja remoção desliga um grafo. Um componente bi-conectado é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O contorno de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, infinito.

 

• Árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz. Árvores são comumente usadas como estruturas de dados em informática.

• Floresta é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.

• Subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G

• Subgrafo gerador é aquele obtido pela remoção de uma ou mais arestas de um outro grafo, dizemos então que este novo grafo obtido é gerador do primeiro.

• Subgrafo induzido é obtido pela remoção de vértices e consequente das arestas relacionadas com ele de um outro grafo, dizemos que este novo grafo é um grafo induzido do original.

• Grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.

• Clique em um grafo é um subgrafo que também é um grafo completo. No grafo do exemplo acima, os vértices 1, 2 e 5 formam um clique.

• Conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.

• Grafo planar é aquele que pode ser representado em um plano sem qualquer intersecção entre arestas. O grafo do exemplo é planar; o grafo completo de n vértices, para n> 4, não é planar.

• Caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.

• Caminho euleriano em um grafo é o caminho que usa cada aresta exatamente uma vez. Se tal caminho existir, o grafo é chamado atravessável. Um ciclo euleriano é um ciclo que usa cada aresta exatamente uma vez.

• Caminho hamiltoniano em um grafo é o caminho que visita cada vértice exatamente uma vez. Um ciclo hamiltoniano é um ciclo que visita cada vértice uma só vez. O grafo do exemplo contém um caminho hamiltoniano. Enquanto determinar se um dado grafo contém um caminho ou ciclo euleriano é trivial, o mesmo problema para caminhos e ciclos hamiltonianos é extremamente árduo.

 

• Lema do aperto de mãos diz que se os convidados de uma festa apertarem as mãos quando se encontrarem pela primeira vez, o número de convidados que apertam a mão um número ímpar de vezes é par. Também em grafos não direcionados a soma dos graus de todos os vértices é igual ao dobro do número de arestas.

• Grafo bipartido é o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Para um grafo ser bipartido ele não pode conter circuitos de comprimento ímpar. 

• 1. Se um grafo G é bipartido, todo o circuito de G possui comprimento par. 

• Sejam V1 e V2 os dois conjuntos em que, de acordo com a definição de grafo bipartido, se particiona V(G). Toda a aresta de G conecta um vértice em V1 com outro em V2. Assim sendo, se X for um vértice de V1, para “voltar” a esse vértice terá de se ir a V2 e voltar a V1 um número indeterminado de vezes, e de cada vez serão percorridas duas arestas, uma de um vértice em V1 para um vértice em V2 e outra de um vértice em V2 para um vértice em V1. Logo, o número de arestas a percorrer será par, ou seja, o comprimento do circuito é par. 

• 2. Se todo o circuito de um grafo G possui comprimento par, então o grafo é bipartido. 
• Seja G um grafo em que todo o circuito tem comprimento par, e seja X um vértice de G. Denotemos por V1 o conjunto formado por X e por todos os vértices cuja distância a X é par. Seja V2 = V(G)\V1 (isto é, o conjunto formado pelos vértices de G que não pertencem a V1). Pretende mostrar-se que não existe qualquer aresta que conecte vértices de V1 ou vértices de V2. Suponhamos a existência de tal aresta, isto é, suponhamos a existência de dois vértices em V1 (ou V2), digamos Xi e Xj, conectados por uma aresta. Ora existe já um caminho de comprimento par entre Xi e Xj, já que existem caminhos, ambos de comprimento par (ou ímpar, no caso de Xi e Xj pertencerem a V2), entre Xi e X e entre X e Xj. Se a esse caminho juntarmos a aresta {Xi;Xj} obtemos um circuito de comprimento ímpar o que contraria a hipótese de apenas existirem circuitos de comprimento par.

• Grafo bipartido completo é o grafo bipartido, cujo qualquer vértice do primeiro conjunto é adjacente a todos vértices do segundo conjunto 

• Grafo k-partido ou grafo de k-coloração é um grafo cujos vértices podem ser particionados em k conjuntos disjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Um grafo 2-partido é o mesmo que grafo bipartido. 

• Emparelhamento de grafos consiste em partir o grafo em conjuntos de vértices a qual não compartilham nenhuma aresta entre eles. 

• Teorema das quatro cores é baseado no problema das cores necessárias para se colorir um mapa sem que os países vizinhos compartilhem da mesma cor. Transformando o mapa em um grafo pode-se provar que pode-se representar qualquer mapa (um grafo planar) com apenas 4 cores (4 partições). 

• Percurso árvores: 

• Percorrimento sistemático em todos os vértices e arestas do grafo. Grafo pode ser dirigido ou não. 
• O percurso em árvores é o processo de visitar cada nó da árvore exatamente uma vez. 
• O percurso pode ser interpretado como colocar todos os nós em uma linha, não existe uma ordem para ser seguida. 
• Existem n percursos diferentes, quase todos caóticos. 
• Os básicos são percurso em profundidade e percurso em largura 
• Fila: busca em largura 
• Pilha: busca em profundidade

• Busca em extensão ou largura: (Breadth-First Search ou BFS). 

• A propriedade especial está no fato de a árvore não possuir ciclos: dados dois vértices quaisquer, existe exatamente 1 caminho entre eles. Um percurso em extensão é visitar cada nó começando do menor nível e move-se para os níveis mais altos nível após nível, visitando cada nó da esquerda para a direita. Sua implementação é direta quando uma fila é utilizada. Depois que um nó é visitado, seus filhos, se houver algum, são colocados no final da fila e o nó no início da fila é visitado. Assim, os nós do nível n+1 serão visitados somente depois de ter visitados todos os nós do nível n. Computa a menor distância para todos os vértices alcançaveis. O sub-grafo contendo os caminhos percorridos é chamado de breadth-first tree. 

• Busca em profundidade (Depth-first search ou DFS). 
• Um algoritmo de busca em profundidade realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos (nó folha). Então a busca retrocede (backtrack) e começa no próximo nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração. A complexidade espacial de um algoritmo de busca em profundidade é muito menor que a de um algoritmo de busca em largura. A complexidade temporal de ambos algoritmos são proporcionais ao número de vértices somados ao número de arestas dos grafos aos quais eles atravessam. Quando ocorrem buscas em grafos muito grandes, que não podem ser armazenadas completamente na memória, a busca em profundidade não termina, em casos onde o comprimento de um caminho numa árvore de busca é infinito. O simples artifício de “ lembrar quais nós já foram visitados ” não funciona, porque pode não haver memória suficiente. Isso pode ser resolvido estabelecendo-se um limite de aumento na profundidade da árvore.

Um caso específico: O Algoritmo de Dijkstra

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.

O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo P um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores caminhos dos vértices alcançáveis pelo vértice inicial determinando todos os melhores caminhos intermediários. Nota: diz-se 'um menor caminho' pois caso existam 2 'menores caminhos' apenas um será descoberto.

O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas.

Um exemplo prático do problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho?

O Cálculo do Caminho de Custo Mínimo

Algoritmo de Dijkstra para cálculo do Caminho de Custo Mínimo

O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de performance. Ele não garante, contudo, a exatidão da solução caso haja a presença de arcos com valores negativos.

Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto.

Algoritmo: Seja G(V,A) um grafo orientado e s um vértice de G:

1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às demais estimativas;
2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice que precede t no caminho de custo mínimo de s para t);
3. Enquanto houver vértice aberto:
   • seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos;
   • feche o vértice k
   • Para todo vértice j ainda aberto que seja sucessor de k faça:
     • some a estimativa do vértice k com o custo do arco que une k a j;
     • caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote k como precedente de j.

A seqüência de diagramas^*  ilustra o funcionamento do Algoritmo de Dijkstra.

Inicialmente todos os nodos tem um custo infinito, exceto s (a raiz da busca) que tem valor 0: vértices s u v x y estimativas 0 ¥ ¥ ¥ ¥ precedentes - - - - -
selecione s (vértice aberto de estimativa mínima) feche s recalcule as estimativas de u e x vértices s u v x y estimativas 0 10 ¥ 5 ¥ precedentes s s - s -
selecione x (vértice aberto de estimativa mínima) feche x recalcule as estimativas de u,v e y vértices s u v x y estimativas 0 8 14 5 7 precedentes s x x s x
selecione y (vértice aberto de estimativa mínima) feche y recalcule a estimativa de v vértices s u v x y estimativas 0 8 13 5 7 precedentes s x y s x
selecione u (vértice aberto de estimativa mínima) feche u recalcule a estimativa de v vértices s u v x y estimativas 0 8 9 5 7 precedentes s x u s x
selecione v (vértice aberto de estimativa mínima) feche v vértices s u v x y estimativas 0 8 9 5 7 precedentes s x u s x

Quando todos os vértices tiverem sido fechados, os valores obtidos serão os custos mínimos dos caminhos que partem do vértice tomado como raiz da busca até os demais vértices do grafo. O caminho propriamente dito é obtido a partir dos vértices chamados acima de precedentes.

Para exemplificar, considere o caminho de custo mínimo que vai de s até v, cujo custo mínimo é 9. O vértice precendente de v na última das tabelas acima é u. Sendo assim, o caminho é:

s ® ... ® u ® v

Por sua vez, o precedente de u é x. Portanto, o caminho é:

s ® ... ® x ® u ® v

Por último, o precedente de x é o próprio vértice s. Logo, o caminho de custo mínimo é:

s ® x ® u ® v

Como apresentado o algoritmo de Dijkstra computa apenas um único caminho de custo mínimo entre um dado par de vértices. Para se obter todos os caminhos de custo mínimo entre dois vértices é necessário modificar a forma de anotação dos precedentes. A modificação no passo 3 indicada a seguir é suficiente para permitir o cômputo de todos os caminhos por um processo similar ao descrito acima.

...

Para todo vértice j ainda aberto que seja sucessor de k faça:

• some a estimativa do vértice k com o custo do arco que une k a j;
• caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote k como precedente único de j;
• caso esta soma seja igual à estimativa anterior para o vértice j, adicione k ao conjunto dos precedentes de j;

Supondo que o peso do arco (y,v) no grafo acima fosse 2, haveriam dois caminhos de custo mínimo do vértice s para v. Esta duplicidade resulta em dois precedentes para o vértice v:

vértices	s	u	v	x	y
estimativas	0	8	9	5	7
precedentes	s	x	u,y	s	x

Sendo assim, os dois caminhos são dados por: (s ® ... ® u ® v) e (s ® ... ® y ® v). Seguindo as precedências para u e y nestes dois casos obtemos os dois caminhos: (s ® x ® u ® v) e (s ® x ® y ® v).

O Algoritmo

Algoritmo de Dijkstra

• 1º passo: iniciam-se os valores: 

V[G] é o conjunto de vértices(v) que formam o Grafo G. d[v] é o vetor de distâncias de s até cada v. Admitindo-se a pior estimativa possível, o caminho infinito. π[v] identifica o vértice de onde se origina uma conexão até v de maneira a formar um caminho mínimo.

• 2º passo: temos que usar dois conjuntos: S, que representa todos os vértices v onde d[v] já contem o custo do menor caminho e Q que contem todos os outros vértices

• 3º passo: realizamos uma série de relaxamentos das arestas, de acordo com o código:

w(u, v) é o peso(weight) da aresta que vai de u a v.

u e v são vértices quaisquer e s é o vértice inicial.

extrair-mín(Q), pode usar um heap de mínimo ou uma lista de vértices onde se extrai o elemento u com menor valor d[u].

No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G. O algoritmo leva tempo O(m + n log n) caso seja usado um heap de Fibonacci, O(m log n) caso seja usado um heap binário e O(n²) caso seja usado um vetor para armazenar Q.

Implementação em C++

Implementação em C/C++

• Implementação em C utilizando uma matriz de adjacências. Dependendo da quantidade limite de vértices (MAXV) pode se tornar ineficiente quanto ao uso de memória, sendo recomendado usar uma lista de adjacências

• Implementação em C++ utilizando uma lista de adjacências.

A implementação do algoritmo utilizando uma lista de adjacências é ligeiramente mais rápida que a implementação com uma matriz de adjacências para casos em que o número de arestas não se aproxima do pior caso (uma aresta ligando cada par de vértices); quando próximo ao pior caso, o desempenho é similar. Ambos possuem complexidade de tempo em torno de O(V²).

É possível obter uma solução em O(E + V log V) (custo amortizado), onde E é o número de arestas, utilizando um heap de fibonacci ou O(E log V) usando priority queue da STL de C++ para extrair o vértice não-visitado com menor distância. O heap simples, embora levemente mais lento que o heap de fibonacci, também pode ser usado para obter uma complexidade similar.