Otimização

Problemas – Teoria de Grafos
1) O problema do assassinato do bilionário Van Diamond: A figura abaixo é a planta da residência do bilionário Van Diamond, que acaba de ser assassinado. Sherlock Gomes (um conhecido detetive que nas horas vagas é um estudioso da Teoria de Grafos) foi chamado para investigar o caso. O mordomo alega ter visto o jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar aquela sala pela mesma porta que havia entrado. O jardineiro, contudo, afirma que ele não poderia ser a pessoa vista pelo mordomo, pois ele havia entrado na casa, passado por todas as portas uma única vez e, em seguida, deixado a casa. Sherlock Gomes avaliou a planta da residência (conforme figura) e em poucos minutos declarou solucionado o caso. Quem poderia ser o suspeito indicado por Sherlock Gomes? Qual o raciocínio utilizado pelo detetive para apontar o suspeito?

2) Uma família da cidade C decide programar, para umas férias, uma viagem pela Europa em que visitará as cidades P, R e B. De modo a minimizar a distância a percorrer, foi elaborado um grafo em que cada vértice representa uma das cidades a ser visitada (além de C, partida e chegada da viagem) e junto a cada aresta foi colocada a quilometragem que separa essas cidades. Qual deve ser o trajeto que minimiza a distância a percorrer?

3) Encontre um caminho até ao centro representado por *, e a respectiva saída.

4) Tente encontrar um trajeto para sair do labirinto de Hampton, supondo que você está em A.

5) O cavalo, no jogo de xadrez, tem um movimento bem peculiar em formato de "L": duas casas no sentido vertical ou horizontal e uma casa no outro sentido. O grafo do cavalo t-por-t é definido assim: os vértices do grafo são as casas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são adjacentes se um cavalo do jogo de xadrez pode saltar de um deles para o outro em um só movimento.

Na figura abaixo temos as possibilidades de movimento (círculo