Teoria de Grafos Exercícios Comentados

Prévia do material em texto

Teoria dos Grafos
Módulo 1
Definição e Aplicações de Grafos
Terminologia da Teoria dos Grafos
 
Clique no ícone para baixar o módulo 1 completo em pdf
Para facilitar a navegação é recomendável que você clique com o botão
direito do mouse e selecione “abrir link em nova guia” ou “abrir link em
nova janela”. Desta forma o arquivo abrirá separadamente.
 
 
 
Exercício 1:
O grafo da figura possui ordem igual à:
https://online.unip.br/Arquivo?id=38948.PDF
A)
2
B)
3
C)
4
D)
5
E)
6
O aluno respondeu e acertou. Alternativa(D)
Comentários:
D) Ordem 5 pela quantidade de vértices.
Exercício 2:
No grafo da figura, vértice 4 possui grau à:
A)
2 
B)
 
3
C)
4
D)
5
E)
6
O aluno respondeu e acertou. Alternativa(A)
Comentários:
A) Esta ligados pelo vértice 1 e 2.
Exercício 3:
No grafo da figura, ao passarmos pelos vértices 1;3;2;5;1
respectivamente, é correto afirmar que:
A)
Estamos fazendo um ciclo de comprimento igual a 5 mas este ciclo não
é simples.
B)
Estamos fazendo um ciclo simples de comprimento igual a 4.
C)
Não estamos fazendo ciclo, pois o grafo é acíclico.
D)
 Para o percurso ser considerado um ciclo é necessário passar pelo
vértice 4.
E)
Para o percurso ser considerado um ciclo é necessário que tenha pelo
menos um laço.
O aluno respondeu e acertou. Alternativa(B)
Comentários:
B) No exemplo, ele não passa pelo vértice 4 mas consegue
completar o ciclo.
Exercício 4:
O grafo da figura possui 4 vértices. È correto afirmar que:
A)
Este grafo é direcionado.
B)
Este grafo apresenta um vértice de grau igual 1.
C)
Este grafo não apresenta um vértice de grau igual 3.
D)
Este grafo possui ordem igual 6.
E)
Este grafo possui 1 laço.
O aluno respondeu e acertou. Alternativa(E)
Comentários:
E) Um dos vértices ela com 1 laço.
Exercício 5:
No grafo acima o vértice de maior grau é o de número:
A)
5
B)
6
C)
7
D)
8
E)
9
O aluno respondeu e acertou. Alternativa(B)
Comentários:
B) 6 está ligado a outras 4 vértices.
Exercício 6:
Podemos afirmar que a soma dos graus dos vértices de um grafo G
não direcionado, é sempre um número:
A)
maior que 4
B)
par
C)
ímpar
D)
primo
E)
igual ao seu número de arestas.
O aluno respondeu e acertou. Alternativa(B)
Comentários:
B) Ela vai possuir duas arestas.