700450_unidade 5- arvores

Prévia do material em texto

1
Unidade V
Árvores (1)
Pontifícia Universidade Católica de Minas Gerais
Prof. Pasteur Jr e Prof. Max do Val 
Machado
1 Conjunto de transparências baseado no material da Profa. Raquel Mini
2
Árvore
• Árvore é um grafo conexo que não 
contém circuitos.
• TEOREMA 1: Em uma árvore existe 
um e apenas um caminho entre cada 
par de vértices.
• TEOREMA 2: Se em um grafo G, 
existe um único caminho entre 
qualquer par de vértices, então G é
uma árvore.
• TEOREMA 3: Uma árvore com n
vértices tem n-1 arestas
3
Árvore
• TEOREMAS:
– Todo grafo conexo com n vértices e n-1 
arestas é uma árvore
– Um grafo G é uma árvore se, e somente 
se, a remoção de qualquer aresta o 
desconectar (grafo minimamente 
conectado).
– Um grafo G com n vértices, n-1 arestas e 
nenhum circuito é conexo
4
Árvore
• Então, um grafo G com n vértices é uma 
árvore se:
– G é conexo e sem circuito, ou
– G é conexo e tem n-1 arestas, ou
– G é sem circuito e tem n-1 arestas, ou
– Existe exatamente 1 caminho entre todos 
os pares de vértices de G, ou
– G é um grafo minimamente conectado
• Em qualquer árvore com pelo menos 2 
vértices existem pelo menos 2 vértices 
pendentes
5
Árvore
• Em um grafo G, a distância d entre um par 
de vértices v1 e v2 corresponde ao número 
de arestas no menor caminho que une v1
a v2
• A excentricidade de um vértice v em um 
grafo conexo G é a distância de v ao 
vértice mais distante
)vd(v, i
6
Centro de uma Árvore
• O centro de um grafo G é o vértice de 
menor excentricidade
3
3
3
3
2 2
7
Centro de uma Árvore 
• TEOREMA: Toda árvore tem exatamente 1 
ou 2 centros
• COLORÁRIO: Se uma árvore tem 2 
centros, então estes centros são 
adjacentes
• Raio de um árvore é a excentricidade do 
centro
• Diâmetro de uma árvore é o comprimento 
do maior caminho em T
8
Árvore Geradora
• Uma árvore geradora de um grafo conexo 
G é um subgrafo de G que contém todos os 
vértices de G e é uma árvore
• Árvore geradora só é definida para grafos 
conexo porque toda árvore é conexa. 
Grafos não conexo possuem florestas 
geradoras
9
Árvore Geradora
• Dado um grafo G e uma árvore geradora 
T de G, define-se:
Galho: um aresta de G em T
Corda: uma aresta de G que não 
pertence a T
• TEOREMAS:
– Todo grafo conexo G tem uma árvore 
geradora
– Dado um grafo conexo G com n vértices, 
e arestas e uma árvore geradora T de G, 
G tem n-1 galhos e e-n+1 cordas
10
Árvore Geradora
• Exemplo: Um fazendeiro possui 6 lotes 
murados como mostrado na figura 
abaixo. Os lotes estão cheios de água. 
Quantos muros devem ser removidos 
para que toda a água seja liberada?
11
Árvore Geradora
• Definições:
Rank de G: número de galhos em 
qualquer floresta geradora de G
r = n-k
Nulidade de G: número de cordas em 
qualquer floresta geradora de G
µ = e-n+k
Rank + Nulidade = número de arestas
12
Circuito Fundamental
• Um grafo conexo G é uma árvore se e 
somente se a adição de uma aresta 
entre qualquer dois vértices de G cria 
exatamente 1 circuito.
• Dado um grafo conexo G, a inclusão de 
uma corda em T cria um único circuito 
que é chamado de circuito fundamental.
• A inserção de arestas em uma árvore 
pode criar vários circuitos, mas circuitos 
fundamentais são aqueles que possuem 
quantos galhos forem necessários e uma 
única corda.
13
Circuito Fundamental
• Exemplo: 
14
Árvore Geradora Mínima
• Árvore Geradora Mínima é a árvore 
geradora de menor peso de G
• Problema: Dado um grafo G com pesos 
associados às arestas, encontrar uma 
árvore geradora mínima de G
• Exemplo: Devemos conectar n cidades 
v1,v2,...,vn através de uma rede de 
estradas. Seja cij o custo de construir 
uma estrada entre as cidades vi e vj. O 
problema é então encontrar a rede que 
minimiza o custo para conectar as n
cidades.
15
Árvore Geradora
• Exemplo: Um pomar com 10 pés de 
frutas deve ser irrigado.
• Cada cano entre duas árvores tem um 
custo proporcional ao comprimento do 
cano e à dificuldade e implantação
• Como encontrar o sistema de irrigação 
que minimiza o custo de implantação?
16
Algoritmo de Prim para 
Árvore Geradora Mínima
Crie um grafo T e um TAD para arestas.
Escolha um vértice i, o insira em T.
Insira todas as arestas do vértice i no TAD.
Enquanto todos os vértices não estiverem em T faça
Faça
Remova a menor aresta (i, j) do TAD
Enquanto (i T e j T)
Insira a aresta (i,j) e o vértice não pertencente a T em T
Insira as demais arestas desse vértice no TAD
Fim Enquanto
4
3 2
1
5
6
3 6
2
a b
d
c
e
f
17
• Algoritmo de Kruskal
Inicialize T como vazia
para i ← 1 até n-1 faça
Escolha a menor aresta de G-T que
não cria circuito em T
Insira essa aresta em T
fim para
C
B
A
D
E
F
305
5
10
20 20
10
20
10
Algoritmo de Kruskal para 
Árvore Geradora Mínima