Algoritmos em Grafos - Exercícios

Prévia do material em texto

Pontifícia Universidade Católica de Minas Gerais 
Sistemas de Informação - Algoritmos em Grafos 
Profa.: Michelle Nery Nascimento 
1/2020 
Valor: 2,5 pontos – Data de entrega: 09/03/2020 (via SGA) 
 
 
1) Determine o número de vértices de um grafo G simples, regular, com 15 arestas. 
2) Determine o número de vértices de um grafo G, simples, de 9 arestas e cujos vértices, todos, 
têm grau 3. 
3) Indique um grafo simples com 8 vértices com os seguintes graus: 1, 1, 2, 3, 3, 4, 5 e 7. 
4) Apresente um grafo conexo, sem loops, com 8 vértices com os seguintes graus: 1, 1, 1, 2, 3, 4, 
5 e 7. 
5) Um grafo possui oito vértices e seis arestas? Esse grafo é conexo? Justifique a resposta. 
6) Os grafos abaixo são isomorfos? Justifique. 
 
 
 
7) Represente o grafo abaixo usando matriz de adjacência e, depois, lista de adjacência: 
 
 
 
8) (Wilson, 1996) Jonh gosta de Jordan, Jean e Jane; Joe gosta de Jane e Joan; Jean e Joan gostam 
um do outro. Desenhe um dígrafo ilustrando estes relacionamentos entre Jonh, Joan, Jean, Jane 
e Joe. 
 
9) Desenhe o grafo 𝐾" e diga quantas arestas este grafo contém. 
 
10) Quantas arestas contém o grafo 𝐾#$? 
 
 
11) Seja V um conjunto de pontos no plano. Digamos que dois desses pontos são adjacentes se a 
distância entre eles é menor que 2. Essa relação de adjacência define o grafo dos pontos no 
plano (sobre o conjunto V). Faça uma figura do grafo definido pelos pontos: 
(0, 2)	(0, 1)	(0, 0)	
(1, 2)	(1, 1)	(1, 0)	
(2, 2)	(2, 1)	(2, 0) 
 
Escreva a matriz de adjacência e a lista de adjacência do grafo. 
 
12) Seja G um grafo com 𝑣 vértices e 𝑎 arestas. Quantas arestas contém o grafo complementar 
de G? 
 
13) Encontre e mostre as condições que fazem um grafo bipartido completo Kn,m ser: 
a. Euleriano 
b. Hamiltoniano 
 
14) Diga se os grafos abaixo são Eulerianos, Hamiltonianos, Unicursais ou nenhum deles: 
a. O grafo 𝐾" 
b. O grafo 𝐾. 
c. O grafo bipartido 𝐾/,0 
d. O grafo bipartido 𝐾.,. 
 
15) Se existem nove times de futebol em uma liga, é possível programar um torneio em que cada 
time jogue com exatamente três outros times? Resolva usando a teoria de grafos. 
 
16) Seja 𝐺 um grafo com 𝑣	vértices e 𝑎 arestas. Quantas arestas contém 𝐺 ∪ �̅�? 
 
17) Mostre quantos ciclos hamiltonianos disjuntos de arestas existem no grafo 𝐾/$. 
 
 
17) Os grafos abaixo são isomorfos? Justifique