Grafos Eulerianos: Teoria e Exercícios Práticos

Grafos Eulerianos Teoria dos Grafos 2021 Prof Roberto C de Araujo Teoria dos Grafos 2021 Problema das 7 pontes de Königsberg atualmente Kaliningrado É possível achar um passeio que começando em uma das regiões de terra de Königsberg A B C ou D passe uma vez em cada ponte e volte à região de origem Podemos definir um grafo G desta forma vértices regiões de terra aresta pontes ligando as regiões correspondentes Euler provou que um tal passeio não existe Ele provou também resultados mais gerais sobre outros problemas do mesmo tipo 1 Grafos Eulerianos Uma trilha que passa por todas as arestas de um grafo G é chamada de trilha de Euler de G Um grafo G é euleriano se G contém uma trilha de Euler fechada Exercício Dado o grafo G abaixo encontre uma trilha de Euler fechada em G Teorema Um grafo conexo não vazio e não trivial é euleriano se e somente se não contém vértices de grau ímpar Corolário Se G é um grafo conexo com exatamente dois vértices uv de grau ímpar então G tem uma trilha de Euler com início em u e término em v Corolário Um grafo conexo tem uma trilha de Euler se e somente se tem no máximo 2 vértices de grau ímpar 2 Algoritmo de Fleury Dado um grafo G devolve um trilha T em G Inicialização escolha v0VG e faça T0 v0 Passo supondo que a trilha Ti v0a1v1aivi já foi escolhida escolha ai1AG a1 ai tal que a vi é extremo de ai1 b a menos que não seja possível ai1 não é aresta de corte de Gi G a1 ai e faça Ti1 Tivi ai1 vi1 Repita o Passo até que ele não possa mais ser implementado Teorema Se G é euleriano então qualquer trilha em G construída pelo algoritmo de Fleury é uma trilha de Euler fechada em G 3 Exercícios 1 O grafo G desenhado abaixo é euleriano Justifique Caso afirmativo apresente uma trilha de euler fechada em G Caso contrário a Qual é a quantidade mínima de arestas que devem ser acrescentadas a AG de tal forma que o grafo resultante seja euleriano b Redesenhe o grafo obtido com a inclusão das arestas determinadas no item anterior c Obtenha uma trilha de Euler fechada no grafo obtido simulando passo a passo o algoritmo de Fleury 2 Faça uma pesquisa sobre O Problema do Carteiro Chinês Escolher uma rota para que um carteiro saindo do correio percorra todas as ruas de sua área entregando cartas e retorne ao correio andando o mínimo possível