Otimização

Páginas: 5 (1136 palavras) Publicado: 12 de novembro de 2011
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 ocorreuo 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. Quempoderia 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 chegadada 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 emformato 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írculovazio) do cavalo que está na casa marcada com círculo cheio.

a) Desenhe o grafo do cavalo para um tabuleiro 3x3 e mostre que é impossível percorrer todas as casas uma única vez partindo de qualquer casa.
b) Qual propriedade o grafo do cavalo teria que ter para que fosse possível percorrer todas as casas passando uma e somente uma única vez em cada casa?

6) a) Imagine um tabuleiro 4x4. Qual omáximo de cavalos você consegue colocar nesse tabuleiro de modo que nenhum deles ameace aos outros?
b) Coloque 4 cavalos no tabuleiro abaixo (há um cavalo em cada casa marcada) de modo também que nenhum dos oito cavalos ameacem um ao outro.

7) O Departamento de Matemática pretende oferecer 7 disciplinas para o próximo semestre:
1. (C) - Cálculo
2. (G) - Grafos
3. (L) - Lógica4. (N) - Noções de Análise
5. (P) - Probabilidade
6. (S) - Sólidos Platônicos
7. (T) - Topologia
Com base num levantamento prévio, verificou-se que cada estudante planeja cursar as disciplinas indicadas abaixo:
Aluno |Disciplinas | |Aluno |Disciplinas | |Aluno |Disciplinas | |Bianca |C,L,T | |Jackson |C,G,S | |Luiz Carlos |G,N | |Marcos |C,L | |Jonathas |L,N | |Marco |C,G | |MarcoTúlio |N,P | |Leonardo |G,L | |Adriana |C,T | |Oraldo |C,S,T | |Vinícius |P,S | |Paula |P,T | |a) Considerando que cada disciplina é dada num período, como se poderia determinar qual o menor número de períodos necessários para que os sete cursos possam ser oferecidos?
b) Qual o maior número de disciplinas que podem ser dadas ao mesmo tempo?

Respostas

1) Tentemos representar a situação descritaatravés de um grafo em que um dos vértices representa a rua e cada um dos restantes uma das divisões da casa. Os vértices estão conectados por uma (ou mais) aresta se entre as divisões correspondentes existir alguma (ou algumas) porta. Podemos agora notar que existem, no grafo, exatamente dois vértices de grau ímpar (P e D). Assim, o único percurso que permite atravessar todas as arestas uma...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Otimização
  • Otimização
  • Otimização
  • Otimização
  • Otimização
  • Otimização
  • Otimização
  • Otimização

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!