Baixe o app para aproveitar ainda mais
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
Compartilhar