Notas de Aula: Teoria dos Grafos

Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Notas de aula da disciplina Teoria dos Grafos Esse material é um compilado dos seguintes Sedgewick R Algorithms in C part 5 graph algorithms 3rd ed AddisonWesley 2002 Bondy J A Murty U S R Graph Theory Graduate Texts in Mathematics Springer New York 2008 Lintzmayer C N Mota G O Notas de aulas Análise de algoritmos e estruturas de dados Em construção 13 Aula 18 grafos eulerianos e hamiltonianos Seja G um grafo conexo Dizemos que uma trilha fechada T é uma trilha Euleriana se ET EG G é um grafo Euleriano se contém uma trilha Euleriana uma trilha T é uma trilha Euleriana aberta se ET EG O Problema das Pontes de Königsberg é equivalente ao problema de detectar se o grafo que representa o mapa da cidade possui uma trilha Euleriana Também relacionado a grafos Eulerianos está o Problema do Carteiro Chinês dados um grafo G com w EG R encontrar o menor passeio que visita todas as arestas pelo menos uma vez Esse problema pode ser resolvido em tempo polinomial Dizemos que um ciclo C é um ciclo Hamiltoniano se C é gerador V C V G G é um grafo Hamiltoniano se contém um ciclo Hamiltoniano um caminho C é um caminho Hamiltoniano se C é gerador Relacionado a grafos Hamiltonianos está o Problema do Caixeiro Viajante TSP de Traveling Salesman Problem dados um grafo G e w EG R encontrar um ciclo Hamiltoniano de custo mínimo em G Esse problema é NPdifícil Na verdade simplesmente decidir se um dado grafo G possui um ciclo Hamiltoniano ou um caminho Hamiltoniano já é NPcompleto Por outro lado existem algoritmos eficientes para decidir se um grafo G possui uma trilha Euleriana ou apenas decidir se G é Euleriano Para grafos Eulerianos são conhecidas caracterizações Para grafos Hamiltonianos ainda não são E caso existam provavelmente não darão algoritmos eficientes Note que como os conceitos de ciclo e caminho estão bem definidos para digrafos esses problemas estão naturalmente bem definidos em digrafos também 91 131 Grafos Eulerianos Observe como se comporta uma trilha Euleriana aberta quando ela passa pelos vértices do grafo Nesse contexto dizemos que um grafo é par se todos os seus vértices têm grau par O teorema a seguir dá uma caracterização para grafos Eulerianos A ida é um resultado de Euler de 1736 e a volta é um resultado de Hierholzer de 1873 Teorema 131 Um grafo conexo G é Euleriano se e somente se G é par Demonstração Considere um grafo G conexo Primeiro vamos mostrar que se G é euleriano então G é par Seja C v1 v2 vk vk1 uma trilha Euleriana em G em que vk1 v1 Note que para i 1 2 k as arestas vi1vi e vivi1 contribuem com duas unidades para o grau de vi Como toda aresta de G aparece em C podemos concluir que todo vértice de G tem grau múltiplo de dois e portanto par Agora vamos mostrar que se G é par então G é Euleriano Vamos usar indução em E EG Se E 0 então por ser conexo G é dado por V G v e EG A trilha v é fechada e contém todas as arestas de G e portanto o resultado vale Agora assuma que E 1 e considere que todo grafo conexo par com menos do que E arestas é Euleriano Como G é conexo e par temos que δG 2 e como E 1 temos que V G 2 Assim pelo Teorema 24 G contém um ciclo C v1 v2 vk v1 Seja G G EC Note que cada componente conexa de G é par Sejam G 1 G 2 G ℓ as componentes conexas de G Note que para i 1 2 ℓ temos que EG i E Assim pela hipótese de indução temos que para i 1 2 ℓ o grafo G i é Euleriano e por definição possui uma trilha Euleriana Ti Agora vamos mostrar como combinar tais trilhas das componentes de G com o ciclo C para formar uma trilha Euleriana de G e com isso provar que G é Euleriano Como o grafo G é conexo temos que V CV G i para i 1 2 ℓ Para cada i 1 2 ℓ seja vri o vértice mais à esquerda na sequência de C tal que vri V C V G i Considere a sequência de vértices visitados pela trilha Ti como tendo início e portanto fim em vri Defina C1 v1 vr11 Cℓ1 vrℓ1 v1 e para 2 i ℓ Ci vri11 vri1 Note que C C1 C2 Cℓ Cℓ1 Assim a trilha T C1 T1 C2 T2 Cℓ Tℓ Cℓ1 é uma trilha Euleriana em G 92 Outra demonstragao para Se G é par entao G é Euleriano Demonstragao Seja G conexo e par Considere uma trilha maxima T em G Pri meiramente vamos provar que T é fechada Suponha por contradicgao que T comega em um vértice u e termina em um vértice v 4 u Entao existe uma quantidade impar de arestas de T que incidem em v Porém dv é par entaéo existe pelo menos uma aresta uw ET Mas entao T vw é uma trilha maior do que JT um absurdo Resta mostrar que T v1 v2 Ug U1 6 Euleriana Suponha por contradicao que T nao é Euleriana Entao existe uma aresta e EG que nao esta em T Como G é conexo existe um caminho de um dos extremos de e até algum v Entao existe e vw que nao esta em T Mas a trilha w Uj Viti Uk U1 V2 Vi1 Vi é maior do que 7 um absurdo O e Uma decomposicgao de um grafo G é uma colegéo G1 GoG de subgrafos de G tal que para qualquer 1 i j k temos que EG N EG 0 e k Unni Gi EG e Note que portanto um vértice v VG pode aparecer em mais de um G e Dizemos que uma decomposigao D de um grafo G é uma decomposicgao em ciclos se todo elemento de D é um ciclo Teorema 132 Um grafo par se e somente se ele pode ser decomposto em ciclos Corolario 133 Um grafo par nao possut arestas de corte e O teorema a seguir caracteriza grafos que contém uma trilha euleriana aberta Teorema 134 Um grafo conezo G contém uma trilha euleriana aberta se e somente se G tem exatamente dois vértices de grau tmpar e Um algoritmo bastante simples porém nao tao eficiente que fornece uma trilha Euleriana é o algoritmo de Fleury 1883 Cada aresta escolhida pelo algoritmo para fazer parte da trilha é removida o algoritmo evita escolher arestas de corte por qué a menos que nao haja alternativa 93 Se quisermos uma trilha Euleriana aberta então o vértice inicial v deve ser um dos vértices de grau ímpar 0 1 2 3 4 5 6 1 Função FleuryG 2 seja v V G qualquer 3 W v 4 x v 5 Enquanto dGx 0 faça 6 Escolha xy EG onde xy não é ponte a menos que não haja alternativa 7 Adicione y ao final de W 8 x y 9 G G xy 10 Devolve W Teorema 135 Se G é um grafo conexo par então W devolvida pelo algoritmo de Fleury é uma trilha Euleriana Demonstração Seja W devolvida pelo algoritmo Primeiro note que W é trilha por construção é um caminho e além disso a mesma aresta não aparece duas vezes em W já que é removida do grafo Também note que W é fechada o vértice final de qualquer trilha fechada tem grau par na trilha e o algoritmo para quando atinge um vértice x com grau zero x tinha grau par inicialmente Resta mostrar que W é Euleriana Suponha para fins de contradição que não é Denote por H o grafo G ao fim da execução Como W não é Euleriana EH Além disso como W é trilha fechada H é par Seja X V G o conjunto de vértices com grau positivo em H Note que V GX pois v V GX Por construção em H não existe aresta entre X e V G X mas em G existe pois G é conexo Então W contém arestas com um extremo em X e outro em V GX Considere uv como sendo a última aresta desse tipo u X e v V G X que foi escolhida pelo algoritmo Note que no momento em que ela foi escolhida ela estava sozinha no corte X V G X o que significa que ela era ponte no grafo G Nesse mesmo momento 94 x u pois a trilha acaba em V G X Mas H é par e portanto dHu 2 ou seja havia outras arestas não ponte incidentes a u pelo Corolário 133 violando a regra de escolha do algoritmo Como Fleury funciona ele passa uma única vez por todas as arestas de G porém em cada uma gasta um tempo para decidir se ela é ponte Sendo assim tem tempo total OE2 Um algoritmo mais eficiente de tempo OE é o de Hierholzer 1873 dado a seguir Sua ideia é decompor o grafo em trilhas fechadas menores e juntálas em uma só e ele segue justamente da prova do Teorema 131 Cada vértice da trilha menor é salvo em uma pilha Então remover os vértices da pilha a princípio nos dá uma trilha Acontece que cada vértice removido da pilha pode ser o início de outra trilha 1 Função TrilhaMaximalG v 2 Enquanto dv 0 faça 3 PushP x 4 seja x algum vizinho de v 5 G G vx 6 v x 7 Devolve v 8 Função HierholzerG 9 seja v V G qualquer 10 seja P uma pilha 11 W v 12 Enquanto TrilhaMaximalG v v e P faça 13 v PopP 14 Adicione v ao final de W 15 Devolve W 95 132 Grafos Hamiltonianos Vamos nos concentrar no problema de dado um grafo G ele possui um ciclocaminho Hamiltoniano Lema 136 Seja G um grafo conexo Se G possui vértice de corte então G não possui ciclo Hamiltoniano Lema 137 Seja G um grafo bipartido conexo e X Y uma bipartição de G Se X Y então G não possui ciclo Hamiltoniano O teorema a seguir é um resultado clássico que garante ciclo hamiltoniano para grafos nos quais todos os vértices têm grau alto Teorema 138 Dirac 1952 Seja G um grafo conexo de ordem n 3 Se δG n 2 então G possui ciclo Hamiltoniano Demonstração Suponha para fins de contradição que nem todo grafo com grau mí nimo pelo menos n2 possui ciclo Hamiltoniano Seja G um tal grafo com n vértices e com o maior número de arestas em outras palavras G é um contraexemplo maxi mal Claramente G não é completo Assim existem vértices u e v não adjacentes em G Então pela escolha de G G uv possui ciclo Hamiltoniano Logo G possui caminho Hamiltoniano Seja C v1 vn um caminho Hamiltoniano em G com v1 u e vn v Sejam S vi vi1u EG e T vi viv EG Note que S T pois se vi S T então v1 vi vn vn1 vi1 v1 seria um ciclo Hamiltoniano em G contrariando a escolha de G Note também que vn S T de onde vemos que S T n Então n S T S T S T S T du dv mas du dv δG δG n 2 n 2 n uma contradição A prova do teorema de Dirac pode ser adaptada para provar os seguintes resultados 96 Teorema 139 BondyChvátal 1976 Seja G um grafo conexo de ordem n 3 tal que existem vértices u e v não adjacentes para os quais du dv n O grafo G possui ciclo Hamiltoniano se e somente se G uv possui ciclo Hamiltoniano Teorema 1310 Ore 1960 Seja G um grafo conexo de ordem n 3 Se para todo par u v de vértices não adjacentes vale que du dv n então G possui ciclo Hamiltoniano 97