Árvores Geradoras
Subgrafo gerador
O subgrafo gerador (ou de espalhamento) de um
grafo G1(V1,E1) é um subgrafo G2(V2,E2) de G1 tal
que V1=V2. Ou seja, G2 contém todos os vértices de
G1
Quando o subgrafo gerador é uma árvore, ele
recebe o nome de árvore geradora (ou de
espalhamento – spanning tree).
Centro de Informática - UFPE
Matemática Discreta
141
Árvore geradora
Uma árvore T é denominada árvore geradora de
um grafo conexo G se T é um sub-grafo de G e
contém todos os vértices de G
Centro de Informática - UFPE
Matemática Discreta
142
Subgrafo e Árvore geradora
(b) e (c) são subgrafos geradores de (a)
(c) é árvore geradora de (a) e (b)
Centro de Informática - UFPE
Matemática Discreta
143
Árvore geradora (outro exemplo)
Centro de Informática - UFPE
Matemática Discreta
144
Floresta geradora
Se um grafo é desconexo, não podemos identificar
nenhuma árvore geradora. Mas podemos identificar
no mínimo uma floresta de árvores geradoras, uma
para cada componente do grafo.
Centro de Informática - UFPE
Matemática Discreta
145
Exemplo de aplicação de árvore geradora
A figura abaixo ilustra um conjunto de terras
separadas por muros. Supondo que todas são
cheias de água, como podemos esvaziar todas,
furando um número mínimo de buracos nos muros?
Centro de Informática - UFPE
Matemática Discreta
146
Se cada terra e a área exterior formam o conjunto de
vértices, e se cada muro separando duas áreas é
representado por uma aresta, temos:
Uma árvore geradora, é a solução
Centro de Informática - UFPE
Matemática Discreta
147
Teorema
Um grafo simples é conexo se e somente se possui
uma árvore geradora
Prova:
1) Se G (simples) possui uma árvore geradora então
G é conexo
Seja T a árvore geradora de G.
T contem todos os nós de G.
Existe um caminho em qualquer dois nós de T.
Como T é subgrafo de G e contem todos os nós de G,
existe um caminho entre quaisquer dois nós de G.
Logo G é conexo
Centro de Informática - UFPE
Matemática Discreta
148
Prova:
2) Se G (simples) é conexo então ele possui uma
árvore geradora.
Se G é conexo e não é uma árvore, ele deve conter um
circuito simples.
Remova uma aresta de um desses circuitos simples.
O subgrafo resultante dessa operação possui uma
aresta a menos, mas contem todos os nós de G e ainda
é conexo.
Se esse subgrafo não é uma árvore, ele possui um
circuito simples. Do mesmo modo, remova uma aresta
desse circuito.
Repita esse processo até que não haja mais circuitos.
O resultado é uma árvore geradora de G.
Centro de Informática - UFPE
Matemática Discreta
149
Algoritmo para achar a árvore geradora
Se G não contém nenhum ciclo ele já é a sua própria
árvore geradora.
Suponhamos agora que ele contém um ciclo. Tirando
uma aresta desse ciclo resulta em um grafo ainda
conexo.
Continuando assim até que não tenha nenhum ciclo,
o grafo obtido é um grafo conexo que é uma árvore.
Algoritmo baseado na prova do teorema visto
Centro de Informática - UFPE
Matemática Discreta
150
Solução 1: {B,G}, {A,F}, {G,F}, {G,D}, {G,C},{B,C}
Solução 2: {B,G}, {A,F}, {G,F}, {E,D}, {G,D}, {B,C}
Centro de Informática - UFPE
Matemática Discreta
151
Algoritmo para achar a árvore geradora
O algoritmo baseado na prova do teorema não é
eficiente, pois ele requer que circuitos simples sejam
identificados.
No lugar de construir árvores geradoras retirando
arestas do grafo, vamos construí-las adicionando
arestas sucessivamente.
Podemos fazer isso de duas maneiras
1) Fazendo busca em profundidade
2) Busca em largura
Centro de Informática - UFPE
Matemática Discreta
152
Busca em profundidade para achar a árvore
geradora (depth-first search)
1) Arbitrariamente escolha um nó do grafo para a raiz.
2) Construa um caminho começando por esse nó, adicionando
arestas sucessivamente, onde cada nova aresta é incidente com o
último nó do caminho e com um nó ainda não pertencente ao
caminho
3) Continue adicionando arestas a esse caminho para ir o mais
longe possível.
4) Se o caminho possui todos os nós do grafo, então o caminho é a
árvore geradora do grafo.
5) Caso contrário, retorne ao nó mais próximo de maneira que um
novo caminho possa ser construído a partir desse nó e que
contenha nós ainda não visitados.
6) Esse processo continua até que todos os nós sejam incluídos na
árvore geradora
Centro de Informática - UFPE
Matemática Discreta
153
Busca em profundidade para achar a árvore
geradora (depth-first search) - Exemplo
Backtracking
Centro de Informática - UFPE
Matemática Discreta
154
Busca em árvores
Na busca em profundidade, nós penetramos o mais
profundamente possível na árvore, antes de partir
para outro vértice
Por exemplo, temos a
árvore rotulada onde os
rótulos correspondem à
ordem em que os
vértices foram visitados
pela busca em
profundidade.
Centro de Informática - UFPE
1
8
2
3
9
7
4
5
Matemática Discreta
6
11
12
10
155
Busca em largura para achar a árvore geradora
(breadth-first search)
1) Arbitrariamente escolha um nó do grafo para a raiz.
2) Adicione todas as arestas incidentes a esse nó
3) Os novos nós adicionados se tornam os nós do nível 1 da árvore
geradora
4) Arbitrariamente, ordene os nós do nível 1
5) Seguindo essa ordem, acrescente cada aresta incidente com os
nós do nível, desde que ela não forme um circuito simples.
6) Arbitrariamente, ordene os filhos de cada nó do nível 1.
7) Isso produz os nós do nível 2
8) Esse processo continua até que todos os nós sejam incluídos na
árvore geradora
Centro de Informática - UFPE
Matemática Discreta
156
Busca em largura para achar a árvore geradora
(bread-first search) - Exemplo
3
2
1
Centro de Informática - UFPE
Matemática Discreta
157
Busca em árvores
Na busca em amplitude, nós percorremos o
máximo de vértices possíveis antes de penetrar
mais profundamente na árvore.
Isso significa que visitamos todos os vértices
adjacentes ao vértice atual antes de prosseguir
para outro vértice.
Centro de Informática - UFPE
Matemática Discreta
158
Busca em árvores
Considerando a árvore ao
lado, começamos pelo
vértice a e percorremos os
vértices b e c que são
adjacentes a a . Depois,
percorremos os vértices d e
e, adjacentes a b, e os
vértices f, g e h, adjacentes
a c; e assim por diante.
a
d
f
g
e
i
Centro de Informática - UFPE
c
b
Matemática Discreta
j
k
h
l
159
Busca em árvores
A figura abaixo nos mostra uma árvore rotulada
onde os rótulos correspondem à ordem em que os
vértices foram visitados pela busca em amplitude, no
exemplo anterior
1
3
2
4
6
5
9
Centro de Informática - UFPE
10 11
7
8
12
Matemática Discreta
160
Backtracking para decidir se um grafo pode ser
colorido com n cores
1) Arbitrariamente escolha um nó a e associe a cor 1 a ele
2) Escolha um nó b e se ele não for adjacente a a, associe a cor 1 a
ele, caso contrário associe a cor 2.
3) Agora vá para o terceiro nó c, e associe a cor 1 se possível, caso
contrário a cor 2, se não for possível também, associe a cor 3.
4) Continue esse processo usando uma das n cores.
5) Caso você encontre um nó que não pode ser colorido com uma
das n cores, retroceda até o último nó colorido e tente trocar a sua
cor para a próxima da lista, caso não seja possível, retroceda
novamente a partir desse nó e assim sucessivamente até que você
encontre um nó que seja possível mudar a sua cor e aí o processo
de colorir continua.
Centro de Informática - UFPE
Matemática Discreta
161
Backtracking para decidir se o grafo a seguir
colorido com 3 cores
e
d
a
a
Centro de Informática - UFPE
b
c
b
c
c
d
d
e
e
Matemática Discreta
162
Backtracking para encontrar um subconjunto de
um conjunto de inteiros cuja a soma de seus
elementos é M
1) Arrumamos o conjunto numa ordem
2) Começamos com a soma de nenhum termo
3) Um inteiro na sequencia é incluído se a soma permanece menor
que M quando esse inteiro é incluído
4) Se ao encontrar um termo cuja a inclusão dê uma soma maior
que M, retroceda apagando o último termo da soma
Ex: encontre um subconjunto de {31,27,15,11,7,5}, cuja soma é
igual a 39.
Centro de Informática - UFPE
Matemática Discreta
163
Ex: encontre um subconjunto de {31,27,15,11,7,5}, cuja soma é
igual a 39.
Ø
Soma = 0
{31}
{27}
Soma = 31
Soma = 27
{31,7}
{31,5}
{27,11}
{27,7}
Soma = 38
Soma = 36
Soma = 38
Soma = 34
{27,7,5}
Soma = 39
Centro de Informática - UFPE
Matemática Discreta
164