Grafos e Árvore

TRABALHO DE PESQUISA Não se esqueça de anotar as fontes de pesquisa ao final do texto 1 Explique DETALHADAMENTE dois problemas representados ou resolvidos utilizando grafos Apresente a formulação matemática e uma proposta de solução de cada problema 20 2 Explique DETALHADAMENTE um problema representado ou resolvido utilizando Árvore Apresente a formulação matemática e uma proposta de solução do problema 10 Obs O problema de árvore geradora de custo mínimo não pode ser utilizado Abaixo um padrão de explicação detalhada a ser seguido httpsdocsufprbrvolmirPOII11arvoregeradoraminimapdf Trabalho de Pesquisa Problemas com Grafos e Árvores June 10 2024 1 Problemas Representados com Grafos 11 Problema do Caminho Mínimo Descrição O Problema do Caminho Mínimo consiste em encontrar o caminho de menor custo entre dois vértices em um grafo ponderado Esse problema é fundamental em diversas áreas como redes de transporte telecomunicações e algoritmos de roteamento Formulação Matemática Dado um grafo G VE onde V é o conjunto de vértices e E é o conjunto de arestas e uma função de peso w E ℝ que atribui um peso a cada aresta o problema é encontrar um caminho P de um vértice s para um vértice t tal que a soma dos pesos das arestas em P seja mínima Matematicamente queremos minimizar uvP wuv Proposta de Solução Um dos algoritmos mais conhecidos para resolver o Problema do Caminho Mínimo é o Algoritmo de Dijkstra O Algoritmo de Dijkstra funciona da seguinte maneira 1 Inicialize a distância de cada vértice v de V como e a distância da origem s como 0 2 Coloque todos os vértices em um conjunto prioritário Q onde a prioridade é determinada pela distância atual 3 Enquanto Q não estiver vazio a Extraia o vértice u de Q com a menor distância b Para cada vizinho v de u relaxe a aresta uv Se dv du wuv então dv du wuv Atualize a prioridade de v em Q Graph Image Figure 1 Grafo para o Problema do Caminho Mínimo 12 Problema do Caixeiro Viajante Descrição O Problema do Caixeiro Viajante TSP é um problema de otimização combinatória onde um caixeiro viajante deve visitar um conjunto de cidades exatamente uma vez e retornar à cidade de origem minimizando a distância total percorrida Formulação Matemática Dado um grafo completo G VE onde V é o conjunto de vértices representando as cidades e E é o conjunto de arestas representando os caminhos entre as cidades com uma função de peso w E ℝ que atribui um custo a cada aresta o objetivo é encontrar um ciclo hamiltoniano de menor custo Matematicamente queremos minimizar uvC wuv onde C é um ciclo que visita cada vértice exatamente uma vez Proposta de Solução Uma solução exata para o TSP pode ser obtida utilizando Programação Dinâmica com o algoritmo de HeldKarp que tem complexidade On² 2ⁿ O algoritmo funciona da seguinte maneira 1 Defina DPSi como o menor custo para alcançar o conjunto de vértices S terminando no vértice i 2 Inicialize DPss 0 para a cidade de origem s 3 Para cada subconjunto S de V que contém s e para cada vértice i em S a Atualize DPSi considerando todos os caminhos possıveis para i a partir de um vertice j em S DPSi minDPS ij wj i para todo j S 4 A solucao final e obtida minimizando DPV i wi s para todo i V s Figure 2 Grafo para o Problema do Caixeiro Viajante 2 Problema Representado com Arvore 21 Problema de Busca Binaria Descricao O problema de busca em uma arvore binaria de busca BST en volve encontrar um elemento na arvore de forma eficiente A BST e uma estru tura de dados onde cada no tem no maximo dois filhos e os nos sao organizados de tal forma que para qualquer no n todos os elementos no subarvore esquerda de n sao menores que n e todos os elementos na subarvore direita de n sao maiores que n Formulacao Matematica Uma arvore binaria de busca e definida como T N E onde N e o conjunto de nos e E e o conjunto de arestas Cada no n tem um valor keyn tal que n N nl leftn nr rightn se nl e um descendente esquerdo de n entao keynl keyn e se nr e um descendente direito de n entao keynr keyn 3 Proposta de Solucao A busca em uma BST pode ser realizada de forma recursiva ou iterativa Busca Recursiva def searchbstnode key if node is None or nodekey key return node if key nodekey return searchbstnodeleft key else return searchbstnoderight key Busca Iterativa def searchbstiterativenode key while node is not None and nodekey key if key nodekey node nodeleft else node noderight return node A busca em uma BST tem complexidade Oh onde h e a altura da arvore No melhor caso quando a arvore e balanceada h logn tornando a busca muito eficiente Figure 3 Arvore Binaria de Busca 4 3 Conclusao Os problemas discutidos demonstram a importˆancia dos grafos e das arvores como ferramentas fundamentais na computacao e na resolucao de problemas complexos O Problema do Caminho Mınimo e o Problema do Caixeiro Via jante exemplificam como os grafos podem ser utilizados para modelar e resolver problemas de otimizacao enquanto o problema de busca em uma arvore binaria de busca ilustra a eficiˆencia das arvores na organizacao e busca de dados 4 Fontes de Pesquisa Algorithm Design by Jon Kleinberg and Eva Tardos Introduction to Algorithms by Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Dijkstras Algorithm httpsenwikipediaorgwikiDijkstra Travelling Salesman Problem Binary Search Tree httpsenwikipediaorgwikiBinarysearchtree 5