Aula10_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 10
Árvores Geradoras
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Árvores Geradoras
Árvores Geradoras
De�nição e Exemplos
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
De�nição 1. Uma árvore T é 
hamada de árvore geradora de um
grafo G se T é um subgrafo de G que possui todos os vérti
es de G.
Exemplos:
Como obter uma árvore geradora
de G?
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Pro
edimento 1
1. Se G não possui 
ir
uitos, G é sua própria árvore geradora.
2. Se G possui 
ir
uitos, retire uma aresta do 
ir
uito. O subgrafo
resultante é 
onexo.
3. Se existirem mais 
ir
uitos, repita a operação até retirar uma aresta
do último 
ir
uito do grafo.
4. O subgrafo resultante é 
onexo, sem 
ir
uitos e possui todos os
vérti
es de G. Portanto é uma árvore geradora de G.
Teorema 2. Todo grafo 
onexo 
ontém pelo menos uma árvore
geradora.
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
De�nição 3. Seja G(V,A) um grafo 
onexo e T(V,E) uma árvore
geradora de G. Uma aresta de G que não perten
e à árvore geradora T é
hamada de elo de G em relação a T. As arestas que 
ompõem uma
árvore geradora são 
hamadas de ramo.
Exemplo : Os elos de G relativos a T1 no exemplo 1 são: (
,f).
(a,
),(d,e),(a,e).
Observação: Observe que uma aresta que perten
e a T1 pode ser um
elo de G em relação a uma outra árvore geradora de G. No entanto, o
número de elos de um grafo é �xo!
Quantos são?
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Teorema 4. Um grafo 
onexo 
om n vérti
es e m arestas possui
(m− n+ 1) elos.
De�nição 5. Se adi
ionarmos um elo de G a árvore T1, um úni
o
ir
uito será formado. Este 
ir
uito é 
hamado de 
ir
uito fundamental
de G.
Quantos 
ir
uitos fundamentais um grafo possui?
Como obter todas as árvores
geradoras de G?
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Pro
edimento 2
1. Utilize o Pro
edimento 1 para obter uma árvore geradora ini
ial.
2. Determine os elos de G relativos a esta árvore. A
res
entando um
elo de G a T1 um 
ir
uito é formado.
3. Retire, uma a uma, as arestas do 
ir
uito fundamental formado.
Desta forma são geradas as árvores geradoras asso
iadas às arestas
deste 
ir
uito, ou seja, tem-se (k − 1) árvores geradoras, onde k é o
número de arestas no 
ir
uito fundamental. Esta operação é
hamada de transformação elementar (tro
a 
í
li
a, 
y
li
ex
hange).
4. Repita a transformação elementar 
onsiderando os outros elos do
grafo.
Como obter todas as árvores
geradoras de G?
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Perguntas: a análise do Pro
edimento 2 esboçado a
ima, permite a
formulação de uma série de perguntas.
1. Partindo de qualquer árvore e fazendo um 
erto número de
transformações elementares é possível obter uma determinada árvore
geradora?
2. Usando transformações elementares é possível obter todas as árvores
geradoras? Quantas transformações elementares serão ne
essárias?
3. A e�
iên
ia do algoritmo depende da árvore geradora ini
ial?
Para responder algumas dessas perguntas pre
isamos de�nir alguns
novos 
on
eitos.
De�nições
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
De�nição 6. Dados dois 
onjuntos, S1 e S2, a soma direta de S1 e S2
(representada por S1⊕ S2) é dada por: S1 ⊕ S2 = (S1 ∪ S2)− (S1 ∩ S2).
Exemplo:S1 = {v1, v2, v3}, S2 = {v1, v4, v5, v6} então
S1 ⊕ S2 = {v2, v3, v4, v5, v6}.
De�nição 7. A Distân
ia entre duas árvores geradoras de G, Ti e Tj , é
igual ao número de arestas que estão presentes em Ti e que não
perten
em a Tj. Denotamos por d(Ti, Tj). Podemos de�nir a distân
ia
entre duas árvores geradoras de G 
omo sendo o número de
transformações elementares ne
essárias para obter Tj a partir de Ti. Isto
é: d(Ti, Tj) =
1
2
|ATi⊕Tj |. onde ATi⊕Tj é o 
onjunto de arestas obtido
pela a soma direta do 
onjunto de arestas de Ti e Tj .
De�nições
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
De�nição 8. Para uma árvore geradora T0 de G, seja maxi d(T0, Ti) a
distân
ia máxima de T0 a qualquer outra árvore geradora Ti de G. Então
T0 é 
hamada de árvore 
entral de G se:
maxi d(T0, Ti) ≤ maxj d(T, Tj) para qualquer árvore geradora T de G.
De�nição 9. O grafo árvore de G, S(G), é de�nido 
omo o grafo em
que 
ada vérti
e representa uma árvore geradora de G e existe uma
aresta entre dois pares de vérti
es se a distân
ia entre as árvores
geradoras asso
iados for igual a 1.
obs: Estes 
on
eitos são usados em [2℄ para en
ontrar todas as árvores
geradoras de G. A Figura a seguir mostra um grafo G1 e o grafo árvore,
S(G1) asso
iado. Um outro algoritmo para listar todas as árvores
geradoras de G é proposto em [3℄.
De�nições
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Teorema 10. É possível gerar todas as árvores geradoras de G
omeçando de uma árvore geradora qualquer e exe
utando su
essivas
transformações elementares.
Pro
edimento 3 - Determinar
uma árvore geradora
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
O Pro
edimento 1 
onstrói uma árvore geradora de G através da
ex
lusão de arestas que fazem parte de um 
ir
uito em G. O
Pro
edimento 3 a seguir 
onstrói uma árvore geradora de G in
luindo
arestas evitando a formação de 
ir
uitos.
Pro
edimento 3: 
onsidere um grafo simples 
om n vérti
es e m
arestas.
Idéia - Ini
ie a árvore T 
om uma aresta qualquer de G. A 
ada iteração,
in
lua uma nova aresta em T de maneira que nenhum 
ir
uito é formado.
1) O que a
onte
e se o grafo não for 
onexo? Iremos obter várias árvores
geradoras, isto é uma �oresta geradora.
2) Como garantir que ao inserir uma aresta nenhum 
ir
uito é formado?
Veri�
ar se as extremidades da aresta já foram in
luídas. Assim ao
tentarmos a
res
entar a aresta (vk, wk) à árvore, as seguintes situações
podem o
orrer:
Pro
edimento 3 - Determinar
uma árvore geradora
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
1. Nem o vérti
e vk, nem o vérti
e wk perten
em a alguma árvore Ti já
onstruída. Neste 
aso 
rie uma nova árvore a partir destes vérti
es
e desta aresta. Considere que exista mais de uma 
omponente no
grafo, faça cp = cp+ 1. Asso
ie o rótulo cp aos vérti
es vk e wk.
2. O vérti
e vk perten
e à árvore Ti e o vérti
e wk perten
e à árvore
Tj, i 6= j. Neste 
aso, a aresta (vk, wk) é usada para unir as duas
árvores. Faça os vérti
es de Tj re
eberem o mesmo rótulo 
 dos
verti
es de Ti. Faça cp = cp− 1.
3. Os dois vérti
es perten
em a árvore Ti. Neste 
aso a aresta é
des
artada pois sua in
lusão 
riaria um 
ir
uito.
4. Apenas um dos dois vérti
es vk (ou wk) perten
e a alguma árvore Ti
já 
onstruída. Neste 
aso a
res
ente a aresta e o vérti
e wk (ou vk)
à árvore. O vérti
e wk (ou vk) re
ebe o mesmo rótulo c que os
vérti
es já perten
entes a Ti.
Pro
edimento 3 - Determinar
uma árvore geradora
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
Como fazer para implementar as idéias a
ima?
A e�
iên
ia do algoritmo depende da rapidez 
om que veri�
amos se as
extremidades da aresta que estamos 
onsiderando perten
e ou não a
alguma árvore já 
riada.
Para fa
ilitaresta bus
a, 
riamos um vetor n-dimensional VERTEX que
armazena esta informação. Quando uma aresta (i, j) é inserida em
alguma árvore 
om rótulo c, as posições i e j do vetor re
ebem o valor c.
Assim para veri�
ar se a aresta (vk, wk) já foi in
luída em alguma árvore,
veri�
amos se 
orrespondentes posições de VERTEX são diferentes de
zero. Se para algum vérti
e q, VERTEX(q) = 0 o vérti
e q não esta
in
luído em nenhuma árvore. Ao �nal do algoritmo o vetor VERTEX
identi�
a os vérti
es em 
ada 
omponentes do grafo.
Pro
edimento 3 - Determinar
uma árvore geradora
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
Isto é su�
iente?
Pre
isamos ainda identi�
ar as arestas que 
ompõe 
ada árvore do grafo.
Para isto 
riamos o vetor m-dimensional ARESTA. Assim se a k-ésima
aresta foi in
luída na árvore c, faça ARESTA(k) = c, 
aso 
ontrário
ARESTA(k)=0. Ao �nal do algoritmo, as posições do vetor 
om
ARESTA(i)=0 identi�
am os elos de G.
Pro
edimento 3 - Determinar
uma árvore geradora
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Exer
í
io
Considere o grafo G 
om 9 vérti
es e 12 arestas. O grafo será
representado através de dois vetores m-dimensionais F e H, de tal forma
que as extremidades da aresta k é armazenada nas posições fk e hk dos
vetores F e H respe
tivamente. Apli
ar o Pro
edimento 3 e as ideias nele
ontidas, para 
onstruir uma árvore geradora para G.
)� ��
$� (� ,� ,� % % & % ) & )� $�
�
+� ��
%� +� %� &� & ( * ) * (� '� &
�
Árvore Geradora Mínima
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Considere uma rede e o problema de en
ontrar a árvore geradora mínima
asso
iada.
Valor de árvore - é a soma dos pesos asso
iados às arestas 
ontidas na
árvore.
Algoritmo de Kruskal - Determinar uma árvore geradora
mínima em um grafo qualquer
Passo 1- ordene as arestas do grafo em ordem não-de
res
ente de peso.
Passo 2 - aplique o Pro
edimento 3 para en
ontrar a arvore geradora,
onsiderando que as arestas serão sele
ionadas de a
ordo 
om a ordem
estabele
ida no passo 1.
Exemplo:
Árvore Geradora Mínima
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
Teorema 11. A árvore geradora T obtida pelo Algoritmo de Kruskal é
uma árvore geradora mínima de G.
Prova - Sejam e1, e2, ..., en−1 as arestas de T na ordem em que foram
onsideradas no Algoritmo de Kruskal. Isto é
p(e1) ≤ p(e2) ≤ ... ≤ p(en−1).
Vamos supor que T não é uma árvore geradora (AG) mínima de G.
Dentre as AG de valor mínimo, seja Tmin a árvore geradora que 
ontém
as arestas e1, e2, ..., ej de T, tal que j seja o maior índi
e possível
(j < (n− 1), pois em 
aso 
ontrário, ej estaria em T).
Considere que a aresta ej+1 é adi
ionada a Tmin. Um 
ir
uito é então
riado. Este 
ir
uito 
ontém uma aresta x que não perten
e a T (Se
todas as arestas do 
ir
uito estivessem em T, T não seria uma árvore,
pois também teria um 
ir
uito).
Árvore Geradora Mínima
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Pela ordem em que as arestas foram 
onsideradas na 
onstrução de T,
temos que ej+1 foi adi
ionada a T, mas x não foi in
luída. Portanto
p(ej+1) <= p(x) (
aso 
ontrário x teria sido in
luída em T sem a
formação de um 
ir
uito).
Vamos então 
onstruir uma nova árvore:
Tnova = Tmin − x+ ej+1.
Se p(ej+1) < p(x) então p(Tnova) < p(Tmin) o que 
ontraria a hipótese
que Tmin é mínima.
Se p(ej+1) = p(x) então p(Tnova) = p(Tmin) e Tnova é mínima e 
ontém
as arestas e1, e2, ..., ej , ej+1, o que 
ontradiz que j é o menor índi
e
possível usado na 
onstrução de Tmin.
Portanto, temos uma 
ontradição quando dizemos que p(ej+1) <= p(x)
e neste 
aso a suposição que T não é mínima é falsa. Assim mostramos
que T é mínima.
Árvore Geradora Mínima
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
Algoritmo 3 (PRIM) - Grafos Conexos
Passo 1 - Sele
ione um vérti
e vk de G e in
lua em T
Passo 2 - Repita este passo até que todos os vérti
es de G pertençam a
T.
Sele
ione a aresta de menor peso (vj, wj) tal que vj pertença a T e wj
não pertença a T.
Exemplo:
Exer
í
io
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
1. Utilize os algoritmos de Kruskal e de Prim para identi�
ar uma
árvore geradora mínima em 
ada um dos grafos ilustrados na �gura
1 e 2 . Qual é o melhor?
Exer
í
io
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
1. Veri�
ar que uma submatriz (n− 1) x (n− 1) da matriz de
in
idên
ia é não singular se e somente se as arestas asso
iadas às
(n− 1) 
olunas desta submatriz 
onstituem uma árvore geradora de
G.
obs: Posto de um grafo - o posto de uma grafo 
om n vérti
es é
igual a n− 1.
Referên
ias
Árvores Geradoras
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
1 - Mi
hel Gagnon - Notas de aula do 
urso: CI065 Algoritmos e
teoria dos grafos UFPR, 2002.
2 - Shioura, A., A. Tamura e T. Uno, An optimal algorithm for
s
anning all spanning trees of undire
ted graphs. SIAM Journal on
Computing, 26(3), 678-692, 1997.
3 - , Minty, G., A Simple Algorithm for Listing All the Trees of a
Graph. Cir
uits and Systems, IEEE Transa
tions on Cir
uit Theory,
Volume 12, Issue 1, Page(s): 120 - 120, Mar 1965.
	Árvores Geradoras
	Definição e Exemplos
	Como obter uma árvore geradora de G?
	
	
	Como obter todas as árvores geradoras de G?
	Como obter todas as árvores geradoras de G?
	Definições
	Definições
	Definições
	Procedimento 3 - Determinar uma árvore geradora
	Procedimento 3 - Determinar uma árvore geradora
	Procedimento 3 - Determinar uma árvore geradora
	Procedimento 3 - Determinar uma árvore geradora
	Procedimento 3 - Determinar uma árvore geradora
	Árvore Geradora Mínima
	Árvore Geradora Mínima
	Árvore Geradora Mínima
	Árvore Geradora Mínima
	Exercício
	Exercício
	Referências