lista5-Grafos
1 pág.

lista5-Grafos

Disciplina:Álgebra Linear II469 materiais5.807 seguidores
Pré-visualização1 página
Lista 5 - Exercícios de Grafos

1ª. Questão

Fulano da Silva está preso em um labirinto. Ele pode ir da sala azul para as salas rosa ou vermelha. Da

sala rosa ele pode ir para a amarela ou verde. Da Amarela ele também pode ir para a vermelha. E da

verde ele também chega até a vermelha. Ele sempre pode utilizar o caminho contrário. Ele não tem

preferência por ir para nenhuma das salas e sempre é obrigado a mudar da sala que está toda vez que

toca uma campainha. Considere para efeito de contas que o Sr. Fulano vai de uma sala a outra adjacente

em 1 passo (Sr. Fulano tem passo de gigante!)

a. Desenhe o grafo que representa o labirinto e escreva a matriz de adjacência.

b. Diga quantas entradas diferentes tem M
n

c. Quais são os autovalores de M?

d. Determine uma fórmula, não recursiva e que dependa somente de n, para calcular o número

de caminhos, de n passos (isto é após n toques de campainha) em que Fulano da Silva começa

na sala azul e para ela retorna no passo n.

e. Determine uma fórmula, não recursiva e que dependa somente de n, para calcular o número

de caminhos, de n passos (isto é após n toques de campainha) em que fulano da silva sai da

sala azul e termina na sala vermelha.

2ª. Questão

Considere o grafo G com cinco vértices {A,B,C,D,E} onde só existem arestas ligando A aos outros

vértices.

a. Escreve a matriz de adjacência do grafo

b. Encontre uma fórmula que dependa só de n, para o número de caminhos fechados de B, de

tamanho n.

c. Encontre uma fórmula que dependa só de n, para o número de caminhos de A até E, de

tamanho n.

3ª. Questão

Lembram do Fulano da Silva? Pois é, o coitado se meteu em outro labirinto! Ele pode ir da sala rosa para

amarela ou azul. Da sala azul ele vai para a branca e da branca para a sala amarela. Ele sempre pode

utilizar o caminho contrário. Ele não tem preferência por ir para nenhuma das salas e sempre é obrigado

a mudar da sala que está toda vez que toca uma campainha. Considere para efeito de contas que o Sr.

Fulano vai de uma sala a outra adjacente em 1 passo (Sr. Fulano tem passo de gigante!), como vocês já

sabem!

a. Escreva a matriz de adjacência.

b. Quais são os autovalores de M e suas multiplicidades algébricas.

c. Determine uma fórmula, não recursiva e que dependa somente de n, para calcular o número

de caminhos, de n passos (isto é após n toques de campainha) em que Fulano da Silva começa

na sala azul e para ela retorna no passo n.

d. Determine uma fórmula, não recursiva e que dependa somente de n, para calcular o número

de caminhos, de n passos (isto é após n toques de campainha) em que Fulano da Silva começa

na sala azul e termina na sala rosa no passo n.