Cognosco

Plus exigua via

Em maré de optmizações de situações concretas com o uso de grafos, eis algumas outras situações em que os grafos são usados para encontrar a melhor solução.

Imagine-se uma região que tem 4 localidades (A, B, C, D).
Cada aresta representa uma estrada entre as localidades (há 6 estradas no total).

Pretende-se encontrar a forma de passar por todas as cidades apenas uma vez (por exemplo, um serviço de carteiro, para distribuir cartas) e voltar à cidade de partida. Qual seria o caminho mais curto?

Este tipo de situação é o que se chama um circuito de Hamilton, em honra do Matemático que descreveu esta situação numa carta a um amigo.
Hamilton chegou a inventar um jogo, o Jogo de Hamilton, jogado num tabuleiro com a forma da planificação de um dodecaedro (ver Omnia factus mathematica sobre este e outros sólidos platónicos) em que cada jogador tem de percorrer todos os pontos do tabuleiro uma única vez e voltar ao ponto de origem. Não pode percorrer mais do que uma vez qualquer aresta nem repetir qualquer vértice, mas pode não percorrer todas as arestas. O objectivo do jogo é somente passar por todos os pontos uma só vez. Este é um circuito de Hamilton.

Mas o que se pretende aqui é percorrer todos os vértices mas da forma mais económica possível, uma vez que cada aresta tem um peso diferente (neste caso distância, podia ser tempo, custo, ...). Este tipo de problema é chamado de Problema do caixeiro viajante ou Problema do carteiro chinês.

Infelizmente não há uma forma de encontrar sempre o caminho mais curto o mais rapidadmente possível. A única forma de encontrar sempre a forma mais curta de percorrer todos os pontos é fazer uma lista de todos os circuitos possíveis, somar o peso de cada aresta e ver qual é o mais curto.
No caso do exemplo inicial, todos os circuito de Hamilton existentes são estes:
(comecei arbitrariamente por B. Começando por qualquer outro ponto os resultados seriam iguais, uma vez que todos estão listados)

• B - C - D - A - B 12 + 7 + 15 + 25 = 59 km
• B - C - A - D - B 12 + 18 + 15 + 8 = 53 km ←
• B - D - B - C - B 8 + 7 + 18 + 25 = 58 km
• B - D - C - B - B 8 + 15 + 18 + 12 = 53 km ←
• B - A - D - C - B 25 + 15 + 7 + 12 = 59 km
• B - A - C - D - B 25 + 18 + 7 + 8 = 58 km

Este caso é bastante simples e é possível listar todas as possibilidades (se se for sistemático de forma a não esquecer nenhum). Mas infelizmente o número de possibilidades cresce de forma explosiva à medida que aumenta o número de vértices.

Suponhamos que o grafo tem 4 vértices:
~ o número de circuitos diferente é 3 x 2 x 1 / 2 = 3.
Se o grafo tem 5 vértices:
~ o número de circuitos diferente é 4 x 3 x 2 x 1 / 2 = 12.
Se o grafo tem 6 vértices:
~ o número de circuitos diferente é 5 x 4 x 3 x 2 x 1 / 2 = 60.
...
Se o grafo tem 10 vértices:
~ o número de circuitos diferente é 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 / 2 = 181 440.
De um forma geral, se o grafo tem n vértices:
~ o número de circuitos diferentes é (n - 1)! / 2
O símbolo «!» significa que se multiplica o número por todos os números inteiros menores do que ele até 1 (5! = 5 x 4 x 3 x 2 x 1 = 120)
(Para mais sobre este símbolo e os métodos de contagem ver Caecus adnumeratio)

Até 5 vértices ainda se pode pensar em listar todos os circuitos e ver qual é o mais curto.
Mas a partir de 6 (360 circuitos diferentes) torna-se quase impossível fazê-lo.
Há alguns métodos para procurar encontrar o caminho mais curto (nenhum infalível e quando dão uma solução nem sempre é a mais curta, pode ser só uma solução que não é muito longe da ideal).

Um deles é listar as arestas por ordem crescente de arestas, depois escolher um ponto de partida, e seguidamente começar a escolher as arestas mais curtas que se ligam ao pontos a que se chega. Por exemplo, no grafo ao lado:

DE 7
AE 8
AD 12
BC 14
BE 18
CE 19
DC 25
AB 37

Comecemos pelo ponto A.
A aresta mais curta que se liga a A é AE (8).
A aresta mais curta que liga E a um ponto livre é DE (7)
A aresta mais curta que liga D a um ponto livre é DC (25)
A aresta mais curta que liga C a um ponto livre é BC (14)
Todos os pontos já foram percorridos. Só falta regressa a A com AB (37)

Obtém-se o circuito A - E - D - C - B - A.
No total o trajecto tem um comprimento de 8 + 7 + 25 + 14 + 37 = 91 km.
Mais uma vez podia ser simples encontrar o caminho por tentativa e erro, mas para grafos maiores (e mais reais) pode ser muito complicado.

A situação é também diferente no caso de o que se pretende ligar entre as cidades não for estradas mas electricidade, ou gás, ou água ou computadores,... redes de coisas que bastam ter uma ligação a um ponto da rede para estarem ligados.

No caso destas 4 cidades, para se viajar por todos os ponto teria de se contornar o quadrado (A-B-C-D), resultando num circuito de comprimento 5 + 9 + 10 + 2 = 26.
Mas para ligar em rede bastava ligar A-B (5) ; A-C (7) ; C-D (2), resultando num comprimento de 5 + 7 + 2 = 14.

Para se encontrar a melhor rede nestes casos (que, mais uma vez, pode não resultar sempre na melhor rede, mas nunca fica longe dela) será listar todas as arestas por ordem crescente de comprimento, escolher o ponto inicial e ligar as arestas mais curtas que unam pontos já na rede que se está a construir a outros que não estejam.
Neste caso
AD 2
AB 5
AC 7
BC 9
DC 10

Comecemos por A.
A aresta mais curta que liga A a um ponto livre é AB (5);
A aresta mais curta que liga um ponto já escolhido (A ou B) a um livre é AC (7);
A aresta mais curta que liga um ponto já escolhido (A ou B ou C) a um livre é CD (2);

A rede mais curta é então D - C - A - B, que tem 5 + 7 + 2 = 14 de comprimento.

E assim, com poucas contas, se consegue encontrar o caminho mais curto para uma viagem de férias, ou a forma mais económica de fazer uma rede de computadores em casa ou na empresa,...

A via mais curta