Lista_de_Exercicios_2_-_ALGORITMOS_EM_GRAFOS

Prévia do material em texto

ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II 
1) Qual é a diferença entre um grafo direcionado e um grafo não direcionado? Dê um exemplo de 
cada. 
 
2) O que é um vértice isolado em um grafo? Como você o identifica? 
 
3) O que é um grafo euleriano? Quais são as condições para um grafo ser euleriano? 
 
 
4) Explique o que é um grafo hamiltoniano e forneça um exemplo de grafo hamiltoniano e um que não 
seja. 
5) Dada as seguintes situações em grafos abaixo, indique qual / quais algoritmos podem ser usados 
para resolver os problemas: 
a. Descobrir se um grafo é conexo: 
b. Encontrar todos os ciclos em um grafo: 
c. O caminho mais curto em um grafo: 
d. Colorir um grafo, tal que vértices adjacentes tenha cores diferentes: 
e. Colorir um grafo bipartido: 
6) Elabore a matriz de adjacência e lista de adjacência dos grafos abaixo. Insira os vértices na sua ordem 
de rotulação: 
 
7) Explique o teorema das quatro cores e seu significado na teoria dos grafos. 
8) Defina o teorema de Kuratowski e explique sua importância na teoria dos grafos. 
9) Seja o grafo abaixo e sua respectiva Lista de Adjacência, dê a busca em Largura e a busca em 
profundidade, seguindo a ordem em que os vértices estão dispostos na lista de adjacência. 
 
10) Seja o grafo ponderado abaixo. Execute o algoritmo de Prim e de Kruskal e observe se a mesma 
árvore geradora é obtida dos dois algoritmos. 
 
 
ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II 
 
11) Qual é o objetivo principal dos algoritmos de caminho mínimo em teoria dos grafos? 
A) Encontrar o caminho mais longo em um grafo. 
B) Encontrar o caminho com o menor número de arestas em um grafo. 
C) Encontrar o caminho com a menor soma de pesos em um grafo. 
D) Encontrar o caminho que visita todos os vértices de um grafo. 
 
12) Qual é a principal diferença entre os algoritmos de Dijkstra e Bellman-Ford para encontrar caminhos 
mínimos? 
A) Dijkstra funciona apenas em grafos ponderados. 
B) Bellman-Ford lida apenas com grafos não direcionados. 
C) Dijkstra é mais eficiente que Bellman-Ford em todos os casos. 
D) Bellman-Ford pode lidar com arestas com pesos negativos, enquanto Dijkstra não. 
 
13) Qual é a principal aplicação das árvores geradoras mínimas? 
A) Coloração de vértices. 
B) Roteamento em redes de computadores. 
C) Encontrar ciclos em um grafo. 
D) Classificação de vértices em um grafo. 
 
14) Qual é a principal diferença entre os algoritmos de Kruskal e Prim para encontrar árvores geradoras 
mínimas? 
A) Kruskal funciona apenas em grafos ponderados, enquanto Prim funciona em qualquer tipo de 
grafo. 
B) Kruskal lida apenas com grafos direcionados, enquanto Prim lida com grafos não direcionados. 
C) Kruskal encontra a árvore geradora mínima mais leve, independentemente da conectividade, 
enquanto Prim inicia a partir de um vértice específico. 
D) Kruskal sempre encontra um ciclo mínimo no grafo. 
 
15) Quais são as condições que um grafo deve atender para garantir a existência de uma árvore 
geradora mínima? 
 
A) Ser um grafo completo. 
B) Ser um grafo direcionado. 
C) Ser conectado e ponderado. 
D) Ter um ciclo hamiltoniano.