Teo Graf 142 5N Trab 1

Prévia do material em texto

Teoria dos Grafos (5N) 
Trabalho 1 (válido como B1) 
 
Prazo: 07/10/2014 
Equipe: Até 2 alunos 
 
 
1. Considere o grafo G = (V,E) definido abaixo. 
 V = {1, 2, 3, 4, 5, 6} 
 E = { e1, e2, e3, e4, e5, e6} 
 onde e1 = (1,2), e2 = (1,4), e3 = (2,3), e4 = (3,6), e5 = (5,6), e6 = (4,5) 
a) ele é conectado? Justifique. 
b) ele possui um ciclo? Justifique. 
c) ele é bipartido? Justifique. 
d) ele é regular? Justifique. 
 
2. Os grafos G1 e G2 representados graficamente abaixo são isomorfos? Justifique. 
 
G1: G2: 
 
 
3. Para o grafo representado graficamente abaixo: 
 
a. represente o grafo através de uma matriz de incidência 
b. represente o grafo através de uma matriz de adjacência 
c. represente o grafo através de uma lista de adjacência 
d. mostre quais são todos os caminhos que existem entre os vértices b e f 
 
4. Para o grafo da questão (3), acompanhe a execução da Busca em Largura, mostrando os vértices e os 
ramos visitados, considerando “e” como o vértice inicial. 
 
 
Entrega - Observe atentamente as instruções a seguir: 
Envie mensagem com o trabalho para 
 paulo_simoni@hotmail.com 
e envie uma cópia da mensagem para você mesmo. 
Atenção - Coloque no campo de assunto da mensagem: 
 TeoGraf (5N) - nomes abreviados dos integrantes - Trab1 
Coloque o nome completo e o registro dos integrantes no início da mensagem e em eventuais arquivos 
anexados (pdf, txt, ppt ou doc). 
Se não chegar a confirmação do recebimento em 2 dias, envie novamente a mensagem. 
 
Paulo Simon