Grafos eulerianos

Linha de Euler

• Em que tipo de grafo é possível achar um ciclo que passe por cada aresta exatamente uma vez?

• Esse ciclo linha de Euler

• O grafo que consiste nesta linha: grafo euleriano

• Um grafo euleriano é sempre conexo, a menos de vértices isolados.

Teorema

Um grafo conexo G é um grafo euleriano

sss

todos os vértices de G são de grau par

Teorema

Um grafo conexo G é um grafo euleriano

sss

ele pode ser decomposto em ciclos

Pontes

Seja (G) o número de componentes conexas de G.

Uma ponte é uma aresta a

tal que

(G - a) > (G)

CC/EC/Mestrado Teoria dos Grafos

Ciclos Eulerianosentrada: grafo euleriano G = (V,E) 1. EC ← [w]; 2. CV ← w; 3. E´ ← ; 4. enquanto |(w)| > 0 faça 5. se | (CV)| > 1 então 6. encontrar v (CV), {CV,v} não é ponte de G-E´ 7. senão 8. v = o vértice em (CV) 9. fim-se10. retirar v de (CV) e CV de (v) 11. E´ ← E´ U {{CV,v}}12. CV ← v;13. adicionar CV no final de EC14. fim-enquantosaída: EC

CV: vértice que está sendo visitadoE´: conjunto de arestas já traçadasEC: lista de vértices ordenada pela seqüência de visitas(v):conjunto de vizinhos de v em G-E´

CC/EC/Mestrado Teoria dos Grafos

Exemplo

a

b

c

d

e

g

f

a

bg

c

d

fee

Exercício:Executar o algoritmo para o grafo descrevendo os principais passose a idéia do seu funcionamento.

CC/EC/Mestrado Teoria dos Grafos

Grafos Hamiltonianos

CC/EC/Mestrado Teoria dos Grafos

Ciclo Hamiltoniano

• Um caminho que contém todos os vértices de G é dito um caminho hamiltoniano

CC/EC/Mestrado Teoria dos Grafos

Caminho e Ciclo Hamiltoniano

• Um caminho que contém todos os vértices de G é dito um caminho hamiltoniano

• Um ciclo hamiltoniano é um ciclo que contém todos os vértices de G

• Nem todo grafo conexo possui um ciclo hamiltoniano

CC/EC/Mestrado Teoria dos Grafos

Questão

Existe uma condição necessária e suficiente para um grafo conexo possuir

um ciclo hamiltoniano?

CC/EC/Mestrado Teoria dos Grafos

Teorema

Se G é hamiltoniano então,

para todo subconjunto não-vazio e próprio

S de V,

(G-S) |S|

CC/EC/Mestrado Teoria dos Grafos

Exemplo

n = 9S = {s

1, s

2, s

3}

s1

s1

s1

s1

s1

s2

s3

CC/EC/Mestrado Teoria dos Grafos

Grafo de Petersen

CC/EC/Mestrado Teoria dos Grafos

Teorema

Se G é um grafo simples

com n 3 e n/2,

então G é hamiltoniano

a

d

c

b

CC/EC/Mestrado Teoria dos Grafos

Prova

• Seja G um grafo simples, com n 3 e n/2 e não hamiltoniano. Sup. G é maximal com respeito a essa propriedade, ou seja, não existe nenhum outro grafo com mais arestas do que ele que não seja hamiltoniano

• Sejam u e v vértices não adjacentes em G

• Como G é maximal, G + {u,v} é hamiltoniano

• A aresta {u,v} pode ser adicionada a G pois sabemos que G não é completo, pois por suposição, n 3 e G é não hamiltoniano (todo grafo completo possui um ciclo hamiltoniano)

• Como G é não hamiltoniano, todo ciclo hamiltoniano de G+{u,v} contém a aresta {u,v}

CC/EC/Mestrado Teoria dos Grafos

Prova• Logo existe o caminho hamiltoniano em G descrito por

u = v1v

2v

3...v

n-1v

n= v

• O grafo G pode conter mais arestas do que aquelas pertencentes ao caminho (pois n/2)

• Sejam S = {vi | uv

i+1 E} e T = {v

i | v

iv E}

• vn S e v

n T v

n S T |S T| < n (I)

• Além disso, |S T| = 0 (senão haveria um ciclo hamiltoniano em G) (II)

• De (I) e (II): d(u) + d(v) = |S|+|T| = |S T| + |S T| < n+0 = n

• Daí, existe algum vértice em G cujo grau é menor que n/2 (contradição)

• Logo G é hamiltoniano

CC/EC/Mestrado Teoria dos Grafos

Teorema

Número de ciclos hamiltonianos com arestas disjuntas em um grafo: em aberto!

Em um grafo completo esse número

pode ser determinado

Em um grafo completo com n vértices, existem (n-1)/2 ciclos hamiltonianos com arestas

disjuntas, se n é ímpar e n 3.

CC/EC/Mestrado Teoria dos Grafos

Exercício

• Exiba um grafo euleriano e hamiltoniano

• Exiba um grafo euleriano e não hamiltoniano

• Exiba um grafo não euleriano e hamiltoniano

• Exiba um grafo não euleriano e não hamiltoniano