TEMA_3_-_ARA0175_-_CAMINHOS_EM_GRAFOS

Prévia do material em texto

Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TEMA 3 – Caminhos em Grafos
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
DEFINIÇÕES EM CAMINHOS
Caminhos em Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 3
Definição 1. Um passeio em um grafo 𝐺 = (𝑉, 𝐸) é uma sequência 
alternada de vértices e arestas que começa e termina com vértices.
Caminhos em Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 4
Definição 1. Um passeio em um grafo 𝐺 = (𝑉, 𝐸) é uma sequência 
alternada de vértices e arestas que começa e termina com vértices.
• A seqüência 𝑣1, … , 𝑣𝑘, ∀ 𝑣1, … , 𝑣𝑘 ∈ 𝑉, é um passeio de 𝑣1 a 𝑣𝑘 , se 
(𝑣𝑗 , 𝑣𝑗+1) ∈ 𝐸, 1 ≤ 𝑗 ≤ |𝑘 – 1|. 
• Um passeio com 𝑘 vértices possui 𝑘 – 1 arestas. 
• O comprimento de um passeio é o número de arestas do passeio. 
Propriedades:
Caminhos em Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 5
Definição 1. Um passeio em um grafo 𝐺 = (𝑉, 𝐸) é uma sequência 
alternada de vértices e arestas que começa e termina com vértices.
𝑢
𝑣
Os vértices (na sequência) 
𝑢, 1, 2, 5, 𝑣 formam um 
passeio.
1
2
3
4
5
Caminhos em Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 6
Definição 2. Um caminho ou caminho simples em um grafo é um 
passeio em que todos os seus vértices são distintos.
𝑢
𝑣1
2
3
4
5
O passeio (na sequência) 
𝑢, 1, 2, 5, 2, 3, 5, 𝑣 não 
constitui caminho.
Caminhos em Grafos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 7
Uma trilha ou trajeto em um grafo é um passeio em que todas as 
suas arestas são distintas.
1
2
3
5
4 A sequência 
1, 2, 3,5, 4, 3 constitui uma 
trilha.
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
GRAFOS EULERIANOS E 
HAMILTONIANOS
Desafio 1
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 9
É possível desenhar a figura ao lado, sem 
tirar o lápis do papel e sem repetir os 
caminhos?
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 10
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 11
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 12
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 13
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 14
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5,7
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 15
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 16
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 17
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 18
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4, 6
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 19
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4, 6, 2
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 20
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4, 6, 2,4
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 21
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4, 6, 2, 4, 3
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 22
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4, 6, 2, 4, 3
2
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 23
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Exemplo:
1
2
3
4
5
6
7
1, 3, 5, 7, 6, 5, 4, 6, 2, 4, 3
2,1
Grafos Eulerianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 24
Definição 3. Um grafo conectado 𝐺 é dito Euleriano se existe uma 
trilha fechada contendo cada uma das arestas de 𝐺.
Propriedades:
• Teorema: Um grafo conectado 𝐺 é Euleriano se e somente se o grau de cada vértice 
é par.
• Seja 𝐺 = (𝑉, 𝐸) euleriano e seja um ciclo euleriano em 𝐺. Ao percorremos esse 
ciclo a partir de um vértice dado, cada vez que atravessarmos um vértice 
utilizaremos duas arestas, uma na chegada e outra na saída. Logo, o grau de cada 
vértice deve ser obrigatoriamente par (Prova por indução direta).
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 25
Definição 4. Um caminho hamiltoniano é um caminho que passa por 
cada vértice de um grafo exatamente uma vez
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 26
Definição 4. Um caminho hamiltoniano é um caminho que passa por 
cada vértice de um grafo exatamente uma vez
Exemplo:
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 27
Definição 5. Um ciclo hamiltoniano é um caminho hamiltoniano que 
retorna ao vértice inicial.
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 28
Definição 5. Um ciclo hamiltoniano é um caminho hamiltoniano que 
retorna ao vértice inicial.
Exemplo:
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 29
Definição 5. Um ciclo hamiltoniano é um caminho hamiltoniano que 
retorna ao vértice inicial.
Um grafo é dito hamiltoniano se 
possui um ciclo hamiltoniano. 
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 30
Exemplo de Grafo hamiltoniano (a) e grafo não 
hamiltoniano (b).
(a) (b) 
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 31
Outros exemplos:
Grafos Ciclo, 𝑲𝒏, Platônicos (Cubo, Tetraedro, Octaedro, 
Dodecaedro, Icosaedro )
𝑲𝟒𝑪𝟒 Tetraedro
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 32
Propriedades:
Condição de Dirac (1952): Seja 𝐺 um grafo simples com 𝑛 ≥ 3 vértices. Se 
𝑔𝑟𝑎𝑢(𝑣) ≥ 𝑛/2, ∀𝑣 ∈ 𝑉(𝐺) então 𝐺 é Hamiltoniano.
𝑲𝟒 𝑲𝟓
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 33
Propriedades:
Condição de Dirac (1952): Seja 𝐺 um grafo simples com 𝑛 ≥ 3 vértices. Se 
𝑔𝑟𝑎𝑢(𝑣) ≥ 𝑛/2, ∀𝑣 ∈ 𝑉(𝐺) então 𝐺 é Hamiltoniano.
Condição de Ore (1960): Seja 𝐺 um grafo simples, se 𝑔𝑟𝑎𝑢 𝑢 + 𝑔𝑟𝑎𝑢(𝑣) ≥
𝑛 paratodo 𝑢, 𝑣 não adjacente, então 𝐺 é Hamiltoniano.
Propriedade do Ciclo: Todo grafo Hamiltoniano com 𝑛 -vértices é 
constituído por um 𝐶𝑛 e mais algumas arestas.
Grafos Hamiltonianos - Definições
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 34
Propriedades:
Condição de Dirac (1952): Seja 𝐺 um grafo simples com 𝑛 ≥ 3 vértices. Se 
𝑔𝑟𝑎𝑢(𝑣) ≥ 𝑛/2, ∀𝑣 ∈ 𝑉(𝐺) então 𝐺 é Hamiltoniano.
Condição de Ore (1960): Seja 𝐺 um grafo simples, se 𝑔𝑟𝑎𝑢 𝑢 + 𝑔𝑟𝑎𝑢(𝑣) ≥
𝑛 para todo 𝑢, 𝑣 não adjacente, então 𝐺 é Hamiltoniano.
Propriedade do Ciclo: Todo grafo Hamiltoniano com 𝑛 -vértices é 
constituído por um 𝐶𝑛 e mais algumas arestas.
Grafos Eulerianos e Hamiltonianos - História
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 35
• A teoria dos grafos nasceu associada à solução e modelagem de um 
problema de ciclos. 
• Diz-se que Euler, por ocasião de uma visita à cidade de Königsberg, durante o 
século XVIII, foi apresentado a um desafio não resolvido por ninguém. 
Durante a solução do problema, Euler teria lançado os fundamentos da 
teoria dos grafos. 
Grafos Eulerianos e Hamiltonianos - História
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 36
O problema tratava-se do rio Pregolya que atravessava a cidade de Königsberg 
(atual Kaliningrado), formando duas ilhas. As ilhas e as margens eram ligadas 
por sete pontes.
É possível fazer uma caminhada que 
atravesse todas as pontes da cidade uma 
única vez e retorna ao ponto inicial?
Grafos Eulerianos e Hamiltonianos - História
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 37
O problema tratava-se do rio Pregolya que atravessava a cidade de Königsberg 
(atual Kaliningrado), formando duas ilhas. As ilhas e as margens eram ligadas 
por sete pontes.
Grafos Eulerianos e Hamiltonianos - História
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 38
O problema tratava-se do rio Pregolya que atravessava a cidade de Königsberg 
(atual Kaliningrado), formando duas ilhas. As ilhas e as margens eram ligadas 
por sete pontes.
Estudando este problema, Euler 
demonstrou, com o auxílio do grafo da 
figura anterior, que o percurso 
pretendido é impossível. Assim nascia 
o problema dos grafos Eulerianos. 
Grafos Eulerianos e Hamiltonianos - História
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 39
No Brasil, temos uma situação semelhante, no Centro de Recife.
Grafos Eulerianos e Hamiltonianos - História
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 40
Curiosidade:
• Existe caracterização formal de grafos eulerianos.
• Não existe uma caracterização formal para identificar grafos 
hamiltonianos.
• Buscar caracterização de grafos hamiltonianos ainda é um 
problema não solucionado em teoria dos grafos.
Exercícios
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 41
1) Os grafos abaixo são hamiltonianos e eulerianos?
Exercícios
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 42
2) Os grafos abaixo são hamiltonianos e eulerianos?
3) Por que grafos eulerianos não podem ter ponte?
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
ALGORITMOS EULERIANOS E 
HAMILTONIANOS
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 44
Algoritmo de Fleury
O Algoritmo de Fleury é utilizado para a construção ou identificação de um 
ciclo euleriano em um grafo euleriano. Foi proposto em 1883.
Características
• O grafo de entrada é sempre Euleriano.
• Utiliza um grafo induzido pelas arestas ainda não marcadas pelo algoritmo. 
Inicialmente todas as arestas estão não marcadas, e a partir de um vértice 
aleatório, uma aresta que obedeça a regra da ponte é escolhida para ser 
percorrida e inserida no ciclo. 
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 45
Regra da Ponte
Se uma aresta {𝑣, 𝑤} é uma ponte no grafo reduzido, então {𝑣, 𝑤} só deve ser 
escolhida pelo algoritmo de Fleury caso não haja outra opção.
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 46
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1.C ← {v}; 
2.repita 
1.Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2.Atravessar {v, w}; 
3.C ← C ∪ {w}; 
4.Marcar {v, w}; 
5.v ← w; 
3.até que todas as arestas estejam marcadas; 
4.C ← C ∪ {v};
Algoritmo de Fleury
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 47
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Algoritmo de Fleury
Vamos rastrear o algoritmo...
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 48
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Algoritmo de Fleury
a
d
b
e
c
f
g
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 49
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Algoritmo de Fleury
a b
e
c
f
g
d
Escolhido o 
vértice 𝑑.
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 50
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Algoritmo de Fleury
a b
e
c
f
g
d
{d, g} 
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 51
Algoritmo de Fleury
a b
e
c
fd
{d, g} 
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Na 3ª iteração, o grafo é reduzido. O 
vértice 𝑤 passa a pertencer ao ciclo 𝐶.
g
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 52
Algoritmo de Fleury
a b
e
c
fd
{d, g} 
g
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 53
Algoritmo de Fleury
a b
e fd
{d, g} 
g
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
c
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 54
Algoritmo de Fleury
a b
e fd
{g, c} 
g
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
c
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 55
Algoritmo de Fleury
a b
e fd
{g, c} 
g
ca b
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquervértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Observe que nesse momento, temos uma ponte, 
somente escolher a ponte se não houver outra 
aresta incidente a vértice 𝑤.
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 56
Algoritmo de Fleury
a b
e fd
{c, f} g
ca b
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 57
Algoritmo de Fleury
a b
e fd
{f, g} 
g
ca b
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 58
Algoritmo de Fleury
a b
e fd
{g, c} 
g
ca b
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 59
Algoritmo de Fleury
g
a b
e fd
ca
{c,b} 
Agora a aresta ponte é 
escolhida, pois não há mais 
outra saída.
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 60
Algoritmo de Fleury
g
b
fd
c
e
a
Entrada: Grafo Euleriano G = (V, A) 
Escolha qualquer vértice v ∈ V; 
1. C ← {v}; 
2. repita 
1. Escolha uma aresta {v, w} não marcada usando a regra da ponte;
2. Atravessar {v, w}; 
3. C ← C ∪ {w}; 
4. Marcar {v, w}; 
5. v ← w; 
3. até que todas as arestas estejam marcadas; 
4. C ← C ∪ {v};
Grafos Eulerianos – Algoritmo de Fleury
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 61
Complexidade de Execução1
• 𝑂(𝑚) remoções de arestas;
• 𝑂(𝑚) para detecção de pontes, para cada vértices, visitar as arestas e 
verificar se são pontes (algoritmo ingênuo);
• Complexidade Final 𝑶(𝒎𝟐 ). 
• Algoritmo de natureza Polinomial.
1 Revisar Complexidade de Tempo de Algoritmos e Notação 
Assintótica. Material extra disponível na Sala de Aula virtual.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 62
Dúvidas?
	Slide 1: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 2: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 3: Caminhos em Grafos - Definições
	Slide 4: Caminhos em Grafos - Definições
	Slide 5: Caminhos em Grafos - Definições
	Slide 6: Caminhos em Grafos - Definições
	Slide 7: Caminhos em Grafos - Definições
	Slide 8: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 9: Desafio 1
	Slide 10: Grafos Eulerianos - Definições
	Slide 11: Grafos Eulerianos - Definições
	Slide 12: Grafos Eulerianos - Definições
	Slide 13: Grafos Eulerianos - Definições
	Slide 14: Grafos Eulerianos - Definições
	Slide 15: Grafos Eulerianos - Definições
	Slide 16: Grafos Eulerianos - Definições
	Slide 17: Grafos Eulerianos - Definições
	Slide 18: Grafos Eulerianos - Definições
	Slide 19: Grafos Eulerianos - Definições
	Slide 20: Grafos Eulerianos - Definições
	Slide 21: Grafos Eulerianos - Definições
	Slide 22: Grafos Eulerianos - Definições
	Slide 23: Grafos Eulerianos - Definições
	Slide 24: Grafos Eulerianos - Definições
	Slide 25: Grafos Hamiltonianos - Definições
	Slide 26: Grafos Hamiltonianos - Definições
	Slide 27: Grafos Hamiltonianos - Definições
	Slide 28: Grafos Hamiltonianos - Definições
	Slide 29: Grafos Hamiltonianos - Definições
	Slide 30: Grafos Hamiltonianos - Definições
	Slide 31: Grafos Hamiltonianos - Definições
	Slide 32: Grafos Hamiltonianos - Definições
	Slide 33: Grafos Hamiltonianos - Definições
	Slide 34: Grafos Hamiltonianos - Definições
	Slide 35: Grafos Eulerianos e Hamiltonianos - História
	Slide 36: Grafos Eulerianos e Hamiltonianos - História
	Slide 37: Grafos Eulerianos e Hamiltonianos - História
	Slide 38: Grafos Eulerianos e Hamiltonianos - História
	Slide 39: Grafos Eulerianos e Hamiltonianos - História
	Slide 40: Grafos Eulerianos e Hamiltonianos - História
	Slide 41: Exercícios
	Slide 42: Exercícios
	Slide 43: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 44: Grafos Eulerianos – Algoritmo de Fleury
	Slide 45: Grafos Eulerianos – Algoritmo de Fleury
	Slide 46: Grafos Eulerianos – Algoritmo de Fleury
	Slide 47: Grafos Eulerianos – Algoritmo de Fleury
	Slide 48: Grafos Eulerianos – Algoritmo de Fleury
	Slide 49: Grafos Eulerianos – Algoritmo de Fleury
	Slide 50: Grafos Eulerianos – Algoritmo de Fleury
	Slide 51: Grafos Eulerianos – Algoritmo de Fleury
	Slide 52: Grafos Eulerianos – Algoritmo de Fleury
	Slide 53: Grafos Eulerianos – Algoritmo de Fleury
	Slide 54: Grafos Eulerianos – Algoritmo de Fleury
	Slide 55: Grafos Eulerianos – Algoritmo de Fleury
	Slide 56: Grafos Eulerianos – Algoritmo de Fleury
	Slide 57: Grafos Eulerianos – Algoritmo de Fleury
	Slide 58: Grafos Eulerianos – Algoritmo de Fleury
	Slide 59: Grafos Eulerianos – Algoritmo de Fleury
	Slide 60: Grafos Eulerianos – Algoritmo de Fleury
	Slide 61: Grafos Eulerianos – Algoritmo de Fleury
	Slide 62