Exerc_cio_II_ALGORITMOS_EM_GRAFOS_-_GABARITO

Prévia do material em texto

ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II - GABARITO 
1) Qual é a diferença entre um grafo direcionado e um grafo não direcionado? Dê um exemplo de 
cada. 
Resposta: Um grafo é um par de conjuntos: um conjunto de coisas conhecidas como vértices e um 
conjunto de coisas conhecidas como arcos. Cada arco é um par ordenado de vértices. O primeiro 
vértice do par é a ponta inicial do arco e o segundo é a ponta final. Um grafo não dirigido consiste 
de um conjunto de vértices e um conjunto de arestas (pares de vértices não ordenados), enquanto 
um digrafo é constituído por um conjunto de vértices e um conjunto de arcos (pares ordenados de 
vértices). 
A diferença entre um grafo dirigido (ou direcionado) para um grafo não dirigido (ou não 
direcionado) é que em um grafo não dirigido pode-se tanto ir quanto voltar de um vértice para o 
outro. Abaixo, o 1º grafo é não dirigido e o 2º grafo é dirigido, ou seja, um dígrafo. 
 
 
2) O que é um vértice isolado em um grafo? Como você o identifica? 
Resposta: Dois vértices 𝑥 e 𝑦 são adjacentes se e somente se existe uma aresta {𝑥, 𝑦} ∈ 𝐴. Neste 
caso, dizemos que a aresta {𝑥, 𝑦} é incidente aos vértices 𝑥 e 𝑦. Quando um vértice não é adjacente 
a outro, dizemos que ele é um vértice isolado. Em um grafo simples, o grau de vértice é igual ao 
número de vizinhos que ele possui. Se um vértice é isolado, então ele possui grau igual a zero (0). 
Outra forma de identificar um vértice isolado é através dos algoritmos de busca em Largura e Busca 
em Profundidade. Se um vértice é isolado, ele nunca será alcançado pelos algoritmos de busca. 
 
3) O que é um grafo euleriano? Quais são as condições para um grafo ser euleriano? 
Resposta: Um grafo conectado 𝐺 é dito Euleriano se existe uma trilha fechada contendo cada uma 
das arestas de 𝐺. 
• Um grafo conectado 𝐺 é Euleriano se e somente se o grau de cada vértice é par. 
• Seja 𝐺 = (𝑉, 𝐸) euleriano e seja um ciclo euleriano em 𝐺. Ao percorremos esse ciclo a 
partir de um vértice dado, cada vez que atravessarmos um vértice utilizaremos duas arestas, 
uma na chegada e outra na saída. Logo, o grau de cada vértice deve ser obrigatoriamente 
par 
 
4) Explique o que é um grafo hamiltoniano e forneça um exemplo de grafo hamiltoniano e um que não 
seja. 
Resposta: Um grafo hamiltoniano é um caminho hamiltoniano que retorna ao vértice inicial. Ou 
seja, um grafo é dito hamiltoniano se possui um ciclo hamiltoniano. Seja 𝐺 um grafo simples com 𝑛 ≥ 3 
vértices. Se 𝑔𝑟𝑎𝑢(𝑣) ≥ 𝑛/2, ∀𝑣 ∈ 𝑉(𝐺) então 𝐺 é Hamiltoniano. Seja 𝐺 um grafo simples, se 𝑔𝑟𝑎𝑢(𝑢) +
𝑔𝑟𝑎𝑢(𝑣) ≥ 𝑛 para todo 𝑢, 𝑣 não adjacente, então 𝐺 é Hamiltoniano. Abaixo, o 1º grafo é hamiltoniano e 
o 2º grafo é não hamiltoniano. 
 
 
 
ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II - GABARITO 
 
 
 
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: Algoritmo de Busca em Profundidade. 
b. Encontrar todos os ciclos em um grafo: Algoritmo de Busca em profundidade. Você pode 
iniciar uma busca em profundidade a partir de cada vértice do grafo e acompanhar o 
caminho percorrido. Se a busca em profundidade retornar a um vértice já visitado (que 
não seja o pai do vértice atual), você encontrou um ciclo. 
c. O caminho mais curto em um grafo: Algoritmo de Dijkstra ou Bellman-Ford. 
d. Colorir um grafo, tal que vértices adjacentes tenha cores diferentes: Algoritmo DSATUR ou 
Welsh-Powell. 
e. Colorir um grafo bipartido: Divida os vértices do grafo em dois conjuntos disjuntos: 
Identifique os conjuntos de vértices de maneira que não haja arestas conectando vértices 
dentro do mesmo conjunto. Isso pode ser feito usando técnicas de bipartição, como o 
algoritmo de busca em largura (BFS). 
 
 
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: 
 
Resposta: 
 
Matriz de Adjacência 
Lista de Adjacência 
 
 
ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II - GABARITO 
7) Explique o teorema das quatro cores e seu significado na teoria dos grafos. 
Resposta: Como colorir um mapa é um problema usual e clássico, daí surgiu o problema de colorir um 
grafo, já que um grafo planar representa um mapa. Para colorir um mapa, devemos seguir algumas 
restrições, onde regiões que são vizinhas recebem cores diferentes, para que essas regiões não conflitem na 
visualização do mapa. Além dessa restrição, podemos inserir uma questão de otimização: Qual a quantidade 
mínima de cores posso colorir um mapa? As questões que acabamos de ver foram necessárias para o 
surgimento de um problema clássico em computação: Problema das Quatro cores. Quatro cores são 
suficientes para colorir as regiões de qualquer mapa sem que duas regiões adjacentes recebam a mesma cor. 
Definição 1. Uma coloração de um grafo simples é o rotulamento de uma cor a cada vértice do grafo tal que 
dois vértices adjacentes não possuem a mesma cor. A sua importância para a Teoria dos grafos vem do fato 
de que o problema das quatro cores pode ser representado por grafos, além de modelar diversos problemas 
do mundo real. 
 
 
 
8) Defina o teorema de Kuratowski e explique sua importância na teoria dos grafos. 
Resposta: O Teorema de Kuratowski é um resultado fundamental na teoria dos grafos e é usado 
para identificar a presença de subgrafos específicos em um grafo. O teorema estabelece condições 
sob as quais um grafo é considerado "não planar", o que significa que ele não pode ser desenhado 
em um plano (em um plano bidimensional) sem que as arestas se cruzem. O teorema é nomeado 
em homenagem ao matemático polonês Kazimierz Kuratowski, que o enunciou em 1930. 
O Teorema de Kuratowski afirma que um grafo é não planar se e somente se ele contiver um 
subgrafo que seja uma subdivisão e/ou subgrafo do grafo completo 𝐾5 ou do grafo bipartido 
completo 𝐾3,3 (grafo bipartido completo com 3 vértices de cada lado). Isso significa que, se você 
encontrar uma subdivisão de em um grafo, então esse grafo é não planar. 
 
 
 
ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II - GABARITO 
 
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. 
 
Resposta: 
 
 
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. 
 
Resposta: O resultado obtido pelos algoritmos de Prim e Kruskal geram a mesma Árvore Geradora. 
Segue: 
 
 
 
ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II - GABARITO 
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 comgrafos 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. 
 
 
 
 
 
ARA0175 – ALGORITMOS EM GRAFOS 
Lista de Exercícios II - GABARITO 
Referências Bibliográficas 
[1] 
[2] 
[3] 
[4] https://www.inf.ufrgs.br/~prestes/Courses/Graph%20Theory/Capitulo%201.pdf 
[5] 
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphs.html#:~:text=Um%20v%C3%A9rtice%20%C3%A9
%20isolado%20se,por%20seu%20conjunto%20de%20arcos. 
[6] 
https://www.inf.ufrgs.br/~prestes/Courses/Graph%20Theory/Capitulo%201.pdf
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphs.html#:~:text=Um%20v%C3%A9rtice%20%C3%A9%20isolado%20se,por%20seu%20conjunto%20de%20arcos
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphs.html#:~:text=Um%20v%C3%A9rtice%20%C3%A9%20isolado%20se,por%20seu%20conjunto%20de%20arcos