CAMINHO DE EULER

Prévia do material em texto

TEORIA DOS GRAFOS - CAMINHOS DE EULER
Manaus – AM
2018
DIEGO NONATO CABRAL – C998GF7
DOUGLAS CARVALHO ALEGRIA - N856GF4
JACKELINE SUZANNE MACEDO DE MORAES – D05GE8
MARCELO FERREIRA SILVEIRA – C992003
TEORIA DOS GRAFOS - CAMINHOS DE EULER
Trabalho Acadêmico da disciplina Teoria dos Grafos, para obtenção de nota parcial referente a NP1, 5º período do Curso de Ciência da Computação, da Universidade Paulista – UNIP, Campus Manaus. 
Orientador: Prof. Williams Teles de Lima 
Manaus – AM
2018
1 INTRODUÇÃO
A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G (V, E), onde V é um conjunto não vazio de objetos denominados vértices (ou nós) e E é um subconjunto de pares não ordenados de V, chamados arestas.
Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um dígrafo (grafo orientado). Um grafo com um único vértice e sem arestas é conhecido como grafo trivial.
Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de ligações da Wikipédia pode ser representada por um dígrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um tema importante da ciência da computação.
O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, teoria dos grafos e topologia.
Mais de um século após a publicação do artigo de Euler sobre as pontes de Königsberg e enquanto Johann Benedict Listing (matemático alemão) introduziu o conceito de topologia, Arthur Cayley (matemático inglês) foi levado por um interesse em formas analíticas particulares decorrentes do cálculo diferencial para estudar uma classe particular de grafos, as árvores. Esse estudo teve diversas implicações na química teórica. As técnicas usadas por ele eram relacionadas a enumeração de grafos com propriedades particulares.
2 CAMINHO DE EULER
Um Caminho de Euler ou Euleriano é um caminho em um grafo que visita cada aresta apenas uma vez. Com caso especial, um Circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg em 1736.
Um grafo G é dito ser euleriano se há um ciclo em G que contenha todas as suas arestas. Este ciclo é dito ser um ciclo euleriano. O grafo da figura 1 abaixo, por exemplo, é euleriano já que ele contém o ciclo: (u1, u2, u3, u4, u5, u3, u1, u6, u2, u7, u3, u6, u7, u1), que é euleriano.
Figura 1: Grafo Euleriano
O teorema que se segue provê uma solução simples para determinar se um grafo é euleriano:
Teorema: Um multigrafo M é euleriano se e somente se M é conexo e cada vértice de M tem grau par.
Agora, considere um multigrafo G tenha uma trilha (não um ciclo) contendo todas as arestas de M. Então G é dito ser um grafo atravessável e a trilha é dita ser uma trilha euleriana. No grafo (figura 2) abaixo, a trilha: (u1, u2, u3, u4, u1, u3, u5) é atravessável.
Figura 2: Multigrafo G
O teorema seguinte indica precisamente quais grafos são atravessáveis:
Teorema: Um multigrafo M é atravessável se e somente se M é conexo e tem exatamente dois vértices de grau impar. Consequentemente, qualquer trilha euleriana de M começa em um dos vértices de grau impar e termina no outro vértice de grau impar.
Provavelmente, o exemplo mais antigo de problema que faz uso de grafos (ou conceito correlatos) como modelo matemático é o Problema das Pontes de Königsberg. Ele foi resolvido pelo matemático suiço Leonhard Euler (1707-1783) em 1736.
2.1 Problema das Pontes de Königsberg
No século 18 havia na cidade de Königsberg um conjunto de sete pontes (identificadas pelas letras de a até f na figura 3 abaixo) que cruzavam o rio Pregel. Elas conectavam duas ilhas (A e D) entre si e as ilhas com as margens (B e C).
Figura 3: Pontes de Königsberg
Por muito tempo os habitantes daquela cidade perguntavam-se se era possível cruzar as sete pontes numa caminhada contínua sem que se passasse duas vezes por qualquer uma delas.
Este problema pode ser representado por um multigrafo G(V,A), tal que: 
V = { m | m é uma ilha ou uma margem}
A = { (m1,m2, p} | as margens ou ilhas m1 e m2 são ligados pela ponte p} cuja representação gráfica pode ser vista na figura 4 abaixo.
Figura 4: Grafo de Konisberg.
Modelado desta forma, o Problema das Pontes de Königsberg é essencialmente um problema de determinar se o multigrafo correspondente possui uma trilha (possivelmente um ciclo) euleriana. Como os graus de todos os vértices são impares, é fácil verificar que este grafo não apresenta nem uma trilha, nem um ciclo euleriano, visto que ele não satisfaz o Teorema de Euler, nem tampouco é um grafo atravessável. Logo, a travessia proposta não é possível.
2.2 Circuito Euleriano ou Grafo Euleriano
Grafos que possuem um circuito Euleriano são chamados Grafos Eulerianos. Uma das principais condições para um grafo ser Euleriano é que todos os vértices precisam ser de grau par. Entretanto, essa condição não é suficiente, pois também é necessário que o grafo seja conexo.
Euler provou que uma condição necessária para a existência de circuitos eulerianos é de que todos os vértices tenham grau par, e afirmou, sem prova de que grafos conexos com todos os vértices pares tem um circuito Euleriano. A primeira prova completa desta última afirmação foi publicada em 1873 por Carl Hierholzer. 
Há, ainda, grafos com caminhos Eulerianos se houver 2 vértices de grau ímpar. Nesse caso, ao se acrescentar uma aresta ligando estes dois vértices, o novo grafo passa a ser um circuito Euleriano.
Pode-se assim enunciar um corolário do Teorema de Euler para Grafos como sendo: 
Um grafo G conexo possui caminho Euleriano se e somente se ele tem exatamente zero ou dois vértices de grau impar.
2.3 Definições
Definição 1. Um trajeto que inclua todas as arestas de um dado grafo G(V, A) é chamado de trajeto euleriano. Seja G um grafo conexo. Dizemos que G é euleriano se possui um trajeto euleriano fechado. Um grafo G não-euleriano é dito ser semi-euleriano se possui um trajeto euleriano.
Definição 2. Se G (V, A ) é um grafo tal que d ( v ) ≥ 2 para todo v ∈ V , então G contém um ciclo. Demonstração. Se G possui laços ou arestas paralelas, não há o que provar. Vamos supor que G é um grafo simples. Seja v 0 ∈ V um vértice arbitrário de G. Como d ( v ) ≥ 2 para todo v ∈ V , podemos construir um passeio v0 → v1 → v2 · · · indutivamente escolhendo vi+1 como sendo qualquer vértice adjacente a vi exceto vi − 1. Como G possui uma quantidade finita de vértices, em algum momento escolheremos algum vértice, digamos vk, pela segunda vez. A parte do passeio entre e primeira e a segunda ocorrência de vk constitui um ciclo.
Teorema 3 (Euler, 1736). Um grafo conexo G (V, A ) é euleriano se, e somente se, o grau de cada vértice de G é par. Demonstração. ( ⇒) Seja T um trajeto euleriano fechado de G. Cada vez que um vértice v ocorre no trajeto T, há uma contribuição de duas unidades para o grau de v (uma aresta para chegar a v e outra para sair). Isto vale não só para os vértices intermediários mas também para o vértice final, pois “saímos” e “entramos” no mesmo vértice no início e no final do trajeto. Como cada aresta ocorreexatamente uma vez em T, cada vértice possui grau par.
A prova é por indução no número de arestas de G. Suponhamos que o grau de cada vértice de G é par. Como G é conexo, d ( v ) ≥ 2 para todo v ∈ V . Segue então do lema anterior que G contém um ciclo C. Se C contém todas as arestas de G, o teorema está provado. Se não, removemos de G as arestas de C, resultando num grafo H, possivelmente desconexo, com menos arestas do que G.
Figura 5: Grafo H
É fácil ver que todos os vértices de H possuem grau par. Logo, pela hipótese de indução, cada componente de H possui um trajeto euleriano fechado. Além disso, pela conexidade de G, cada componente de H possui ao menos um vértice em comum com C. Portanto, concatenando os trajetos euleriados fechados de cada componente de H com o ciclo C obtemos um trajeto euleriano fechado em G, ou seja, G é um grafo euleriano.
REFERÊNCIAS BIBLIOGRÁFICAS
<<GrafosEulerianos>>http://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/socorro4029/geuleriano_2014_3.pdf. - Acessado em 23 de março de 2018. 
 «Grafos Eulerianos». www.inf.ufsc.br. Consultado em 15 de julho de 2015LÉVY, M. S. P. Elementos para uma História das Ciências III: de Pasteur ao computador.[S.l.]: Lisboa, Terramar, 1989.
R. Rossetti, A.P. Rocha, A. Pereira, P.B. Silva, T. Fernandes FEUP, MIEIC, CPAL, 2010/2011