EXERCÍCIOS DE TEORIA DOS GRAFOS 2a UNIDADE

Prévia do material em texto

LISTA DE EXERCÍCIOS DE INTRODUÇÃO À TEORIA DOS GRAFOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Problema 4 
O Problema das Sete Pontes de Königsberg é um problema matemático famoso e resolvido por 
Euler. Existe um percurso que passe exatamente uma vez por cada uma das sete pontes da antiga cidade de 
Königsberg? Euler respondeu que não. 
 
 a) Modele o problema como um grafo: 
_ Quem são os vértices? Quem são as arestas? Escreva uma pergunta sobre um grafo que seja equivalente 
ao problema das pontes. 
b) A figura da direita é uma casa. É apresentada com um desafio para crianças: desenhar sem tirar a ponta 
do lápis do papel e sem repetir linhas. Argumente que os dois problemas são os mesmos, mas para grafos 
diferentes. Desenhe o grafo para cada problema e conte o grau de cada vértice. Quantos vértices de grau par 
e ímpar tem cada um? 
_ Você consegue fazer o desenho da direita, sem levantar o lápis ou repetir linhas, mas começando pelo 
telhado? 
Problema 05 
Escreva a matriz de adjacência dos grafos abaixo: 
 
 
 
 
 
Problema 06 
 
Problema 07 
 
 
 
 
 
 
Problema 08 
 
 
 
09. Dado um grafo G e um vértice de origem, qual é o algoritmo de busca que descobre todos os vértices a 
uma distância K do vértice origem, antes de descobrir qualquer vértice a uma distância K+1? 
 
(A) Pré-ordem. 
(B) Largura. 
(C) Pós-ordem. 
(D) Profundidade. 
(E) Simétrica. 
 
10. Em relação ao grafo da Figura (a), as Figuras (b) e (c) representam, respectivamente, 
 
A) matriz de arestas e lista de incidências. 
B) matriz de adjacências e lista de adjacências. 
C) matriz de conexões e lista de arestas. 
D) matriz de incidências e lista de vértices. 
E) matriz de vértices e lista de conexões. 
 
11. A matriz de um grafo G = (V,A) contendo n vértices é uma matriz n x n de bits, em que A[i,j] é 1 (ou 
verdadeiro, no caso de booleanos) se e somente se existir um arco do vértice i para o vértice j. Essa definição 
é uma: 
A) Matriz de adjacência para grafos não ponderados. 
B) Matriz de recorrência para grafos não ponderados. 
C) Matriz de incidência para grafos não ponderados. 
D) Matriz de adjacência para grafos ponderados. 
E) Matriz de incidência para grafos ponderados. 
 
12. A Figura (a) abaixo mostra o exemplo de um grafo não direcionado G com os pesos mostrados ao lado 
de cada aresta. Sobre a árvore T representada na Figura (b), é correto afirmar que: 
 
 
A) T representa a árvore geradora mínima do grafo da Figura (a) cujo peso total é 12. T não é única, 
pois a substituição da aresta (3,5) pela aresta (2,5) produz outra árvore geradora de custo 12. 
B) T representa a árvore de caminhos mais curtos entre todos os pares de vértices do grafo da Figura 
(a). T não é única, pois a substituição da aresta (3,5) pela aresta (2,5) produz caminhos mais 
curtos entre os mesmos pares de vértices do grafo. 
C) T representa a árvore geradora mínima do grafo da Figura (a) cujo peso total é 12. A substituição 
da aresta (3,5) pela aresta (2,4) produz uma árvore geradora máxima cujo peso total é 14. 
D) T representa a ordenação topológica do grafo da Figura (a). O peso da aresta (0,2) indica que ela 
deve ser executada antes da aresta (2,3) e o peso da aresta (2,3) indica que ela deve ser executada 
antes da aresta (4,5) e assim sucessivamente. 
E) T representa a árvore de caminhos mais curtos do grafo da Figura (a) com origem única no vértice 
2. T não é única, pois a substituição da aresta (3,5) pela aresta (2,4) produz caminhos mais curtos 
entre todos os pares de vértices do grafo. 
 
 
13. Em relação a Teoria dos Grafos, relacione a Coluna 1 à Coluna 2. 
 
Coluna 1 
1. Grafo Completo. 
2. Hipergrafo. 
3. Árvore Livre. 
4. Grafo Planar. 
5. Grafo não direcionado antirregular. 
 
Coluna 2 
 
( ) Grafo não direcionado, no qual todos os pares de vértices são adjacentes entre si. 
( ) Grafo não direcionado em que cada aresta conecta um número arbitrário de vértices, ao invés de conectar 
dois vértices apenas. 
( ) Grafo não direcionado acíclico e dirigido. 
( ) Grafo em que seu esquema pode ser traçado em um plano, de modo que duas arestas quaisquer se toquem, 
no máximo, em alguma extremidade. 
( ) Grafo que possui o maior número possível de graus diferentes em sua sequência. 
A ordem correta de preenchimento dos parênteses, de cima para baixo, é: 
 
A) 1 – 2 – 3 – 4 – 5. 
B) 2 – 3 – 4 – 5 – 1. 
C) 3 – 4 – 5 – 1 – 2. 
D) 4 – 5 – 1 – 2 – 3. 
E) 5 – 1 – 2 – 3 – 4. 
 
14. Seja G = (V, E) um grafo em que V é o conjunto de vértices e E é o conjunto de arestas. Considere a 
representação de G como uma matriz de adjacências. 
 
O correspondente grafo orientado G é: 
 
 
 
 
15. Sobre árvores binárias, considere as afirmativas a seguir. 
 
I. Qualquer nó de uma árvore binária é raiz de, no máximo, outras duas subárvores comumente denominadas 
subárvore direita e subárvore esquerda. 
 
II. Uma dada árvore binária A armazena números inteiros e nela foram inseridos 936 valores não repetidos. 
Para determinar se um número x está entre os elementos dessa árvore, tal número será 
comparado, no máximo, com 10 números contidos na árvore A. 
 
III. Uma dada árvore binária de busca A armazena números inteiros e nela foram inseridos 936 valores 
não repetidos. Para determinar se um número x está entre os elementos dessa árvore, serão feitas, 
no máximo, 10 comparações. 
 
IV. Uma dada árvore binária de busca A armazena números inteiros e nela foram inseridos 936 valores 
não repetidos. Supondo que r seja o nó raiz da árvore A e que sua subárvore esquerda contenha 
460 elementos e sua subárvore direita possua 475 elementos. Para determinar se um número x pertence a essa 
árvore, serão feitas, no máximo, 476 comparações. 
 
Assinale a alternativa correta. 
a) Somente as afirmativas I e II são corretas. 
b) Somente as afirmativas I e IV são corretas. 
c) Somente as afirmativas III e IV são corretas. 
d) Somente as afirmativas I, II e III são corretas. 
e) Somente as afirmativas II, III e IV são corretas 
 
16. Assinale a alternativa que apresenta, corretamente, o algoritmo utilizado para determinar o caminho 
mínimo entre todos os pares de vértices de um grafo. 
 
a) Bellman-Ford. 
b) Floyd-Warshall. 
c) Dijkstra. 
d) Kruskal. 
e) Prim 
 
17. Considere um grafo não dirigido G = (V, E), onde V é o conjunto de vértices e E o conjunto de arestas, 
no qual cada aresta possui um peso. G é uma instância para o Problema do Caixeiro Viajante (PCV), onde 
cada um de seus vértices são cidades e cada uma de suas arestas corresponde à ligação entre essas 
cidades. O peso de cada aresta corresponde à distância entre as duas extremidades. 
A árvore de busca, a seguir, corresponde à busca pela solução realizada por um algoritmo para o PCV. 
Sabendo-se que a busca pela solução ocorreu por profundidade, os nós da árvore de busca são analisados, 
explorando os “filhos” mais à esquerda primeiro (vértices com menor número). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Com base na estratégia de “poda” a ser utilizada para melhorar o desempenho e na análise das características 
da árvore de busca sobre a instância G, atribua V (verdadeiro) ou F (falso) às afirmativas a seguir. 
 
( ) Ao encontrar o primeiro melhor caminho, deve-se registrá-lo, para não analisar caminhos que possuam 
mais vértices que este. 
( ) Durante a abertura dos nós na árvore de busca, parar de seguir o caminho quando um ciclo é pior 
que o melhor encontrado até então. 
( ) Manter o ciclo hamiltoniano de menor custo encontrado até então. Se, durante a busca, o caminho 
analisado ultrapassar este menor custo, parar tentativa por aquele caminho. 
( ) Manter a distância atual do caminho percorrido e evitar abrir nós que a ultrapassem. 
( ) Não realizar caminhos inversos aos que já foram analisados. 
Assinale a alternativa que contém,de cima para baixo, a sequência correta. 
 
a) V, V, F, V, F. 
b) V, F, V, F, V. 
c) F, V, F, V, F. 
d) F, V, F, F, V. 
e) F, F, V, F, V. 
 
18. Observe a Árvore Binária de Busca (ABB) a seguir: 
 
 
 
Assinale a alternativa que apresenta, corretamente, a sequência de inserção que gera essa ABB. 
a) 30, 15, 40, 10, 20, 60, 80 
b) 30, 15, 40, 10, 20, 80, 60 
c) 30, 15, 60, 10, 20, 40, 80 
d) 30, 60, 20, 80, 15, 10, 40 
e) 30, 60, 40, 10, 20, 15, 80 
 
19. Um problema das árvores binárias de buscas convencionais é que a disposição dos elementos pode ficar 
semelhante à de uma estrutura linear, na qual as árvores criam uma profundidade maior que sua largura, 
como ocorre, por exemplo, em inserção de chaves em ordem crescente. Em árvores com essa característica, 
não há ganho substancial quanto ao tempo de busca de uma lista, por exemplo. As árvore AVL e SBB 
são árvores projetadas para evitar esse problema e balancear o tempo de busca a seus elementos. 
Quanto às árvores AVL e SBB, assinale a alternativa que apresenta, corretamente, suas características. 
 
a) Árvores AVL utilizam altura das subárvores como critério de balanceamento, enquanto árvores SBB 
utilizam orientação vertical e horizontal dos “apontadores” dos nós. 
 
b) Árvores AVL utilizam quatro tipos diferentes de algoritmos de balanceamento, enquanto árvores SBB 
utilizam apenas dois tipos genéricos (direita e esquerda), levando em consideração a origem e a propagação 
de uma violação. 
c) Árvores SBB utilizam alturas das subárvores como critério de balanceamento, enquanto árvores AVL 
utilizam orientação vertical e horizontal dos “apontadores” dos nós. 
 
d) Árvores SBB utilizam quatro tipos diferentes de algoritmos de balanceamento, enquanto árvores AVL 
utilizam apenas dois tipos genéricos (direita e esquerda), levando em consideração a origem e a propagação 
de uma violação. 
e) As árvores AVL e SBB possuem diferença quanto à estrutura dos nós e à composição das chaves e das 
funções de busca, de inserção e de remoção. 
 
20.. Execute o algoritmo de Dijkstra para determinar especificamente o menor caminho entre os vértices a e 
m do grafo abaixo. 
 
 
 
21. Execute o algoritmo de Floyd-Warshall para o grafo abaixo, especificamente para determinar o menor 
caminho entre os vértices 1 e 5. Esta mesma tarefa poderia ser realizada corretamente pelo algoritmo de 
Dijkstra?