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)
Ciclos Eulerianos
entrada: 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-se
10. retirar v de  (CV) e CV de  (v)
11. E´ ← E´ U {{CV,v}}
12. CV ← v;
13. adicionar CV no final de EC
CV: vértice que está sendo visitado
14. fim-enquanto
E´: conjunto de arestas já traçadas
saída: EC
EC: lista de vértices ordenada pela
seqüência de visitas
(v):conjunto de vizinhos de v em GE´
CC/EC/Mestrado
Teoria dos Grafos
Exemplo
Exercício:
Executar o algoritmo para o grafo
descrevendo os principais passos
e a idéia do seu funcionamento.
g
b
a
c
e
f
d
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=9
S = {s1, s2, s3}
s21
s1
CC/EC/Mestrado
Teoria dos Grafos
s3
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
d
b
a
c
CC/EC/Mestrado
Teoria dos Grafos
Prova
• Seja G um grafo simples e maximal, com n  3 e   n/2 e não
hamiltoniano. 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 = v1v2v3...vn-1vn= v
• O grafo G pode conter mais arestas do que aquelas
pertencentes ao caminho (pois   n/2)
• Sejam S = {vi | uvi+1  E} e T = {vi | viv  E}
• vn  S e vn  T  vn  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
CC/EC/Mestrado
Teoria dos Grafos
Exercícios
1. Mostre que |E(Kp,q)| = p*q
2. Seja G = (V,E) um grafo com |V| = n e |E| = m. Mostre que
se G é um grafo bipartido então m  n2/4.
3. Sejam a, b e c três vértices distintos em um grafo. Existe
um caminho entre a e b e também existe um caminho
entre b e c. Prove que existe um caminho entre a e c.
CC/EC/Mestrado
Teoria dos Grafos