PASSEIOS EM TEORIA DOS GRAFOS.

A teoria dos grafos teve início no ano de 1736 com a resolução do problema das pontes de Konigsberg, pelo matemático suíço Leonhard Euler (1707-1782). No rio Pregel de Konigsberg existiam duas ilhas e sete pontes ligando as ilhas entre si e às margens do rio. E o problema questionava se era possível atravessar cada uma das pontes uma única vez e voltar ao ponto de partida. Através da Teoria dos Grafos, Euler concluiu que não isso era possível. Formalmente, um grafo G consiste em um par (V(G), A(G)), onde V(G) é um conjunto não vazio denominado conjunto de vértices e A(G) é um conjunto formado por pares não ordenados de elementos de V(G), denominado conjunto das arestas. Para resolver o problema Euler associou cada ilha e margem do rio a um único ponto e definiu um grafo, G, onde cada vértice corresponde a um desses pontos e cada arestas corresponde a um par de pontos conectados por uma ponte da cidade. Ele provou que o percurso desejado existe se, e somente se, todo vértice deste grafo pertence a uma quantidade par de arestas. Outro problema bem conhecido da teoria dos grafos é o problema do caixeiro viajante, onde o objetivo do caixeiro é sair de sua cidade passar por um certo conjunto de cidades e retornar, sendo que ele só pode passar em cada cidade uma única vez e precisa percorrer a menor distância possível. Esse problema possui inúmeras aplicações, como por exemplo, aquelas que visam minimizar custos de transporte em rotas de diversos tipos. Grafos também são bastante úteis para modelar problemas nas áreas da computação, da indústria e até mesmo de outros ramos da matemática. Este trabalho teve como objetivo estudar conceitos básicos relacionados a grafos e algumas aplicações clássicas, como as duas citadas acima, a fim de ambientar um estudo futuro sobre este tema. Observa-se que pequenas variações no enunciado de um problema pode torna-lo bem mais simples ou bem mais difícil.