Aula06_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 6
Grafos Eulerianos
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Grafos Eulerianos
Introdução
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
No iní
io do 
urso nós estudamos o problema das Pontes de Konigsberg
e representamos o problema através do seguinte grafo::
A
C
B
D
Queríamos saber se é possível fazer um passeio pela 
idade, 
omeçando e
terminando no mesmo lugar e passando por 
ada uma das pontes apenas
uma vez.
Em outras palavras queríamos en
ontrar no grafo a
ima um
trajeto fe
hado que in
luísse todas as arestas do grafo.
De�nições
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
De�nição 1. Um trajeto que in
lua todas as arestas de um dado grafo
G(V,A) é 
hamado de trajeto euleriano.
Seja G um grafo 
onexo. Dizemos que G é euleriano se possui um
trajeto euleriano fe
hado.
Um grafo G não-euleriano é dito ser semi-euleriano se possui um
trajeto euleriano.
Observação: Note que em um grafo euleriano 
ada aresta é per
orrida
uma, e uma úni
a, vez.
Exemplos
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
A seguir temos exemplos de grafos euleriano, semi-euleriano e
não-euleriano:
Resultado auxiliar
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Lema 2. Se G(V,A) é um grafo tal que d(v) ≥ 2 para todo v ∈ V ,
então G 
ontém um 
i
lo.
Demonstração. Se G possui laços ou arestas paralelas, não há o que
provar.
Vamos supor que G é um grafo simples. Seja v0 ∈ V um vérti
e
arbitrário de G. Como d(v) ≥ 2 para todo v ∈ V , podemos 
onstruir um
passeio v0 → v1 → v2 · · · indutivamente es
olhendo vi+1 
omo sendo
qualquer vérti
e adja
ente a vi ex
eto vi−1.
Como G possui uma quantidade �nita de vérti
es, em algum momento
es
olheremos algum vérti
e, digamos vk, pela segunda vez.
A parte do passeio entre e primeira e a segunda o
orrên
ia de vk
onstitui um 
i
lo.
Condição ne
essária e su�
iente
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Teorema 3 (Euler, 1736). Um grafo 
onexo G(V,A) é euleriano se, e
somente se, o grau de 
ada vérti
e de G é par.
Demonstração. (⇒) Seja T um trajeto euleriano fe
hado de G. Cada
vez que um vérti
e v o
orre no trajeto T , há uma 
ontribuição de duas
unidades para o grau de v (uma aresta para 
hegar a v e outra para
sair).
Isto vale não só para os vérti
es intermediários mas também para o
vérti
e �nal, pois �saímos� e �entramos� no mesmo vérti
e no iní
io e no
�nal do trajeto.
Como 
ada aresta o
orre exatamente uma vez em T , 
ada vérti
e possui
grau par.
Cont. da demonstração
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
(⇐) A prova é por indução no número de arestas de G. Suponhamos
que o grau de 
ada vérti
e de G é par. Como G é 
onexo, d(v) ≥ 2 para
todo v ∈ V . Segue então do lema anterior que G 
ontém um 
i
lo C.
Se C 
ontém todas as arestas de G, o teorema está provado.
Se não, removemos de G as arestas de C, resultando num grafo H,
possivelmente des
onexo, 
om menos aretas do que G.
C
H
H
Cont. da demonstração
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
É fá
il ver que todos os vérti
es de H possuem grau par. Logo, pela
hipótese de indução, 
ada 
omponente de H possui um trajeto euleriano
fe
hado.
Além disso, pela 
onexidade de G, 
ada 
omponente de H possui ao
menos um vérti
e em 
omum 
om C.
Portanto, 
on
atenando os trajetos euleriados fe
hados de 
ada
omponente de H 
om o 
i
lo C obtemos um trajeto euleriano fe
hado
em G, ou seja, G é um grafo euleriano. �
Exer
í
ios
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Corolário 4. Um grafo 
onexo é euleriano se, e somente se, puder ser
de
omposto em 
ir
uitos disjuntos:
G =
⋃
i
Ci, Ci ∩ Cj = grafo nulo.
Corolário 5. Um grafo 
onexo é semi-euleriano se, e somente se, possui
exatamente dois vérti
es de grau ímpar.
Exer
í
ios
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Veri�que se os grafos abaixo são eulerianos. Se possível exiba um trajeto
euleriano.
Algoritmo de Fleury
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Considere um grafo 
onexo G(V,A), onde d(v) é par ∀v ∈ V .
Come
e em qualquer vérti
e v e per
orra as arestas de forma aleatória,
seguindo sempre as seguintes regras:
1. Ex
lua as arestas depois de passar por elas;
2. Ex
lua os vérti
es isolados, 
aso o
orram;
3. Passe por uma ponte
1
somente se não houver outra alternativa.
1
Uma aresta é dita ser uma ponte se a sua remoção torna o grafo des
onexo.
Exemplo
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Aplique o Algoritmo de Fleury para en
ontrar um trajeto euleriano no
grafo abaixo a partir do vérti
e 5.
Digrafos Eulerianos
De�nições
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
De�nição 6. Um trajeto orientado que in
lua todas as arestas de um
dado digrafo G(V,A) é 
hamado de trajeto euleriano.
Seja G um digrafo 
onexo. Dizemos que G é euleriano se possui um
trajeto euleriano fe
hado.
Um digrafo G não-euleriano é dito ser semi-euleriano se possui um
trajeto euleriano.
Observações:
1. Um digrafo 
onexo euleriano é ne
essariamente fortemente 
onexo.
2. Entretanto, nem todo digrafo fortemente 
onexo é euleriano.
De�nições
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
De�nição 7. Um trajeto orientado que in
lua todas as arestas de um
dado digrafo G(V,A) é 
hamado de trajeto euleriano.
Seja G um digrafo 
onexo. Dizemos que G é euleriano se possui um
trajeto euleriano fe
hado.
Um digrafo G não-euleriano é dito ser semi-euleriano se possui um
trajeto euleriano.
Observações:
1. Um digrafo 
onexo euleriano é ne
essariamente fortemente 
onexo.
2. Entretanto, nem todo digrafo fortemente 
onexo é euleriano.
Exemplos
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Teorema de Euler para digrafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Teorema 8. Um digrafo 
onexo D(V,A) é euleriano se, e somente se,
D é balan
eado, i.e., de(v) = ds(v) ∀ v ∈ V .
Demonstração: Exer
í
io.
Corolários? Exer
í
ios.
Teorema de Euler para digrafos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Teorema 9. Um digrafo 
onexo D(V,A) é euleriano se, e somente se,
D é balan
eado, i.e., de(v) = ds(v) ∀ v ∈ V .
Demonstração: Exer
í
io.
Corolários? Exer
í
ios.
O Problema Chinês do
Carteiro
Colo
ação do problema
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
O Problema Chinês do Carteiro foi postulado em 1962 pelo matemáti
o
hinês Mei-Ku Kwan:
Considere um grafo valorado (ou rede) G tal que os pesos das
arestas são não-negativos. En
ontre um passeio fe
hado que
per
orra todas as arestas de G 
om peso total mínimo.
Apli
ações:
1. Coleta de lixo;
2. Entregas;
3. Limpeza de ruas;
4. Che
agem de páginas da internet:
Colo
ação do problema
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
O Problema Chinês do Carteiro foi postulado em 1962 pelo matemáti
o
hinês Mei-Ku Kwan:
Considere um grafo valorado (ou rede) G tal que os pesos das
arestas são não-negativos. En
ontre um passeio fe
hado que
per
orra todas as arestas de G 
om peso total mínimo.
Apli
ações:
1. Coleta de lixo;
2. Entregas;
3. Limpeza de ruas;
4. Che
agem de páginas da internet:
Exemplo de Maarten van Steen:
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
Che
king a Web site: Typi
ally, a Web site 
onsists of numerouspages, in turn 
ontaining links to ea
h other. As is so often the 
ase,
most Web sites are notoriously poor at having their links maintained to
the 
orre
t pages. This is often due to the simple reason that so many
people are responsible for maintaining their part of a site. Apart from
links that are broken (i.e., refer to nonexisting pages), it is often
ne
essary to manually 
he
k how pages are linked to ea
h other.
Graph theory 
an help by modeling a Web site as an undire
ted graph
where a page is represented by a vertex and a link by an edge having
weight 1. Note that we are not using a dire
ted graph, as we may need
to 
ross a link in reverse order, for example, when going ba
k to the
original page. If a site is to be manually inspe
ted, then we are seeking a
solution to navigate through a site, but with preferably 
rossing a link at
most on
e. This is now the same as �nding a dire
ted walk 
ontaining
all edges of minimal length.
Algoritmo [Gibbons, 1985℄
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Considere um grafo valorado 
onexo G em que o 
onjunto de vérti
es de
grau ímpar é Vimpar = {v1, . . . , v2k}, onde k ≥ 1.
1. Para 
ada par (vi, vj) ∈ Vimpar × Vimpar 
om vi 6= vj, en
ontre o
aminho mínimo Pi,j entre vi e vj .
2. Construa um grafo 
ompleto 
om os 2k vérti
es de Vimpar em que o
peso da aresta (vi, vj) é o peso do 
aminho mínimo Pi,j.
3. Determine o 
onjunto E = {e1, e2, . . . , ek} de k arestas do grafo
ompleto, duas a duas não-adja
entes, tal que a soma de seus pesos
seja mínima.
4. Para 
ada aresta e = (vi, vj) ∈ E, duplique as arestas de Pi,j em G.
Exemplo (Maarten van Steen)
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
v1
v2
v3
v4
u1
u2
u3
u4
u5
u6
1
1 2
3
3
2
1
4
2
1
3 2
1
5
2
1
2 1
v1 v2
v4v3
3
3
4
5
5
2
1
1
1 2
3
3
2
1
4
2
1
3 2
1 1
5
2
1
2 1
1
2
Exer
í
io: estudar o seguinte
Algoritmo de De
omposição
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
Considere um grafo 
onexo G(V,A), onde d(v) é par ∀v ∈ V .
Passo 1: Determine um 
ir
uito C1 em G.
De�na T1 = C1 e G1 = G.
Se T1 possui todas as arestas de G, pare. T1 é o trajeto pro
urado.
Tome k = 1.
Passo 2: Faça k = k + 1. Construa o subgrafo Gk(V¯k, A¯k)
removendo de Gk−1 as arestas perten
entes a Tk−1(Vk−1, Ak−1).
Remova de Gk os vérti
es isolados.
Passo 3: Determine um vérti
e v ∈ V¯k ∩ Vk−1. A partir de v
determine um 
ir
uito Ck em Gk.
Passo 4: Determine Tk = Tk−1 ∪ Ck.
Se Tk possui todas as arestas de G, vá para o Passo 5.
Caso Contrário, retorne ao Passo 2.
Passo 5: Pare. Tk é o trajeto pro
urado e G =
k⋃
i=1
Ci.