Prévia do material em texto
Teoria dos Grafos: Problemas
Anderson Monte1 André F. Riker1 Thales Madeira1
1Programa de Pós-Graduação em Ciência da Computação
Universidade Federal do Pará (UFPA)
Belém – PA – Brasil
andersonxef@gmail.com, and_rik@hotmail.com, thales.bcc@gmail.com
1. Polígono
1.1. Identificação dos vértices e arestas:
O problema do polígono envolve os próprios grafos. Portanto, neste caso, não
cabe falar de algo que precisa ser representado através de um grafo, e sim de algo que o
grafo envolvido representa. Neste problema, é possível ver um grafo como um conjunto
de operadores de adição e multiplicação (“+” e “*”, repsectivamente), representados
pelas arestas, e de operandos, representados pelos vértices. As combinações entre os
vértices e as arestas geram operações matemáticas que, aos poucos, vão criando uma
expressão algébrica. Tal expressão, dado um mesmo grafo, pode variar, dependendo de
como as combinações entre os vértices e arestas são realizadas. Baseado neste contexto,
a solução do problema consiste em, basicamente, encontrar uma expressão algébrica,
utilizando os operandos e operadores dados pelo grafo envolvido, cujo resultado é o
maior número possível. Além disso, a solução encontrada também deve informar quais
arestas devem ser consideradas por primeiro, na resolução do problema, para que
resultado máximo possa ser obtido.
1.2. Solução do problema:
No problema do polígono, para criar uma expressão algébrica e descobrir o seu
respectivo resultado, é necessário, primeiramente, remover uma das arestas, pois o
número de arestas (operadores) e de vértices (operandos) é N, mas apenas N-1
operadores são necessários para formar uma expressão. Após este passo, os próximos
são realizados da seguinte forma, até que o resultado final seja obtido:
Escolher uma aresta E e dois vértices V1 e V2 que são ligados por E;
Substituir E, V1 e V2 por um novo vértice, rotulado com o valor resultante da
operação indicada por E sobre os valores V1 e V2.
As arestas e vértices de um grafo envolvido no problema do polígono
representam três tipos de elementos: números inteiros (operandos), operadores de
adição e operadores de multiplicação. Para solucionar tal problema, ou seja, para
encontrar uma expressão algébrica que resulte no maior número possível, é necessário
implementar um algoritmo que cria expressões de tal modo que, nesta última, as
operações de adição geralmente envolvam números pequenos, enquanto que as
operações de multiplicação deve envolver os maiores números possíveis. Entretanto, os
operandos negativos devem receber uma atenção especial, pois é preciso fazer com que
os resultados das operações com os mesmos resultem em números cada vez menores o
mínimo possível. Em outras palavras, o algoritmo para solucionar o problema deve
seguir as seguintes recomendações:
Para cada vértice com operando negativo no grafo e arestas incidentes na mesma
contendo operadores de multiplicação, deve-se efetuar as multiplicações até que
os resultados parciais se tornem números positivos ou nulos (ou seja, iguais a
zero), ou até que os vértices contendo os resultados parciais sejam incididos
apenas por arestas contendo operadores de adição.
As operações de adição que envolver números negativos devem ser efetuadas
por último.
As operações de adição que envolver apenas números positivos devem ser
efetuadas antes das operações de multiplicação que também envolvem apenas
tais tipos de números.
O algoritmo deve ser executado tantas vezes quanto o número de arestas
existentes no grafo, de modo que, a cada execução, uma aresta diferente seja
excluída no primeiro passo. Os resultados das execuções, juntamente com as
arestas excluídas no primeiro passo, devem ser armazenados para posterior
comparação. As execuções que atingirem o resultado máximo terão suas arestas
iniciais inclusas no conjunto de arestas que, se removidas na primeira jogada,
podem levar à pontuação máxima.
1.3. Exemplo de aplicação
Considerando o grafo abaixo:
O algoritmo, para este grafo, será executado da seguinte maneira:
Dados (N=4, “+ -7 + 4 * 2 * 5”)
ConjArestas = {1, 2, 3, 4};
Para i=1....n faça {
ResultadoAtual = 0;
ArestaAtual = ConjArestas[i];
Remover ConjArestas[i];
Enquanto (quantidade de operandos negativos > 0) ou (operadores de
multiplicação incidentes em operadores negativos > 0) faça
ResultadoAtual = ResultadoAtual + Efetuar operações de
multiplicação com os operandos negativos;
Enquanto (operadores de adição em números positivos > 0)
ResultadoAtual = ResultadoAtual + Efetuar operações de adição
em operandos positivos;
Enquanto (operadores de multiplicação em números positivos > 0)
ResultadoAtual = ResultadoAtual + Efetuar operações de
multiplicação em operandos positivos;
ResultadoAtual = ResultadoAtual + Efetuar operações de adição
envolvendo operandos negativos;
MaiorResultado = 0;
Se (MaiorResultado < ResultadoAtual) {
MaiorResultado = ResultadoAtual;
ConjArestasMaiorRes = ArestaAtual;
}
Se (MaiorResultado == ResultadoAtual) {
MaiorResultado = ResultadoAtual;
ConjArestasMaiorRes = ConjArestasMaiorRes + ArestaAtual;
}
}
Este algoritmo irá retornar os seguintes resultados para o referido grafo:
Removendo a Aresta 1: 5 * 2 * 4 + (-7) = 33;
Removendo a Aresta 2: 4 * 2 * 5 + (-7) = 33;
Removendo a Aresta 3: 2 * 5 + (-7) + 4 = 7;
Removendo a Aresta 4: 2 * 4 + (-7) + 5 = 6;
Portanto, a solução para este problema, retornada pelo algoritmo, indica que o
resultado máximo possível é 33 e que a remoção das arestas 1 e 2, na primeira jogada,
podem levar a este resultado.
2. Problema das Pontes de Königsberg
2.1. Representação do grafo
Vértices: cidades A, B, C, D.
Arestas: pontes a(A,B), b(A,B), c(A,C), d(A,C), e(A,D), f(B,D), g(C,D).
2.2. Técnica utilizada
As cidades são representadas pelos vértices e as pontes são arestas, pois
representam as ligações entre as cidades (vértices).
O problema consiste em afirmar se existe um caminho que passe por todas as
pontes (arestas) uma única vez.
A resolução consiste em desenhar um grafo que represente as cidades e as pontes
e verificar a existência de um caminho euleriano. Se houver um caminho euleriano entre
as arestas, então haverá um caminho entre as pontes.
Segundo o teorema: Um grafo contem um caminho euleriano, se e somente se,
tiver 2 vértices de grau ímpar.
2.3. Solução
Vértice A: grau 5, arestas incidentes: a,b,c,d;
Vértice B: grau 3, arestas incidentes: a,b,f;
Vértice C: grau 3, arestas incidentes: c,d,e;
Vértice D: grau 3, arestas incidentes: e,f,g;
Como todos os 4 vértices tem grau ímpar, logo, não existe uma maneira de
cruzar as pontes de Königsberg passando por todas as pontes uma única vez.
3. Problema do caixeiro viajante
3.1. Breve descrição do problema
Em uma cidade conectadas por rodovias, um caixeiro viajante quer visitar
pessoalmente cada cidade de modo que ele passe por todas as cidades somente uma vez
até voltar ao ponto de partida.
3.2. Representação do grafo
No caso do problema do caixeiro viajante, as arestas são as rodovias e os
vértices são as cidades. Desse modo, um exemplo de uma cidade utilizando esta
representação é apresentada na Figura 1.
Figura 1. Exemplo de representação.
3.3. Técnica utilizada
A técnica utilizada para resolver este problema é encontrar um ciclo
hamiltoniano no grafo. Caso haja um ciclo hamiltoniado então o problema está
solucionado, caso não seja possível encontrar um ciclo hamiltoniano então o problema
não pode ser solucionado.
Um grafo é dito ser hamiltoniano se existe um ciclo que contenha todos os seus
vértices, sendo que cada vértice só aparece uma vez no ciclo, com exceção do primeiro.
3.4.Exemplo da técnica utilizada
Na Figura 1 há um ciclo hamiltoniano V={PA, AP, MA, TO, MT, AM, RO,
PA}.
Não existe ainda um método conveniente para determinar se um grafo é
Hamiltoniano. Os teoremas existentes são específicos para determinados tipos de
grafos, por exemplo:
Teorema: Se G é um grafo de n >=3 vértices, tal que o grau(v) >= n/2 para
todos os vértice v de G, então G é hamiltoniano. Neste problema, este teorema se
aplicaria assim: “Existe um ciclo hamiltoniano se o número de rotas em cada cidade seja
maior ou igual ao número de cidades dividido por 2”
Esta é uma condição suficiente, porém não necessário. Isto significa que nem
todos os grafos hamiltonianos satisfazem esta condição, porém todos os grafos que
satisfazem esta condição são hamiltonianos.
4. Problema do Desenho da Casa
4.1. Identificação dos vértices e arestas:
Neste problema, todas as linhas que formam a casa são arestas, enquanto que as
bolinhas vermelhas são consideradas os vértices do grafo.
4.2. Solução do problema:
O desenho da casa, representado pelo grafo acima, pode ser feito do modo como
a criança relatou, ou seja, colocando o lápis em uma das bolinhas e realizando
movimentos contínuos para traçar cada linha uma única vez, até que o desenho esteja
completo. Isto é possível porque o grafo que representa o desenho da casa é conexo e
possui exatamente dois vértices de grau ímpar, ou seja, ele é atravessável e possui
trilhas eulerianas, que por sua vez é um tipo de trilha que começa em um dos vértices
de grau ímpar e termina no outro vértice, passando por todas as arestas apenas uma vez.
4.3. Exemplo de aplicação:
Consideram-se os rótulos a seguir, dados para os vértices do grafo em questão:
Com base nesta rotulação, uma forma de desenhar esta casa do modo como a
criança relatou é seguir a trilha (6, 5, 4, 3, 2, 1, 3, 6, 4, 2, 5). A trilha mencionada
começa em um vértice de grau ímpar, passa por todas as arestas do grafo apenas uma
vez, e termina no outro vértice que também possui grau ímpar, portanto tal trilha é
euleriana e resolve o problema adequadamente.
5. O Problema do Assassinato do Bilionário Count Van Diamond
5.1. Representação do grafo
Vértices: são os cômodos da casa. Sala de jogos (A), quarto de hospedes (B), bar
(C), dormitório (D), dependência da empregada (E), sala da piscina (F), adega (G),
cozinha (H), despensa (I), e fora da casa(J), pois ainda existem duas portas que levam
para fora da residência, devendo este ser considerado também um vértice.
Arestas: portas entre os cômodos: porta entre sala de jogos e quarto de hospedes
1(A,B), e em seguida, 2(A,B), 3(B,F), 4(B,C), 5(C,D), 6(D,E), 7(D,E), 8(G,H), 9(G,H),
10(F,H), 11(H,I), 12(F,I), 13(F,J), 14(F,J).
5.2. Técnica utilizada
O problema se baseia em provar quem tem razão: o mordomo ou o jardineiro. E
a prova gira em torno das portas já que o jardineiro afirma que passou por todas sem
repetir uma porta e o mordomo afirma que ele repetiu uma das portas da piscina. No
problema cada cômodo foi considerado um vértice e o lado de fora da casa também,
pois existem portas entre a piscina e o lado de fora e as portas são as arestas que ligam
cada cômodo.
O problema consiste em afirmar se existe um caminho que passe por todas as
portas (arestas) uma única vez, provando que o jardineiro diz a verdade, e o mordomo
mente. Caso contrário o mentiroso é o jardineiro.
A resolução consiste em desenhar um grafo que represente os cômodos e as
portas e verificar a existência de um caminho euleriano. Se houver um caminho
euleriano entre as arestas, então haverá um caminho entre as pontes, o que prova que o
mordomo mente, caso contrário, o mentiroso será o jardineiro, pois não existirá uma
maneira de passar por todas as portas, passando uma única vez por cada uma.
Segundo o teorema: Um grafo contem um caminho euleriano, se e somente se,
tiver 2 vértices de grau ímpar.
5.3. Solução
Vértice A: grau 2, arestas incidentes(1,2);
Vértice B: grau 4, arestas incidentes(1,2,3,4);
Vértice C: grau 2, arestas incidentes(4,5);
Vértice D: grau 3, arestas incidentes(5,6,7);
Vértice E: grau 2, arestas incidentes(6,7);
Vértice F: grau 5, arestas incidentes(3,10,12,13,14);
Vértice G: grau 2, arestas incidentes(8,9);
Vértice H: grau 4, arestas incidentes(8,9,10,11);
Vértice I: grau 2, arestas incidentes(11,12);
Vértice J: grau 2, arestas incidentes(13,14);
Como existem exatamente dois vértices de grau ímpar (D=dormitório e
F=piscina), então existe um caminho euleriano, logo, existe uma maneira de passar por
todas as portas passando por cada uma delas uma única vez, o que confirma a versão do
jardineiro e prova que o mordomo está mentindo. O mordomo é o assassino.
6. O Problema do passeio do cavalo (xadrez)
6.1. Breve descrição do problema
Um cavalo que possui movimentos em “L” no xadrez, pode partir de uma casa
qualquer, percorrer todas as casas somente uma vez e retornar à casa inicial?
6.2. Representação do grafo
No problema do passeio do cavalo as casas do tabuleiro são os vértices e os
possíveis movimentos do cavalo são as arestas.
Figura 2. Representação dos movimentos do cavalo no tabuleiro de
xadrez.
6.3. Técnica utilizada
A técnica utilizada para resolver este problema é verificar se o grafo gerado é
hamiltoniano. A Figura 2 apresenta que o grafo completo possuirá 64 vértices e 168
arestas, e como apresentado na Figura 1 existem vários ciclos sendo formados.
7. Problema da Pavimentação de Estradas
7.1. Identificação dos vértices e arestas:
A rede de estradas envolvida no problema é representada pela matriz de
adjacência abaixo:
Através desta matriz de adjacência, também é possível representar a rede de
estradas através de um grafo onde os vértices são as cidades ligadas pela rede de
estradas (na matriz de adjacência, cada cidade é representada por um número, sendo a
cidade de Santana do Caixa Prego representada pelo número 1) e as arestas são as
estradas que ligam tais cidades (representadas, na matriz de adjacência, pelas posições
assinaladas com um “X”, indicando que existe uma estrada entre duas determinadas
cidades).
7.2. Solução do problema:
Segundo Tertuliano Gonçalves, o trabalho de pavimentação deve começar em
Santana e prosseguir em continuidade, estada após estrada, terminando na mesma
cidade onde o trabalho foi iniciado. Para que isso seja possível, é necessário que exista,
no grafo que representa a rede de estradas a ser pavimentada, um ciclo euleriano. O
ciclo euleriano de um grafo é aquele que começa em um vértice, passa por todas as
arestas apenas uma vez, e termina no mesmo vértice onde começou. O referido tipo de
ciclo só poderá existir em um grafo se este último for conexo e todos os seus vértices
possuírem grau par.
7.3. Exemplo de aplicação:
Através da matriz de adjacência mostrada anteriormente, é possível saber o grau
de um determinado vértice através da quantidade de adjacências que podem ser
contadas em sua respectiva linha ou coluna. O vértice 2, por exemplo, possui na sua
linha e na sua coluna quatro adjacências com diferentes vértices, portanto o seu grau é
4.
Baseado nas informações contidas na matriz de adjacência, é possível constatar
que o grafo que representa a rede de estradas a ser pavimentada não possui um ciclo
euleriano, pois os vértices 1, 8, 9 e 10 possuem grau ímpar. Logo, não é possível
realizar o trabalho de pavimentação do modo como foi planejado e o Tertuliano não
estava sendo sincero com a Josefina. Ainda que o itinerário 1-5-9-10 estivesse a cargo
de outra empresa, o trabalho não poderia ser concluído do modo planejado e o
Tertuliano ainda não estaria sendo sincero, pois a eliminação deste itinerário dos planos
da primeiraempresa iria, também, eliminar algumas adjacências dos vértices que
compõem o itinerário, de modo que os vértices 1 e 10 passariam a ter grau par, porém
os vértices 8 e 9 ainda iriam possuir grau ímpar, o que impossibilita a existência de
ciclos eularianos no grafo.
8. O problema da Coleta de Correspondências
8.1. Representação do grafo
Vértices: postos de coletas de correspondência.
Arestas: rotas entre os postos.
8.2. Técnica utilizada
O problema se baseia em encontrar uma maneira eficiente de fazer a coleta de
correspondência entre os postos do correio. E responder 3 perguntas básicas do
problema: Como modelar o problema?, Como encontrar a melhor rota? Que
particularidades devem ser tratadas?
O problema consiste em encontrar um caminho que passe por todos os postos de
coletas (vértices) uma única vez, de modo que os motoristas tenham um caminho mais
simples para trabalhar.
A resolução consiste em desenhar um grafo que represente os postos de coleta e
as rotas entre os postos e verificar a existência de um caminho hamiltoniano, ou seja,
encontrar a solução mais eficiente seria encontrar um caminho que fizesse os motoristas
passarem por cada posto uma única vez sem ter de dar diversas voltas pela cidade. Se
houver um caminho hamiltoniano entre as arestas (rotas entre os postos), então este será
o caminho mais eficiente para os motoristas.
8.3. Solução
O problema deve ser modelado na forma de um grafo onde os postos de coleta
serão os vértices e as rotas entre estes postos serão as arestas. A melhor rota será uma
rota que represente um caminho hamiltoniano, ou seja, será a rota que passa uma única
vez por cada posto de coleta. As particularidades que devem ser tratadas são os
caminhos hamiltonianos que podem existir, caso não exista um, o caminho mais
eficiente será aquele que chegar próximo ao caminho hamiltoniano. Outra
particularidade seria dividir o grafo de todos os postos de coleta em subgrafos que
contenham caminhos hamiltonianos assim cada subgrafo ficaria sob a responsabilidade
de um motorista garantindo a cada motorista o melhor caminho.
9. O problema do Robô-Café
9.1. Breve descrição do problema
Um robô deve distribui cafezinhos em todas os escritórios da empresa, de modo
circular. Uma melhoria deve ser feita, de modo que o robô se adapte a qualquer empresa
de sorte que o robô escolha o melhor roteiro. Sempre considera-se o mesmo piso. Para
isso o robô foi equipado com um sensor que identificava portas e outro que indica
pontos de paradas. O robô seria capaz de diferenciar os sensores de portas dos sensores
de parada, porém em cada local ele só seria capaz de captar apenas o sinal de dentro da
sala. Na escolha do melhor roteiro o robô deve:
Passar por todas as salas com sensores;
Minimizar a distância percorrida;
O ciclo deve ser sempre completado, o que pode-se mudar é a ordem das salas
visitadas;
9.2. Representação do grafo
O problema se resume basicamente a escolher um percurso cíclico de modo a
otimizar a ordem das salas visitadas. Como parâmetro para esta otimização pode-se
atribuir pesos a cada aresta, sendo este peso como a combinação entre a distância e a
requisição de parada. Para representar este problema como um grafo deve-se considerar
cada ponto de parada como vértice e cada porta como aresta.
9.3. Técnica utilizada
Como para cada aresta pode ser atribuída pesos que são combinação entre a
distância e a requisição, pode-se utilizar o algoritmo de Dijstra para calcular o caminho
de custo mínimo. Esta rota daria prioridade aos pontos de paradas mais pertos que estão
emitindo sinal de requisição de café.
10. Problema do Caminho de Custo Mínimo
10.1. Identificação dos vértices e arestas:
A rede de estradas mostrada no mapa abaixo pode ser representada através de
um grafo, onde as arestas representam as estradas que ligam as cidades e os vértices
representam as cidades por onde as estradas passam. Cada aresta irá possuir um peso
que representa a distância entre as duas cidades ligadas pela respectiva estrada.
10.2. Solução do problema:
O caminho de menor custo entre quaisquer duas cidades pode ser calculado
através do algoritmo de Dijkstra. Escolhido um vértice do grafo como raiz da busca,
este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do
grafo. 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:
o seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos
os vértices abertos;
o feche o vértice k
o 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.
10.3. Exemplo de aplicação:
O grafo a seguir será utilizado como exemplo:
Ao aplicar o algoritmo de Dijkstra no grafo anterior, onde o objetivo é encontrar
o caminho de menor custo entre o vértice A e o vértice D, será possível constatar que,
apesar de haver um caminho direto entre os dois vértices, o caminho (A, C, D) é o de
menor custo dentre todos os possíveis, pois este último possui um custo total de 5,
enquanto que o caminho (A, D) possui um custo total 8, e o caminho (A, B, D), também
8.
11. O Problema do Metrô
11.1. Representação do grafo
Vértices: cada estação (destino ou partida).
Arestas: ligações diretas entre cada estação vizinha.
11.2. Técnica utilizada
O problema consiste em encontrar a melhor rota de metrô. No problema o
melhor caminho leva em consideração o número de trocas de composição e em seguida
o numero de paradas. Logo o melhor caminho será aquele que tiver o menor número de
troca de composição e menor número de paradas.
Para resolver o problema desenha-se um grafo onde cada estação será um
vértice, onde cada estação pode ser uma troca de composição ou parada.
11.3. Solução
Para verificar o melhor caminho entre dois vértices (estações) verifica-se todos
os caminhos possíveis entre estes vértices. Depois verificar o número vértices que são
trocas de composição e armazenar esse valor, e o número de vértices que são paradas e
armazenar também. Depois se realiza uma comparação onde o caminho que tiver o
menor número de trocas de composição e menor número de paradas nessa ordem será o
melhor caminho. Uma particularidade desse problema é que o sistema pode calcular
esses resultados uma única vez e armazenar os resultados em um banco, dessa forma
quando cada usuário for utilizar o metrô, basta mostrar o resultado já calculado e
armazenado para cada combinação de estações (destino e partida).
12. O problema da RNP
12.1. Breve descrição do problema
A RNP (Rede Nacional de Pesquisa) é uma rede de computadores que interliga
várias instituições. Como selecionar a melhor rota quando for houver mais de uma
possibilidade?
12.2. Representação do grafo
Cada vértice é um POP (Ponto de Presença) e cada aresta é um enlace
12.3. Técnica utilizada
Pode-se atribuir pesos às arestas de modo que quando houver mais de um
caminho possível escolher-se aquele com menor peso. Sendo queeste peso pode ser
indicando o congestionamento do enlace ou a vazão do enlace.
Para calculo computacional da melhor rota pode-se utilizar o algoritmo de
Dijkstra, que calcula o caminho de custo mínimo.
13. Problema da Carga Pesada
13.1. Identificação dos vértices e arestas:
Este problema pode ser representado através de um grafo onde os vértices
representam as cidades e as arestas representam as estradas que ligam tais cidades.
Além disso, cada aresta do grafo possui um peso que corresponde à restrição de altura
máxima, imposta pelo viaduto existente na estrada representada.
13.2. Solução do problema:
Uma vez tendo a representação de tal problema em forma de grafo, para resolvê-
lo é necessário encontrar o fluxo máximo do grafo, que se trata do número máximo de
unidades de fluxo (que, no caso do problema em questão, representa a altura das cargas)
que é possível enviar, através do grafo, desde o nó de origem até o nó de destino.
O Algoritmo de Ford-Fulkerson pode ser utilizado para encontrar o fluxo
máximo de um grafo:
1. Introduz-se um fluxo arbitrário compatível (fluxo de cada arco não
exceda a capacidade).
2. Obtém-se um fluxo completo (todos os caminhos contenham pelo menos
um arco saturado)
3. Obtém-se o fluxo máximo
a. Marca-se a fonte com sinal +
b. Um vértice Xi estando marcado:
i. marcar com + Xi todo vértice Xj não marcado tal que existe um
arco (Xi,Xj) não saturado.
ii. marcar com - Xi todo vértice Xj não marcado tal que exista um
arco (Xj,Xi) percorrido por um fluxo não nulo.
c. Se o fluxo não for máximo, considera-se a seqüência de vértices
marcados (+ ou -) indo da fonte ao sumidouro; se um arco desta
seqüência é orientado no sentido da seqüência soma-se, em caso
contrário subtrai-se uma unidade ao fluxo desse arco;
d. Apaga-se as marcas e retorna-se ao passo 3.a até que não seja
possível marcar o sumidouro (passo 3.c).
14. O Problema da Ambulância
14.1. Representação do grafo
Vértices: vilas 1,2,3,4,5,6,7.
Arestas: igarapés (1,2), (2,6), (3,4), (4,3), (4,5), (5,7), (6,2), (6,4), (6,7), (7,1),
(7,4).
14.2. Técnica utilizada
O problema consiste em encontrar o menor caminho entre as vilas.
A solução baseia-se em representar o problema na forma de um dígrafo onde as
vilas são representadas pelos vértices e os igarapés por arestas dirigidas. E o menor
caminho entre as vilas será o caminho com o menor número de arestas.
14.3. Solução
Para verificar o menor caminho entre dois vértices em um dígrafo, é necessário
criar uma lista de todos os caminhos possíveis entre esses dois vértices e em seguida
verificar qual deles passa pelo menor número de arestas, pois este será o menor
caminho.
15. O problema dos canibais e dos missionários
15.1. Breve descrição do problema
Há três missionários e três canibais que devem atravessar um rio em uma canoa
que transporta apenas duas pessoas. Como fazer essa atravessia sem que o número de
canibais seja superior ao número de missionários
15.2. Representação do grafo
Todas as situações possíveis nas margens podem ser representadas por um par
ordenado (c,m), onde m representa o número de missionários e c o número de canibais.
Assim, são gerados 16 combinações, porém como há restrição para que m>=c restam
10 situações possíveis.
Os vértices são os 10 pares ordenados (c,m), que descrevem os possíveis estados
das margens;
As arestas são os pares ordenados composto pelo vértice da margem antes de
iniciar a travessia e pelo vértice da margem oposta após a travessia ser completada.
15.3. Técnica utilizada
A solução poderia utilizar um algoritmo de busca que escolhesse estados até
chegar ao estado (cc,mm) e de lá retornasse ao estado (ccc,mmm)
16. Problema da Fuga dos Ladrões
16.1. Identificação dos vértices e arestas:
Este problema pode ser representado através de um grafo onde os vértices
devem representar as situações (ou estados) que podem ocorrer nos locais de origem e
de destino da fuga, no que se refere à presença dos ladrões e do dinheiro roubado. Cada
um destes estados pode ser representado através de um conjunto (a, b, c, d) de números
binários, onde:
“a” representa o ladrão que sabe pilotar, cujo peso é 60 Kg;
“b” representa o guarda-costas do chefe, que pesa 100 Kg;
“c” representa o chefe dos ladrões, que pesa 70 Kg;
“d” representa o dinheiro roubado, cujo peso é 40 Kg.
O valor 0 para um determinado item significa a ausência daquele elemento em
um determinado local, enquanto que o valor 1 significa presença.
16.2. Solução do problema:
Para este problema, existem algumas restrições que eliminam algumas situações,
pois as mesmas não podem ocorrer:
Apenas um ladrão sabe pilotar, portanto ele sempre estará presente no
avião e no local onde o mesmo se encontra a cada momento (origem ou
destino), durante o processo de fuga (Seu valor será sempre 1 nos
estados).
O avião comporta apenas 170 Kg. Portanto, se o piloto der carona para o
guarda-costas, nada mais poderá ser levado no avião, na mesma viagem
(O valor 1 para o piloto e para o guarda-costas implica em valor 0 para os
demais elementos).
Como existe desconfiança mútua entre o piloto e o chefe, em nenhum
momento qualquer um dos dois pode ficar sozinho com o dinheiro. Isto
quer dizer que estados onde se nota a presença de apenas um destes dois
elementos e do dinheiro, tanto no lado onde o avião se encontra como no
lado opsoto, não são permitidos (como (1, 0, 0, 1), (0, 0, 1, 1), (1, 1, 0, 0)
e (0, 1, 1, 0)). Nos dois últimos conjuntos, a ausência de um dos ladrões
em questão e do dinheiro significa a presença dos mesmos no outro lado.
O grafo abaixo apresenta alguns estados possíveis (representados pelos vértices)
e transições entre os mesmos (representados pelas arestas). A solução para o problema
em questão é encontrar um caminho que parta do vértice (1, 1, 1, 1), onde todos os
ladrões e o dinheiro se encontram na origem da rota de fuga, e chegue novamente ao
mesmo vértice, indicando que todos os elementos se encontram no destino da rota.
17. O Problema dos três maridos ciumentos
17.1. Representação do grafo
Vértices: maridos e esposas: M1,E1,M2,E2,M3,E3.
Arestas: pessoas que não podem estar juntas no carro, nem no local de partida e
nem no local destino: (M1,E2), (M1,E3), (M2,E1), (M2,E3), (M3,E1), (M3,E2).
17.2. Técnica utilizada
O problema consiste em levar 3 casais a um lugar em um carro onde só cabem
duas pessoas e um marido não pode estar sozinho com a esposa do outro.
Pode-se descrever este problema na forma de um grafo principal P(V,A) onde os
vértices são os maridos e esposas e as arestas são as pessoas que não podem estar juntas
nos carros, ou seja, um marido e a mulher dos outros.
A solução baseia-se em formar 3 grafos completos, um representando a dupla no
carro, um representando as pessoas no local de partida e um representando as pessoas
no local de destino. E a cada passo da resolução cada um desses 3 grafos não pode ser
igual (mesmas arestas entre os mesmos vértices) a nenhum subgrafo do grafo principal
P, ou seja, nenhum desses grafos pode ter a mesma ligação de uma das arestas do grafo
principal, pois representam duplas que não podem estar sozinhas.
17.3. Solução
Na saída: M1,E1,M2,E2,M3,E3. No destino: ninguém.
No carro: M1 vai com E1, M1 volta só. Na partida: M1,M2,E2,M3,E3. No
destino: E1.
No carro: M1 vai com M2, M2 volta só. Na partida: M2,E2,M3,E3. No destino:
M1,E1.
No carro: M2 vai com M3, E1 volta só. Na partida: E1,E2,E3. No destino:
M1,M2,M3.
No carro: E1 vai com E2, M3 volta só. Na partida: M3,E3. No destino:
M1,E1,M2,E2.
No carro: M3 vai com E3. Na partida: ninguém. No destino:
M1,E1,M2,E2,M3,E3.
18. O problema dos potes de vinho
18.1. Breve descriçãodo problema
Existem três potes v1, v2, v3 de vinho com capacidades de 8, 5 e 3 litros,
respectivamente. O maior está cheio e os outros estão vazios. Deve-se dividir os 8 litros
de vinho em duas partes de 4 litros. Para realizar isso, qual seria o menor número de
transvasos possível para completar a tarefa?
18.2. Representação do grafo
Os vértices podem ser representados como sendo trio ordenado (q, q2, q3),
representando a quantidade de vinho dos vasos v1, v2, v3.
As arestas são representadas pelos pares ordenados (e1, e2), onde e1 representa
o estado inicial de um vaso, e e2 representa um estado final que foi alcançado por meio
de um único transvaso de um pote no outro.
18.3. Técnica utilizada
Para encontrar a solução deve-se gerar o grafo contento todos os estados que
satisfazem as condição. Depois de gerar tal grafo será possível executar um algoritmo
de caminho de custo mínimo (Dijstra) que vá do estado (8,0,0) até (4,4,0).
19. Problema do Concerto com o U2
19.1. Identificação dos vértices e arestas:
Este problema pode ser representado através de um grafo onde os vértices
devem representar as situações (ou estados) que podem ocorrer nos locais de origem e
de destino da travessia da ponte, no que se refere à presença dos músicos. Cada um
destes estados pode ser representado através de um conjunto (b, e, a, l) de números
binários, onde:
“b” representa o Bono, que cruza a ponte em 1 minuto;
“e” representa o Edge, que cruza a ponte em 2 minutos;
“a” representa o Adam, que cruza a ponte em 5 minutos;
“l” representa o Larry, que cruza a ponte em 10 minutos;
O valor 0 para um determinado músico significa a ausência daquele sujeito em
um determinado lado da ponte, enquanto que o valor 1 significa presença.
19.2. Solução do problema:
Para este problema, existem algumas restrições a serem consideradas na busca
da solução:
O concerto do qual a banda vai participar vai começar em 17 minutos,
portanto o tempo total do processo de travessia da ponte não deve
ultrapassar este tempo;
Apenas dois músicos podem atravessar a ponte por vez;
A travessia da ponte sempre deve ser feita com uma lanterna, que pode
ser carregada por qualquer um dos músicos. A lanterna não pode ser
jogada, portanto, até que todos tenham cruzado a ponte, um dos músicos
deve voltar com a lanterna para buscar aqueles que ficaram para trás.
O grafo abaixo apresenta alguns estados possíveis (representados pelos vértices)
e transições entre os mesmos (representados pelas arestas). A solução para o problema
em questão é encontrar um caminho que parta do vértice (1, 1, 1, 1), onde todos os
músicos se encontram no lado de origem da ponte, e chegue novamente ao mesmo
vértice, indicando que todos os músicos se encontram no lado de destino da ponte.
20. Problema dos dissidentes políticos
20.1. Representação do grafo
Vértices: celas a1,a2,a3,a4,a5,a6,a7,a8,a9,a10 e a saída r.
Arestas: paredes entre celas e a saída: (a1,a6), (a2,a4), (a2,a5), (a2,a6), (a3,a4),
(a4,a5), (a4,a10), (a5,a7), (a5,a9), (a5,a10), (a6,a7), (a7,a8), (a7,a9), (a9,a10), (r,a1),
(r,a2), (r,a3), (r,a4), (r,a7), (r,a8), (r,a9), (r,a10).
20.2. Técnica utilizada
O problema consiste em encontrar um caminho que passe por todas as celas
(vértices) destruindo o menor número de paredes (passando pelo menor número de
arestas).
Passar por todas as celas consiste em encontrar um caminho que passe por todos
os vértices. Em um grafo conexo o menor caminho que passe por todos os vértices é
igual ao número de vértices – 1, pois cada aresta liga dois vértices, então se retirarmos 1
aresta eliminamos um vértice do caminho exceto a última aresta a ser retirada que
completa o caminho e retira 2 vértices. Por isso a fórmula (nºV – 1).
20.3. Solução
No problema temos 11 vértices, logo a melhor solução possível será destruir 10
portões. De uma maneira geral o menor número de portões será sempre o numero de
celas existentes menos 1.
21. O problema da construção da ferrovia
21.1. Breve descrição do problema
Deve-se construir uma malha ferroviária que ligue um conjunto de cidades.
Todos os segmentos que ligam duas cidades possui um custo conhecido. De que modo
deve ser feito a definição da malha de modo a ficar mais barata possível.
21.2. Representação do grafo
Cada cidade do estado são os vértices e cada aresta são todos os possíveis
segmentos ligando cada duas cidades. Neste caso deve-se atribuir a cada aresta o custo
da construção do segmento.
21.3. Técnica utilizada
Como solução deste problema pode-se utilizar um Algoritmo para calcular o
caminho hamiltoniano de custo mínimo.
22. Problema dos Conspiradores Políticos
22.1. Identificação dos vértices e arestas:
Este problema pode ser representado através de um grafo onde os vértices
representam os agentes A, B, C, D, E, F, G e H e arestas representam as comunicações
diretas que são praticáveis entre os mesmos. Além disso, cada aresta possui um peso
que corresponde ao fator de risco imposto pela comunicação direta representada.
22.2. Solução do problema:
Para se obter o menor risco total neste sistema, é necessário utilizar alguma
técnica para se chegar a um grafo de custo global mínimo, ou seja, uma árvore de custo
mínimo, onde todos podem se comunicar com o menor fator de risco possível.
O Algoritmo de Prim pode ser utilizado para encontrar a árvore de custo
mínimo de um grafo:
1. Selecionar qualquer nó e conectá-lo (isto é, adicionar um arco) para o nó mais
próximo.
2. Identificar o nó desconectado mais próximo para um nó conectado e então
conectar estes dois nós.
3. Repetir o passo 2 até que todos os nós tenham sido conectados.
No caso de empate de dois ou mais nós não conectados mais próximos de
um nó conectado, escolher arbitrariamente um dos nós não conectados.
23. O Problema da Rede ótica entre tabas
23.1. Representação do grafo
Vértices: tabas 1,2,3,4,5.
Arestas: ligações possíveis de fibra ótica e seu custo: (1,2,c15), (1,3,c12),
(2,3,c6), (2,4,c13), (2,5,c5), (3,4,c6).
23.2. Técnica utilizada
O problema consiste em encontrar o que ramos da rede de fibra ótica devem ser
construídos de forma a garantir comunicação entre todas as tabas causando o menor
impacto ambiental possível (menor custo).
Representamos este problema na forma de um grafo onde as tabas são os
vértices e as ligações de fibras óticas são as arestas e cada aresta tem um custo.
Para sabermos qual a melhor solução devemos encontrar um subgrafo gerador
do grafo principal cujo somatório de todos os custos das arestas seja o menor.
Um subgrafo gerador SG de um grafo G é um grafo que conexo que contem um
conjunto de vértices igual a G, porém o menor número possível de arestas que torne SG
conexo.
23.3. Solução
Para encontrar a melhor solução formamos todos os subgrafos geradores do
grafo principal e somamos os custos de todas as arestas, e o subgrafo gerador com o
menor custo total é a melhor solução. No caso o subgrafo gerador seguinte: (1,3,c12),
(2,3,c6), (2,5,c5), (3,4,c6). Este grafo apresenta um custo total de 29.
24. O problema da instalação da rede elétrica
24.1. Breve descrição do problema
Com base na tabela de possibilidades de instalação de seções da rede elétrica em
um loteamento, deve-se determinar:
a) Quais seções da rede devem ser construídas a fim de levar energia até o sítio j de
forma a ter menor custo.
b) Depois de ter a linha de a para j instalada, planejar uma rede para abastecer os
outros sítios com menor custo.
c) Se a empresa teve prejuízos ao fazer a primeira instalação.
24.2. Representação do grafo
Cada vértice é representado pelos sítios e cada aresta é representada pelo ligação
elétrica.
24.3. Técnica utilizadaPara se solucionar o problema deve-se gerar todas as possibilidades de ligação e
atribuir a cada aresta o peso correspondente ao custo. Posteriormente, pode-se calcular
uma árvore geradora mínima de modo a ter o custo mínimo.
