Teoria dos Grafos

Valeriano A. de OliveiraSocorro Rangel

Departamento de Matemtica Aplicadaantunes@ibilce.unesp.br, socorro@ibilce.unesp.br

Grafos Eulerianos

Preparado a partir do texto:Rangel, Socorro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.

Grafos Eulerianos

Grafos Eulerianos Digrafos Eulerianos

IntroduoGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 3

No incio do curso ns estudamos o problema das Pontes de Konigsberge representamos o problema atravs do seguinte grafo::

A

C

B

D

Queramos saber se possvel fazer um passeio pela cidade, comeando eterminando no mesmo lugar e passando por cada uma das pontes apenasuma vez.

Em outras palavras queramos encontrar no grafo acima um

trajeto fechado que inclusse todas as arestas do grafo.

DefiniesGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 4

Definio 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 no-euleriano dito ser semi-euleriano se possui um

trajeto euleriano.

Observao: Note que em um grafo euleriano cada aresta percorridauma, e uma nica, vez.

ExemplosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 5

A seguir temos exemplos de grafos euleriano, semi-euleriano eno-euleriano:

Resultado auxiliarGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 6

Lema 2. Se G(V,A) um grafo tal que d(v) 2 para todo v V ,ento G contm um ciclo.

Demonstrao. Se G possui laos ou arestas paralelas, no h o queprovar.

Vamos supor que G um grafo simples. Seja v0 V um vrticearbitrrio de G. Como d(v) 2 para todo v V , podemos construir umpasseio v0 v1 v2 indutivamente escolhendo vi+1 como sendoqualquer vrtice adjacente a vi exceto vi1.

Como G possui uma quantidade finita de vrtices, em algum momentoescolheremos algum vrtice, digamos vk, pela segunda vez.

A parte do passeio entre e primeira e a segunda ocorrncia de vkconstitui um ciclo.

Condio necessria e suficienteGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 7

Teorema 3 (Euler, 1736). Um grafo conexo G(V,A) euleriano se, esomente se, o grau de cada vrtice de G par.

Demonstrao. () Seja T um trajeto euleriano fechado de G. Cadavez que um vrtice v ocorre no trajeto T , h uma contribuio de duasunidades para o grau de v (uma aresta para chegar a v e outra parasair).

Isto vale no s para os vrtices intermedirios mas tambm para ovrtice final, pois samos e entramos no mesmo vrtice no incio e nofinal do trajeto.

Como cada aresta ocorre exatamente uma vez em T , cada vrtice possuigrau par.

Cont. da demonstraoGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 8

() A prova por induo no nmero de arestas de G. Suponhamosque o grau de cada vrtice de G par. Como G conexo, d(v) 2 paratodo v V . Segue ento do lema anterior que G contm um ciclo C.

Se C contm todas as arestas de G, o teorema est provado.

Se no, removemos de G as arestas de C, resultando num grafo H,possivelmente desconexo, com menos aretas do que G.

C

H

H

Cont. da demonstraoGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 9

fcil ver que todos os vrtices de H possuem grau par. Logo, pelahiptese de induo, cada componente de H possui um trajeto eulerianofechado.

Alm disso, pela conexidade de G, cada componente de H possui aomenos um vrtice em comum com C.

Portanto, concatenando os trajetos euleriados fechados de cadacomponente de H com o ciclo C obtemos um trajeto euleriano fechadoem G, ou seja, G um grafo euleriano.

ExercciosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 10

Corolrio 4. Um grafo conexo euleriano se, e somente se, puder ser

decomposto em circuitos disjuntos:

G =

i

Ci, Ci Cj = grafo nulo.

Corolrio 5. Um grafo conexo semi-euleriano se, e somente se, possui

exatamente dois vrtices de grau mpar.

Algoritmo de DecomposioGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 11

Considere um grafo conexo G(V,A), onde d(v) par v V .

Passo 1: Determine um circuito C1 em G.

Defina T1 = C1 e G1 = G.

Se T1 possui todas as arestas de G, pare. T1 o trajeto procurado.

Faa k = 1.

Passo 2: Faa k = k + 1. Construa o subgrafo Gk(Vk, Ak) removendo de Gk1 asarestas pertencentes a Tk1(Vk1, Ak1). Remova de Gk os vrtices isolados.

Passo 3: Determine um vrtice v Vk Vk1. A partir de v determine um circuito

Ck em Gk.

Passo 4: Determine Tk = Tk1 Ck.

Se Tk possui todas as arestas de G, v para o Passo 5.

Caso Contrrio, retorne ao Passo 2.

Passo 5: Pare. Tk o trajeto procurado e G =

k

i=1

Ci.

ExercciosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 12

Verifique se os grafos abaixo so eulerianos. Se possvel exiba um trajetoeuleriano.

Algoritmo de FleuryGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 13

Considere um grafo conexo G(V,A), onde d(v) par v V .

Comece em qualquer vrtice v e percorra as arestas de forma aleatria,seguindo sempre as seguintes regras:

1. Exclua as arestas depois de passar por elas;

2. Exclua os vrtices isolados, caso ocorram;

3. Passe por uma ponte1 somente se no houver outra alternativa.

1Uma aresta dita ser uma ponte se a sua remoo torna o grafo desconexo.

ExemploGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 14

Aplique o Algoritmo de Fleury para encontrar um trajeto euleriano nografo abaixo a partir do vrtice 5.

Digrafos Eulerianos

Grafos Eulerianos Digrafos Eulerianos

DefiniesGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 16

Definio 6. Um trajeto orientado que inclua todas as arestas de um

dado digrafo G(V,A) chamado de trajeto euleriano.

Seja G um digrafo conexo. Dizemos que G euleriano se possui um

trajeto euleriano fechado.

Um digrafo G no-euleriano dito ser semi-euleriano se possui um

trajeto euleriano.

DefiniesGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 16

Definio 7. Um trajeto orientado que inclua todas as arestas de um

dado digrafo G(V,A) chamado de trajeto euleriano.

Seja G um digrafo conexo. Dizemos que G euleriano se possui um

trajeto euleriano fechado.

Um digrafo G no-euleriano dito ser semi-euleriano se possui um

trajeto euleriano.

Observaes:

1. Um digrafo conexo euleriano necessariamente fortemente conexo.

2. Entretanto, nem todo digrafo fortemente conexo euleriano.

ExemplosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 17

Teorema de Euler para digrafosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 18

Teorema 8. Um digrafo conexo D(V,A) euleriano se, e somente se,D balanceado, i.e., de(v) = ds(v) v V .

Demonstrao: Exerccio.

Teorema de Euler para digrafosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 18

Teorema 9. Um digrafo conexo D(V,A) euleriano se, e somente se,D balanceado, i.e., de(v) = ds(v) v V .

Demonstrao: Exerccio.

Corolrios? Exerccios.

Grafos EulerianosIntroduoDefiniesExemplosResultado auxiliarCondio necessria e suficienteCont. da demonstraoCont. da demonstraoExercciosAlgoritmo de DecomposioExercciosAlgoritmo de FleuryExemplo

Digrafos EulerianosDefiniesExemplosTeorema de Euler para digrafos