899272 Lista2

Lista 2 Profa. Anna Izabel Tostes

Questão 1

Um explorador deseja explorar todas as estradas entre um número de cidades, mostradas na figura. É possível encontrar um roteiro que passe por cada estrada apenas uma vez e volte a cidade inicial?

Grafos

Objetivo: fixação de conteúdo.

Conteúdo:
Grafos eulerianos
Grafos unicursais
Grafos hamiltonianos
Heurísticas
Entrega: próxima aula

Questão 2

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 (= knight) do jogo de xadrez pode saltar de um deles para o outro em um só movimento. Faca uma figura do grafo do cavalo 3-por-3. Escreva as matrizes de adjacência e incidência do grafo do cavalo 3-por-3. Quantas arestas tem o grafo do cavalo 8-por-8? Quantas arestas tem o grafo do cavalo t-por-t?

Questão 3

Que aparência tem a matriz de adjacências de um grafo bipartido?


Questão 4

O cenário abaixo é a residência do bilionário Count Van Diamond, que acaba de ser assassinado. Sherlock Gomes (um conhecido detetive que nas horas vagas é um estudioso da teoria dos 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 abaixo) 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?

Questão 5

Sobre grafos, considere as figuras representativas a seguir.

Assinale a alternativa correta.
a) Somente os grafos I e II admitem caminho euleriano.

b) Somente os grafos I e IV admitem