listan1

Prévia do material em texto

Lista de Exercícios Ñ 3,0 pontos
Introdução à Teoria dos Grafos
Prof. Charles Ferreira
1 Instruções
• A atividade deve ser entregue exclusivamente pelo Blackboard.
• Deverá ser entregue um arquivo exclusivamente no formato pdf contento as respostas
desta lista e o nome e o RA de todos os membros do grupo.
• A lista deve ser entregue até dia 05/05/2021.
• A atividade pode ser feita em grupos de 3 a 5 alunos.
• A nota será calculada como: nota = notaDaLista * 0,3.
1
2 Exercícios
1. (Valor 1,5) Construa uma representação geométrica do grafo G = (V, E), em que:
V = { 1, 2, 3, 4, 5, 6 };
E = { (1,2), (1,4), (1,5), (2,3), (2,4), (2,5), (3,5), (4,5) }
(a) Escreva o grau dos vértices.
(b) Escreva o tamanho.
(c) Represente-o através de suas matrizes de adjacências e de incidência.
2. (Valor: 1,5) Os amigos João, Pedro, Antônio, Marcelo e Francisco sempre se encontram para
botar conversa fora e as vezes jogam dama, xadrez e dominó. As preferências de cada um são
as seguintes:
i. João só joga xadrez;
ii. Pedro não joga dominó;
iii. Antônio joga tudo;
iv. Marcelo não joga xadrez e dominó;
v. Francisco não joga nada.
(a) Represente através de um grafo bipartido G = (V, E) todas as possibilidades de um amigo jogar
com os demais. Defina V e E.
(b) Defina um subgrafo em que todos, menos Francisco, joguem ao mesmo tempo.
(c) A partir do grafo bipartido do item a) construa um grafo rotulado que mostra quem pode jogar
com quem o que.
3. (Valor: 1,0) Identifique se os grafos a seguir são isomorfos. Justifique sua resposta.
(a)
2
(b)
v1 v2 v3 v5 v6 v8
v4 v7
v1 v2 v3 v5 v6 v8
v4 v7
4. (Valor 1,0) Observe o seguinte grafo direcionado e responda as seguinte perguntas:
1
6 5
4
32
a6
a7 a5
a4
a3
a2
a11
a8
a9
a10
a1
(a) Quais são os nós acessíveis a partir do nó 3?
(b) Qual o caminho mais curto do nó 3 para o nó 6?
(c) Qual o caminho de comprimento 5 do nó 1 para o nó 6?
5. (Valor: 1,0) Olhando o grafo abaixo, mostre:
a b
c d
e
(a) Cinco passeios diferentes;
(b) Quatro trilhas diferentes;
(c) Três caminhos abertos;
(d) Um caminho fechado.
6. (Valor: 1,0) Demonstre (passo a passo) utilizando o grafo abaixo o funcionamento dos
algoritmos de:
3
1
3
4
2
5
(a) busca em largura (BFS)
(b) busca em profundidade (DFS)
7. (Valor: 1,5) Encontre a árvore geradora mínima utilizando o algoritmo de Kruskal do grafo
abaixo.
1
3
4
2
5
8
9
5
4
5 3
2
5
1
8. (Valor: 1,5) Encontre a árvore geradora mínima utilizando o algoritmo de Prim do grafo
abaixo.
2
3
1 4
6
5
7
30
60
20
30
25
20
40
10
15
35
4