Árvores
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvores
• Grafo Acíclico: não possui ciclos
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvores
• Grafo Acíclico: não possui ciclos
• Uma árvore é um grafo conexo acíclico
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvores
• Grafo Acíclico: não possui ciclos
• Uma árvore é um grafo conexo acíclico
Todas as árvores com 6 vértices
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Floresta
Um grafo acíclico é também
chamado de floresta.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Um grafo T é uma árvore
sss
existir um único caminho entre cada
par de vértices de T
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Prova
• () Por contradição!!!
– T é uma árvore
• v e w dois vértices quaisquer de T
– não existe caminho entre v e w ou
– P1e P2: dois caminhos-(u,v) distintos
» Existem necessariamente dois vértices t1 e t2  P1 e
P2 tais que entre t1 e t2, P1 e P2 são distintos
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Prova
• () Também por contradição!!!
– existe um único caminho entre cada par de
vértices: T é conexo
– Sup. T não é acíclico:
• existe um ciclo C em T
• seja {v,w} uma aresta de C:
– dois caminhos entre v e w em T (contradição!)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Se T é uma árvore então m=n-1
Prova:
• Por indução em n!!!!
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Folha de uma árvore
• Uma folha de uma árvore é um vértice v tal
que d(v) = 1
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema
Toda árvore possui
pelo menos duas folhas, n > 1.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Um grafo conexo é uma árvore
sss
toda aresta é uma ponte
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Distância
• Conceitos útil para se medir a localização
relativa entre diferentes vértices de uma
árvore ou de um grafo
• Distância d(v,w):
– na árvore: número de arestas do caminho
que liga v a w
– em um grafo conexo: número de arestas do
menor caminho que liga v a w.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Excentricidade de um vértice
em um grafo
• Excentricidade de um vértice E(v): o valor
da maior distância entre v e qualquer
outro vértice de G.
E(v) = max d(v,vi), v  V
vi V
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Centro
• O conjunto de vértices com excentricidade
mínima em um grafo é denotado centro do
grafo
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Diâmetro e vértice periférico
• Diâmetro de um grafo G é a maior das
excentricidades existentes em G.
• Vértice periférico de um grafo G é um
vértice cuja excentricidade é igual ao
diâmetro
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Qual o centro, o diâmetro e os
vértices periféricos?
G
a
c
e
b
2010/1
d
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
As propriedades seguintes são equivalentes:
a) G é um grafo conexo e acíclico;
b) G é acíclico e tem n-1 arestas;
c) G é conexo e tem n-1 arestas;
d) G é sem ciclos e por adição de uma aresta se cria
um único ciclo;
e) G é conexo mas G' = G – e é desconexo, e  E;
f) todo par de vértices de G é unido por um e só um
caminho simples.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Prova
a)
b)
c)
d)
e)
f)
a)
Exercício!!!
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Toda árvore é um grafo bipartido.
Exercício!!!
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
O centro de uma árvore
possui um ou dois vértices.
Exercício!!!
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Subgrafo gerador
• Relembrando: um grafo H é subgrafo de G
se V(H)  V(G) e E(H)  E(G). Se V(H) =
V(G) então H é subgrafo gerador ou de
espalhamento de G.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvore Geradora
• Uma árvore geradora é um subgrafo
gerador de G que é uma árvore.
• Uma árvore geradora em um grafo G é um
subgrafo minimal que conecta todos os
vértices de G;
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Todo grafo conexo possui uma árvore
geradora
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Corolário:
Se G é conexo, então m  n-1
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Seja T uma árvore geradora
de um grafo conexo G
e seja a uma aresta de G,
a T. Então T+ a contém um único ciclo.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Prova:
• Como T é acíclico, cada ciclo de T+a
contém a.
C é um ciclo de T+e sse C-e é um caminho
em T ligando os extremos de e.
Pelo teorema, T tem um único caminho
desse tipo, logo T+e contém um único
ciclo.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
• Como T é acíclico, cada ciclo de T+a
contém a.
• C é um ciclo de T+a sss C-a é um
caminho em T ligando os extremos de a.
Pelo teorema, T tem um único caminho
desse tipo, logo T+e contém um único
ciclo.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
• Como T é acíclico, cada ciclo de T+a
contém a.
• C é um ciclo de T+a sss C-a é um
caminho em T ligando os extremos de a.
• Pelo teorema, T tem um único caminho
desse tipo, logo T+a contém um único
ciclo.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Algoritmos
• Para construção de uma árvore geradora;
• Para construção de uma árvore geradora
mínima.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Busca em Profundidade
entrada: G = (V,E), Lista de Adjacência de G: A(v), v  V
1. i ← 1;
2. F ← ;
PBP(v)
3. para-todo v  V faça
{
1. indice(v) ← i;
1.
indice(v) ← 0;
2. i ← i+1;
5. fim-para-todo
3. para-todo v´  A(v) faça
6. enquanto existir u, indice(u) = 0 faça
4. se indice(v´) = 0 então
1.
PBP(u);
5.
F ← F U {{v,v´}};
8. fim-enquanto
6.
PBP(v´);
saída: F
7.
fim-se
8. fim-para-todo
}
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Complexidade
• Para cada v  V, PBP(v) é chamado apenas
uma vez quando o vértice ainda não foi visitado
(indice(v) = 0)
• Tempo gasto por PBP(v): proporcional a d(v)
• Tempo gasto por todas as chamadas de PBP(v):
proporcional a |E|
• Linhas 3 – 8: O(n)
• Construção de F: O(|E|)
• Complexidade: O(max {n,|E|})
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvores geradoras
em um grafo valorado
• O peso de uma árvore geradora T de G é
definido como a soma dos valores de
todas as arestas de T.
• Diferentes árvores geradoras de T podem
ter diferentes pesos.
• Árvore Geradora mínima: a árvore
geradora de G de menor peso.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvore geradora mínima
• Aplicações:
– Em problemas de interligação (comunicação,
redes de luz, esgotos, etc.)
– Em problemas de construção de redes de
menor custo (malhas rodoviárias, redes de
computadores)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
Uma árvore geradora T
de um grafo conexo valorado G é mínima
sss
não existe qualquer outra árvore geradora
de G, a uma distância 1 de T,
cujo peso é menor que o peso de T.
Distância entre Ti e Tj de G: número de arestas de
G presentes em Ti mas não presentes em Tj.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Algoritmo de Prim
entrada: G = (V,E), Lista de Adjacência de G: A(v), v  V, matriz de pesos
1.
T ← ;
2.
V´ ← {u};
3.
para-todo v  V – V´ faça
4.
L(v) ← peso ({u,v});
5. fim-para-todo
6. enquanto V´  V faça
7.
ache um vértice w tal que L(w) = min {L(v)| v  V-V´};
8.
u = o vértice de V´, ligado a w, representando a aresta com o menor custo;
9.
e = {u,w};
10.
T ← T U {e};
11.
V´← V´ U {w};
12.
para-todo v  V – V´ faça
13.
se peso({v,w}) < L(v) então
14.
L(v) ← p({v,w});
15.
16.
fim-se
fim-para-todo
17. fim-enquanto
saída: T
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Complexidade
• Linhas 6 - 16: n-1 vezes
• Linhas 7- 8: n-1 vezes
• Linhas 11 – 15: n-1 vezes
• Complexidade: O(n2)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Teorema:
O algoritmo de Prim acha
uma árvore geradora mínima
de um grafo conexo G
não orientado.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Algoritmo de Kruskal
entrada: G = (V,E), Lista de Adjacência de G: A(v), v  V,
matriz de pesos
1. se peso (ei) > peso (ej) então
2.
i > j;
3. fim-se
// ordenar as arestas pelos pesos
4. T ← ;
5. para-todo i = 1, ..., |E| faça
6.
se T U {ei} é acíclico então
7.
T ← T U {ei};
8.
fim-se
9. fim-para-todo;
saída: T
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Complexidade
• Exercício!!
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES