CONTAGEM E CODIFICAÇÃO DE ÁRVORES
PAULO JORGE M. TEXEIRA
1. Motivação
São inúmeros os problemas que podem ser modelados através de árvores. As árvores são estruturas de
dados extremamente úteis em muitas aplicações e admitem tratamento computacional eficiente quando
comparadas às estruturas mais genéricas como os grafos (os quais, por sua vez são mais flexı́veis e complexos). As diferentes aplicações de árvores necessitam de estruturas bem mais complexas, como veremos
no decorrer deste trabalho.
2. Conceitos Iniciais da Teoria de Grafos
Um grafo não orientado, ou simplesmente grafo G é um par (V, E), onde V é o conjunto de vértices e E
é o conjunto de arestas. Indicaremos por |V | = n e |E| = m a quantidade de elementos de cada conjunto.
Cada aresta é um subconjunto de V com 1 ou 2 vértices.
Dada uma aresta {v, w} ∈ E, os vértices v e w são denominados extremidades da aresta, ou então,
que a aresta incide sobre os vértices v e w. Uma aresta unitária, da forma {v} é dito um laço. No
caso de um laço, a aresta unitária é ”contada” duas vezes quando da determinação do grau do vértice
e, portanto, contribui com 2(duas) unidades para o seu grau. Neste trabalho, os grafos considerados são
finitos (possuem um número finito de vértices) e não possuem laços.
Um subgrafo H de G é dito um subgrafo gerador ou de espalhamento de G se V (H) = V (G).
Dois vértices são adjacentes ou vizinhos quando são extremidades de uma aresta. O conjunto de vizinhos
de um vértice v é o conjunto N (v) = {w ∈ V /{v, w} ∈ E}. A cardinalidade |N (v)| ou então, o número de
arestas incidentes em v, é dita o grau de v, e indicado por d(v).
A excentricidade de um vértice v de um grafo G, denotada por e(v), é a maior das distâncias do vértice
v aos demais vértices do grafo G, isto é: e(v) =
máx{d(v, w)/w ∈ V (G), w 6= v}.
O diâmetro de um grafo G, denotado por diâmetro (G), é o maior valor dentre todas as excentricidades
dos vértices de G, isto é: diâmetro (G) = máx {e(v)/v ∈ V (G)}.
O raio de um grafo G, denotado por raio(G), é o menor valor dentre todas as excentricidades dos vértices
de G, isto é: raio(G) = mı́n{e(v)/ v ∈ V (G)}. O centro de um grafo G, denotado por C(G), é o conjunto
de vértices do grafo G que têm a menor excentricidade, isto é: C(G) = {v ∈ V (G)/e(v) é mı́nimo }.
Portanto, em vista da definição, tem-se que o centro de um grafo não é formado, necessariamente, por um
único vértice.
Dado um grafo G = (V, E), um passeio em G é uma seqüência de vértices de G : v1 , v2 , ....., vk tais que
toda aresta (vi , vi+1 ) ∈ E, i, 1 6 i 6 k − 1. O comprimento do passeio é dado pelo número de arestas
que o compõem, isto é, k − 1 como indicado anteriormente. O vértice v1 é chamado de origem (ou inı́cio)
2
PAULO JORGE M. TEXEIRA
do passeio e o vértice vk seu término (ou fim). Um passeio em que não há repetição de arestas, isto é:
todas as arestas do passeio são distintas, é dito uma trilha ou trajeto. Em particular, se não há repetição
de vértices, o passeio é dito um caminho. Um passeio v1 , v2 , · · · , vk é dito fechado quando o vértice de seu
inı́cio coincide com o vértice de seu término, isto é: v1 = vk . Analogamente, uma trilha ou um caminho
são ditos fechados quando o vértice de inı́cio coincide com o vértice final. Um caminho é dito hamiltoniano
se é composto por uma seqüência de arestas que percorre os vértices do grafo uma e somente uma única
vez.
Uma trilha é dita hamiltoniana se é um caminho hamiltoniano que, partindo de um qualquer vértice de
um grafo G conexo, retorna ao vértice inicial de tal modo que, exceto para o vértice inicial, foi percorrido
um caminho hamiltoniano. Assim, fica formado um circuito com todos os vértices do grafo G e, portanto,
todos os vértices desse circuito têm grau igual a 2(dois). Um ciclo é um passeio fechado v1 , v2 , · · · , vk−1 , vk ,
v1 tal que v1 , v2 , · · · , vk é um caminho. Ou seja, um ciclo é um caminho de comprimento maior do que ou
igual a 3, em que o primeiro e o último vértices coincidem. Um ciclo simples é um caminho de comprimento
maior do que ou igual a 3 em que somente o primeiro e o último vértices coincidem. O tamanho de um
passeio fechado é dado pelo número de arestas que o compõem. Em particular, o comprimento de um
ciclo é dado pelo seu número de vértices distintos ou, equivalentemente, de seu número de arestas. Um
ciclo com um número par de arestas é dito um ciclo par, e com um número ı́mpar de arestas é dito um
ciclo ı́mpar. Um grafo que não possui ciclos é dito acı́clico. Um grafo é conexo quando existir pelo menos
um caminho entre cada par de vértices. Caso contrário é dito desconexo. Uma componente conexa é um
subgrafo conexo do grafo considerado. Indicamos o número de componentes conexas de um grafo G por
w(G).
Uma árvore é um grafo conexo e acı́clico. Uma corda em um ciclo é uma aresta que é adjacente a dois
vértices não consecutivos desse ciclo. Uma corda em um caminho é uma aresta que é adjacente a dois
vértices não consecutivos de um caminho.
3. Introdução
Quando dois ou mais grafos têm particularidades próprias entre si dizemos que eles pertencem à mesma
famı́lia de grafos. Assim, podemos definir uma famı́lia de grafos como o conjunto (finito ou não) de todos
os grafos que satisfazem a uma ou mais propriedades (as quais caracterizam essa famı́lia) que precisam ser
claramente atendidas por todos os seus elementos.
Normalmente, a definição de uma famı́lia consiste em mencionar a propriedade satisfeita pelos grafos
que a constituem.
Como o conjunto de todos os grafos é infinito, o máximo que podemos afirmar é que um grafo pode
pertencer a mais de uma famı́lia, de acordo com a caracterização a ela dada. O universo dos grafos tem
sido então, largamente estudado, através de diferentes famı́lias com suas especı́ficas caracterı́sticas.
O grande desafio da comunidade de Teoria dos Grafos é:
* estabelecer condições que caracterizam com precisão os elementos de cada famı́lia assim definida;
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
3
* encontrar condições que permitam determinar o total de elementos de cada famı́lia; e
* definir a maneira de ser possı́vel construir grafos que atendam às propriedades estabelecidas para cada
uma das famı́lias. Entre essas famı́lias podemos destacar:
* a famı́lia dos grafos eulerianos (aqueles grafos em que é possı́vel verificar a existência de um
circuito (ou ciclo) que inclua exatamente uma vez cada aresta);
O problema foi estudado pela primeira vez por Euler (1707-1783) e, por essa razão um circuito que
percorre cada aresta de um grafo exatamente uma vez é dito um circuito euleriano e, um grafo que possui
tal circuito é então chamado de grafo euleriano.
* a famı́lia dos grafos hamiltonianos (aqueles grafos em que é possı́vel verificar a existência de um
circuito (ou ciclo) que inclua exatamente uma vez cada vértice);
Um circuito passando exatamente uma vez por cada vértice de um grafo é chamado de circuito hamiltoniano, em homenagem ao matemático irlandês William Rowan Hamilton (1805-1865), que estudou este
problema no grafo determinado pelas arestas de um dodecaedro regular. Um grafo que possui um circuito
hamiltoniano é então chamado de grafo hamiltoniano.
Há grafos que podem pertencer a mais de uma famı́lia. Por exemplo, os grafos da famı́lia de ciclos
são eulerianos e hamiltonianos. Há outros grafos que são eulerianos e não são hamiltonianos. Há outros
que são hamiltonianos mas não são eulerianos, e há outros que não são eulerianos e também não são
hamiltonianos.
* a famı́lia dos grafos planares (aqueles em que sua representação no plano seja possı́vel desde que
atenda ao fato de que quaisquer duas arestas nunca se cruzem, podendo as arestas até ter um vértice em
comum).
* a famı́lia das árvores (aqueles grafos que são conexos e acı́clicos e com o menor número de arestas);
* a famı́lia dos grafos isomorfos (aqueles grafos em que há uma bijeção entre os conjuntos de vértices
de cada um deles e de tal modo que as adjacências entre arestas fiquem preservadas, conforme a definição
a seguir);
3.1. O Problema do Isomorfismo entre Grafos.
Dois grafos G1 = (V1 , E1 ) e G2 = (V2 , E2 ) são ditos isomorfos quando existir uma bijeção f : V1 −→ V2
tal que, para todo v, w ∈ V1 , {v, w} ∈ E1 ⇐⇒ {f (v), f (w)} ∈ E2 . Ou seja: vértices vizinhos de G1 devem
ser mapeados (têm sua imagem) pela função f em vértices vizinhos de G2 e vice-versa.
Exemplo 3.1.1. A função f : {1, 2, 3, 4, 5} −→ {m, n, o, p, q} tal que: f (1) = n, f (2) = q, f (3) = o,
f (4) = p e f (5) = m define um isomorfismo entre os grafos G1 e G2 representados na figura a seguir.
Decidir, por exemplo, quando dois grafos finitos G1 e G2 são isomorfos é um problema de difı́cil solução.
O problema do isomorfismo entre grafos consiste em obter um algoritmo que verifique se dois grafos
G1 = (V1 , E1 ) e G2 = (V2 , E2 ) são isomorfos. A solução deve exibir uma função que associe de modo
4
PAULO JORGE M. TEXEIRA
q
3
2
1
n
4
5
m
o
p
Figura 1. Dois grafos Isomorfos
biunı́voco os vértices dos dois grafos, preservando a noção de adjacência. Inicialmente, como condição
necessária para que isto ocorra é preciso que ambos os conjuntos de vértices tenham a mesma quantidade
de elementos, ou seja: |V1 | = |V2 | = n. Caso contrário não podem existir bijeções de V1 em V2 .
A solução da verificação da existência ou não de um isomorfismo entre dois grafos por ”força bruta”
é aquela em que devemos experimentar todas as funções bijetoras existentes de V 1 para V 2 (ou parte
delas) , verificando, para cada uma, se a relação de adjacência expressa pelo conjunto de arestas de G1 é
preservada no conjunto de arestas de G2 . Ora, quando |V1 | = |V2 | = n, existem n! bijeções distintas de V1
em V2 . Assim, será preciso exibir pelo menos uma, dentre as n! possı́veis bijeções de G1 para G2 , o que
evidencia a ineficiência deste algoritmo.
Não é conhecido até o momento, na literatura, um algoritmo eficiente (de complexidade
polinomial) que permita verificar se dois grafos quaisquer (que não pertencem a uma famı́lia conhecida,
ou essa famı́lia não foi caracterizada no momento da verificação, ou os grafos não satisfazem à nenhuma
propriedade em especial) são ou não grafos isomorfos, ou seja, um algoritmo que resolva o problema da
verificação do isomorfismo. E, também, ainda não
foi provado que tal algoritmo não existe . Para
a famı́lia das árvores o problema tem solução de forma eficiente, isto é, pode ser verificado o isomorfismo
entre duas árvores, em tempo linear, no número de vértices.
3.2. Representação de Grafos.
Um esquema de representação é uma maneira alternativa de exibir os grafos de uma determinada famı́lia.
O resultado obtido pela aplicação de um esquema a um grafo G = (V, E), onde |V | = n e |E| = m, E =
{{u, v}/u ∈ V, v ∈ V } é chamado representação para o grafo. É preciso explicitar n vértices e m
pares de vértices. A partir dela, os conjuntos de vértices e arestas do grafo representado devem poder ser
deduzidos sem ambigüidades.
A seguir apresentamos alguns esquemas de representação:
3.2.1. O esquema de representação mais usual para grafos arbitrários é o gráfico, onde:
* todo grafo pode ser representado sobre uma superfı́cie por um conjunto de pontos e segmentos de
curvas de tal modo que a cada vértice corresponda um ponto e a cada aresta corresponda um segmento
de curva interligando os pontos associados às suas extremidades.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
5
* essa representação gráfica não é única.
3.2.2. - Outro esquema consiste em mencionar, para todo vértice v ∈ V , seu conjunto de vizinhos N (v),
construindo um conjunto de pares da forma {(v, {N (v)})/v ∈ V }. Numa representação obtida por esse
X
esquema são mencionados
(1 + |N (v)|) = n + 2m termos.
v∈V
Exemplo 3.2.2.1. Subfamı́lia dos grafos conexos cujos vértices possuem grau 2. Uma caracterização
equivalente seria dizer que os grafos integrantes desta famı́lia são ciclos simples sem arestas interiores
(cordas). Logo, grafos com n vértices desta famı́lia possuem exatamente n arestas. O esquema de representação por vizinhos exige a nomeação de n + 2n = 3n elementos. Por exemplo, considere o ciclo
representado abaixo:
1
6
2
5
4
3
Figura 2
Representação por vizinhos: {(1, {2, 6}), (2, {1, 3}), (3, {2, 4}), (4, {3, 5}), (5, {4, 6}), (6, {5, 1})}. Figura
2: Um ciclo simples com 6 vértices e seu esquema de representação por vizinhos.
3.3. Um esquema alternativo mais compacto para representar os grafos de um ciclo é utilizar uma
seqüência de n vértices, dispostos na mesma ordem em que figuram no ciclo: ¿ 1, 2, 3, 4, 5, 6 À. Esta representação não é única pois o mesmo grafo poderia ser representado por ¿ 1, 6, 5, 4, 3, 2 À ou
¿ 2, 3, 4, 5, 6, 1 À, por exemplo.
Ao utilizarmos um esquema de representação, se cada grafo da famı́lia possui uma única representação
esta é denominada um Código. Neste caso, a correspondência entre grafos e códigos deve ser biunı́voca. O
processo para a obtenção do código para um determinado grafo de uma dada famı́lia chama-se
Codificação.
A validação de um código consiste em determinar se a ele corresponde um grafo da famı́lia, sem
explicitamente exibir tal grafo. A construção explı́cita do grafo a partir de seu código chama-se
Decodificação.
Algumas vezes, o estudo de codificações para famı́lias particulares de grafos conduz à solução de problemas de contagem e geração. Esse é o caso da famı́lia das árvores. Na seção 9 será apresentado o Código
de Prüfer para a Codificação e Decodificação de Árvores, objeto deste trabalho.
6
PAULO JORGE M. TEXEIRA
A seguir, apresentamos algumas propriedades básicas de árvores, introduzimos alguma terminologia
conveniente para trabalhar com árvores e provamos algumas fórmulas úteis de contagem sobre árvores.
4. Definições Básicas em Árvores e Árvores Enraizadas
Um dos tipos especiais de grafos mais amplamente utilizados em diferentes aplicações é uma árvore.
Há uma importante utilização como modelos combinatórios em quı́mica, ciência da computação, pesquisa
operacional, ciências sociais, e muitas outras áreas da matemática aplicada. Devido à sua relativa simplicidade estrutural, as árvores são uma das classes de grafos mais intensamente estudadas. Portanto, gerar
árvores é um importante problema computacional.
Definição 4.1. Uma árvore enraizada T é um grafo com um determinado vértice r, chamado de raiz, e
pode-se provar (mais adiante será feito) que há um único caminho da raiz até qualquer dos outros vértices.
Após a definição do vértice raiz, os vértices restantes constituem um único conjunto vazio ou são divididos
em k (k > 1) conjuntos disjuntos, distintos e não vazios, que são as subárvores de r, onde cada subárvore
é, por sua vez, uma árvore.
Observação 4.2. Uma árvore enraizada T tem uma única raiz.
De fato.
Suponha, por absurdo, que seus vértices a e b sejam, ambos, raı́zes de T . Então, haveria caminhos do
vértice a para o vértice b e do vértice b para o vértice a, formando um ciclo, o que é uma contradição.
Assim, uma vez enraizada, uma árvore tem uma única raiz.
Intuitivamente, uma árvore em Teoria dos Grafos parece-se com uma árvore real no sentido de que toda
árvore pode ser desenhada com a ”aparência” de uma árvore real.
Notação: A notação Tr indica a subárvore de T com raiz em r se r é um vértice de T .
Como os conjuntos das subárvores têm de ser disjuntos observe que a estrutura indicada na Figura 3,
abaixo, não é uma árvore. Podemos também observar que há dois caminhos distintos entre os vértices A
e H: um caminho passando pelo vértice C e outro caminho passando pelo vértice B.
Além do mais, se uma árvore é um grafo não direcionado (sem arestas direcionadas), então, qualquer
vértice pode ser a raiz da árvore. Por exemplo, considere os exemplos de árvores na Figura 4, abaixo.
O vértice rotulado por a é uma raiz para cada uma dessas árvores. A árvore mais à direita na Figura
4 é desenhada de tal forma que a parece ser uma raiz, mas a árvore mais abaixo na Figura 4, que é a
árvore mais à direita redesenhada, não possui nenhum vértice que seja uma raiz natural. Isto é, qualquer
vértice pode ser a raiz. Finalmente, uma árvore não tem ciclos (num grafo direcionado, não há ciclos
mesmo quando as direções das arestas são ignoradas), porque um ciclo forneceria dois modos de se chegar
da raiz a certos vértices. Isso prova que há um único caminho da raiz até qualquer dos outros vértices. Por
−→
exemplo, na árvore da esquerda na Figura 4, o acréscimo de uma aresta (g, h) criaria um ciclo (quando as
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
7
A
B
C
D
E
H
F
G
I
Figura 3
h
a
d
b
c
e
d
h
f
i
j
b
e
g
a
k
l
i
j
f
k
m
c
l
g
i
h
j
e
d
b
a
k
l
c f
m
g
Figura 4
direções das arestas são ignoradas) e um segundo caminho de a para h via g ; o acréscimo de uma aresta
−→
(d, a) cria um ciclo o que faz com que se tenha um segundo caminho de a para a, uma vez que já temos o
caminho nulo de a para a.
4.1. Propriedades das árvores enraizadas.
Em grande parte deste parágrafo estaremos usando árvores com arestas direcionadas. Seguindo a terminologia comum, chamamos de árvore direcionada a uma árvore enraizada (ao contrário de uma árvore
8
PAULO JORGE M. TEXEIRA
não direcionada que não tem raiz (no sentido de que não tem uma raiz em especial)). Uma árvore não
direcionada pode ser transformada em uma árvore enraizada escolhendo-se um vértice como raiz e, então,
direcionando todas as arestas saindo da raiz. Em uma árvore T = (V, E), qualquer vértice pode ser eleito
como raiz, tornando-a enraizada.
Uma árvore cuja raiz não é determinada a priori é simplesmente chamada uma árvore livre. Essas
definições são usadas para árvores enraizadas e não enraizadas.
Por exemplo, para enraizar a árvore não direcionada que está no meio na Figura 4, no vértice a,
simplesmente podemos direcionar todas as arestas da esquerda para a direita.
O modo padrão de desenhar uma árvore enraizada T é colocar a raiz a no topo da figura. Então os
vértices adjacentes de a são colocados num nı́vel abaixo do nı́vel de a, e assim por diante, como na primeira
árvore da Figura 4. Dizemos que a raiz está no nı́vel 0, os vértices b e c naquela árvore estão no nı́vel 1,
os vértices d, e, f , e g naquela árvore estão no nı́vel 2 e assim por diante. Para qualquer vértice x em T ,
exceto a raiz, o pai de x é o único vértice y com uma aresta para x (o mais próximo do último vértice no
caminho único de a para x). Reciprocamente, o vértice x é um filho do vértice y. Se dois vértices têm o
mesmo pai, eles são irmãos. Na primeira árvore da Figura 4, o vértice e tem o vértice b como seu pai, os
vértices h e i como seus filhos, os vértices d e f como seus irmãos, o vértice a como seu outro ancestral, e
o vértice l como seu outro descendente. Os ancestrais de um vértice v em uma árvore enraizada são todos
os vértices no (único) caminho simples entre a raiz e v (incluindo o próprio vértice v). A raiz é, portanto,
um ancestral comum a todos os vértices. Um vértice w é descendente de v se, e somente se, v for ancestral
de w. A relação pai-filho se estende aos ancestrais e descendentes de um vértice.
Seja n o vértice raiz da subárvore Tn de T . Os vértices raı́zes n1 , n2 , · · · , nk das subárvores de Tn são
chamados de filhos de n e n é o pai destes vértices, que são vértices irmãos entre si. Se z é filho de n1
então n2 é tio de z e n é avô de z. O grau de uma árvore é o máximo entre os graus de seus vértices.
Denomina-se caminho numa árvore a uma seqüência de vértices distintos v1 , v2 , · · · , vk−1 , vk , de modo que
exista sempre a relação ”vi é pai de vi+1 ” ou ”vi é filho de vi+1 ” entre vértices consecutivos, isto é, entre
v1 e v2 , entre v2 e v3 , · · · , entre vk−1 e vk . Diz-se que v1 alcança vk e que vk é alcançado por v1 , quando
há um único caminho entre os vértices v1 e vk . Um caminho de k vértices é obtido pela sequência de k − 1
pares de vértices. Nesse caso o caminho é dito de comprimento k − 1.
Definimos o número do nı́vel ou profundidade de um vértice x em M como o comprimento do único
caminho do vértice a para o vértice x, ou seja, é o número de vértices do caminho entre a raiz e o vértice.
O nı́vel de um vértice é o número de ancestrais que ele possui. O nı́vel da raiz (ou profundidade de uma
árvore) é, portanto, igual a 1. Na Figura 4, o comprimento do caminho entre o vértice a e o vértice h é 3.
Cada vértice x em T é a raiz da subárvore de x e seus descendentes. O número de filhos de um vértice
x é chamado grau de saı́da desse vértice, e indicado por d+ (x). Se um vértice u pertence à subárvore Tv
(v é a raiz de Tv ), então u é descendente de v e v é dito ancestral ou antecessor de u. Se, neste caso, u
é diferente de v então u é dito descendente próprio de v e v é ancestral próprio de u. Um vértice que não
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
9
possui descendentes próprios (vértices sem filhos) é chamado de vértice folha. Ou seja, um vértice folha é
aquele com grau de saı́da nulo. Assim, um vértice v tal que d(v) = 1 é chamado folha.
Um vértice que não é folha é chamado vértice interior ou vértice interno. Se cada vértice interno de
uma árvore enraizada tem m filhos, a árvore T é chamada de árvore m-ária. Se m = 2, a árvore T é dita
uma árvore binária e se m = 3, T é uma árvore ternária.
A altura de um vértice v é o número de vértices no maior caminho de v até um de seus descendentes.
Assim, as folhas, por definição, têm altura igual a 1. A altura de uma árvore T é igual ao máximo nı́vel
de seus vértices. Representa-se a altura de T por h(T ) e a altura da subárvore de raiz v por h(v).
Uma árvore ordenada é aquela na qual os filhos de cada vértice estão ordenados. Assume-se a ordenação
da esquerda para a direita. Desse modo, a árvore da Figura 3 é ordenada. Entretanto, o mesmo não ocorre
com a árvore da Figura 5.
Figura 5. Árvore não ordenada
5. Diferentes Caracterizações das árvores
As árvores têm muitas caracterizações equivalentes. Apresentaremos aqui 3(três) delas.
5.1. Primeira caracterização de árvores.
Definição 5.1.1. Um grafo conexo e sem ciclos (acı́clico) é dito uma árvore e será indicado por T = (V, E)
(quando for preciso fazer referência aos respectivos conjuntos de vértices e arestas) ou simplesmente por
T , uma referência do inglês ”tree”
Uma excelente caracterização para uma árvore é que é um grafo tal que a adição de qualquer aresta
à árvore forma um único ciclo, e a retirada de qualquer aresta resulta em um grafo desconexo com duas
componentes conexas: uma componente que inclui um dos vértices extremidade da aresta retirada e a
outra componente conexa que inclui o outro vértice extremidade da aresta retirada.
10
PAULO JORGE M. TEXEIRA
Definição 5.1.2. Um grafo sem ciclos é dito uma floresta. Assim, uma árvore é uma floresta com um
único grafo conexo: ela mesma. E cada componente conexa de uma floresta é uma árvore.
A seguir, apresentamos alguns resultados derivados dessa primeira caracterização das árvores.
Teorema 5.1.3. Um grafo T é uma árvore se e somente se todo par de vértices de T é unido por um
único caminho.
Prova:
Seja T uma árvore.
Suponha, por contradição, que existem dois caminhos distintos P1 e P2 entre os vértices v e w de T .
Como os caminhos são distintos, existem vértices t1 e t2 tais que as seções de P1 e P2 entre t1 e t2 são
totalmente disjuntas. Logo, considerando a união dessas seções (P1 (t1 − t2 ) ∪ P2 (t1 − t2 )), temos um ciclo.
Isso é uma contradição! Logo, se T é uma árvore, para todo par de vértices de T existe um único caminho
entre eles.
P1
v
P1
w
v
w
t1
P2
P2
t2
Figura 6
Suponha agora que para todo par de vértices de T existe um único caminho entre eles. Logo, T é conexo.
Falta então, agora, mostrar que T é grafo acı́clico. Suponha que T é cı́clico, ou seja, que T contém algum
b
ciclo C.
u
v
C
Figura 7
b Então, C
b − (u, v) é um caminho em T entre u e v, contradizendo
Seja e = (u, v) uma aresta no ciclo C.
a hipótese de que o caminho era único. Portanto, T é conexo e acı́clico e então, por definição, T é uma
árvore.
Teorema 5.1.4. Seja T = (V, E) uma árvore tal que |V | = n, |E| = m. Então, m = n − 1.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
11
Prova:
Seja T = (V, E) tal que |V | = n, |E| = m. Vamos fazer a prova por indução no número de vértices de T .
Para n = 1, temos que: m = 0 = n−1 = 1−1. Verdadeira para n = 1. Suponha como hipótese de indução
que o resultado é válido para toda árvore com menos do que n vértices, e para n > 1. Então, T possui pelo
menos uma aresta e = {v, w}. Se removermos a aresta e de T teremos duas componentes conexas T1 e T2 ,
sendo ambas árvores e o grafo T com menos de n vértices. Seja |V (t1 )| = n1 ; |E(t1 )| = m1 ; |V (t2 )| = n2
; |E(t2 )| = m2 Logo, a hipótese de indução vale para T1 e para T2 , ou seja: m1 = n1 − 1 e m2 = n2 − 1.
Mas, |V (t)| = n = (|V (t1 )| = n1 ) + (|V (t2 )| = n2 ) = n1 + n2 |E(t)| = m = |E(t1 )| + |E(t2 )| + 1 =
n1 − 1 + n2 − 1 + 1 = n1 + n2 − 1 = n − 1. Então, o resultado vale para toda árvore com n elementos,
n > 1.
Lema 5.1.5. Seja T = (V, E) uma árvore. As afirmações seguintes são equivalentes:
1. T é uma árvore.
2. T é conexo e |E| é mı́nima.
3. T é acı́clico e |E| = |V | − 1.
4. T é conexo e |E| = |V | − 1.
5. T é acı́clico e para todo v, w ∈ V , a adição de uma aresta v,w produz um grafo contendo exatamente
um ciclo.
6. T é conexo e para toda aresta e = {u, w} em E, o grafo G1 = G − {{u, w}} é desconexo.
7. Para quaisquer vértices u e w em V , o caminho de u a w é único.
Prova:
1 =⇒ 2: Se T é árvore, T é conexo e acı́clico, e o número mı́nimo de arestas é n − 1, pois, caso
contrário, T seria desconexo (um caminho é o grafo conexo com o menor número de arestas e,
sendo o número de vértices igual a n, há n − 1 arestas nesse caminho);
2 =⇒ 3: Como T é conexo e |E| é mı́nima, T é acı́clico, pois a existência de qualquer ciclo implica
que |E| não seja mı́nima. A retirada de uma aresta e = u, w de T implica que T1 = T − {{u, w}}
é grafo desconexo com duas componentes conexas, pois, caso contrário, a inclusão da aresta em
T formaria um ciclo. Procedendo à retirada das arestas de T , uma a uma, terı́amos, ao final, a
formação de n componentes conexas (o máximo possı́vel) com a retirada de n − 1 arestas. Assim:
m = |E| = |V | − 1;
3 =⇒ 4:
Suponha que T é acı́clico e m = |E| = n − 1. Suponha, por absurdo, que T é
desconexo. Logo, T no mı́nimo tem duas componentes conexas C1 e C2 . Sejam os vértices u e w,
respectivamente, de C1 e C2 . A inclusão da aresta e = u, w à T não cria um ciclo e torna T conexo.
Se T tem k componentes conexas, inclui-se k − 1 arestas como visto antes, e, daı́, T é conexo. Nesse
caso, o total de arestas será m = n − 1 + (k − 1) o que é absurdo, pois por hipótese, m = n − 1.
Logo, T é conexo e m = n − 1;
4 =⇒ 5:
12
PAULO JORGE M. TEXEIRA
(a) Suponha que T é conexo e m = |E| = n − 1. Suponha, por absurdo, que C1 e C2 são ciclos
em T . Ao retirar duas arestas, uma de cada ciclo, T continuará conexo e m = n − 1 − 2 6 n − 1.
Contradição, pois m é mı́nima. Logo, T é acı́clico;
(b) Seja e = u, w uma aresta a ser adicionada a T . Como T é conexo, havia um caminho entre
os vértices u e w e a inclusão da aresta e = u, w cria um ciclo em T . Como T é acı́clico (parte (a)),
esse ciclo criado é único;
5 =⇒ 6: (a) A primeira parte vem de 3 4. Logo, para todo apr de vértices u e w de V , há um
único caminho entre u e w. A retirada de qualquer aresta {v, t} no caminho entre dois quaisquer
vértices u e w, desconecta o grafo T , ou seja, T − {{v, t}} é desconexo;
6 =⇒ 7: Suponha que dois quaisquer vértices u e w de T estejam unidos por mais de um caminho
em T . Assim, a retirada de qualquer aresta de um dos caminhos entre u e w não torna o grafo
desconexo, o que contraria a hipótese. Logo, o caminho entre dois vértices quaisquer em T é único;
7 =⇒1: Suponha que para todo par de vértices u e w em V , o caminho entre u e v é único. Logo,
por definição, T é conexo. Como o caminho entre u e v é único, não há um ciclo contendo u e w
em T . Logo, T é acı́clico. Daı́ T é árvore, por definição.
Teorema 5.1.6. (do aperto de mãos) Seja G = (V, E) grafo tal que |V | = n e |E| = m. Então
X
d(v) = 2m.
v∈V
Prova: cada aresta (v, w) contribui com 2(duas) unidades para a soma dos graus dos vértices (uma
unidade para d(v) e uma unidade para d(w)). Logo, a soma total é duas vezes o número de arestas.
Observação: Esse teorema é também válido para multigrafos.
Corolário 5.1.7. Em qualquer grafo G, a soma dos graus de seus vértices é par.
X
Prova: É imediato, pois
d(v) = 2m, e 2m é par.
v∈V
Corolário 5.1.8. Em qualquer grafo G = (V, E), o número de vértices de grau ı́mpar é par.
Prova: Sejam VP = {v ∈ V / d(v) é par} e VI = {v ∈ V / d(v) é ı́mpar}. É claro que V = VP ∪ VI e
X
X
X
X
d(v) = 2m Logo, o número de parcelas
d(v) +
d(v) =
d(v) =
VP ∩ VI = φ. Além disso:
v∈VP ∪VI
v∈V
v∈Vp
v∈VI
de grau ı́mpar (ou o número de vértices de grau ı́mpar) é par.
X
Lema 5.1.9. Em uma árvore T = (V, E),
d(v) = 2m = 2n − 1 , onde n = |V |.
v∈V
Prova: Imediato, pois qualquer aresta u, w de um grafo tem o grau de seus vértices extremidades u
e w contados duas vezes: uma com os vizinhos de u e outra com os vizinhos de w, e pelo Lema 5.1.5,
m = n − 1.
Definição 5.1.10. Seja T = (V, E) uma árvore. Um vértice v de T é dito uma folha se d(v) = 1.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
13
Teorema 5.1.11. Toda árvore não trivial, ou seja, |V (T )| > 2 tem pelo menos duas folhas.
Prova: Todo grafo conexo com pelo menos dois vértices tem uma aresta. Considere um caminho
maximal em uma árvore. Os vértices extremos desse caminho são necessariamente de grau 1 (pois se não
fossem de grau 1, o caminho poderia ser prolongado e então não mais seria um caminho maximal). Logo,
os vértices extremos desse caminho são duas folhas de T .
Lema 5.1.12. Seja T = (V, E) uma árvore com n vértices e v uma folha de T . Então, T − v é uma árvore
com exatamente n − 1 vértices.
Prova: Seja v uma folha de T e T1 = T − v. Sejam u e w ∈ V (T ), u 6= v, w 6= v e P um caminho
entre u e w. É claro que v não está em P . Logo, P é também um caminho em T1 . Logo T1 é conexo. A
remoção do vértice v não cria ciclos em T1 . Logo, T1 é uma árvore com n − 1 vértices.
Definição 5.1.13. O centro de uma árvore é definido como C(T ) = {v ∈ V (T )/ e(v) é mı́nima}.
Essa é uma particular definição do centro de um grafo, como anteriormente já visto.
Teorema 5.1.14 (Jordan 1869). O centro de uma árvore T tem exatamente um vértice ou exatamente
dois vértices adjacentes entre si.
Prova: Vamos fazer a prova por indução no número de vértices de T . Se |V (T )| = 1, então C(T ) = v
e, assim: |C(T )| = 1. Se |V (T )| = 2, então V (T ) = u, v e, assim: |C(T )| = 2.
Logo, a proposição é verdadeira para n = 1 e para n = 2.
Suponha, então, o resultado verdadeiro para toda árvore com menos do que n vértices, sendo n > 2.
Seja T qualquer árvore com n vértices. Seja F = {vV (T )/d(v) = 1}, ou seja: F é o conjunto das folhas
de T . Seja T1 = T − F .
Pelo Lema 5.1.9, T1 é uma árvore com menos do que n vértices (logo, a hipótese de indução se aplica a
T1 ).
Observe que para todo vértice u ∈ V (T ), o vértice que está a uma distância máxima de u é necessariamente uma folha, pois T é grafo conexo. Logo, os vértices de excentricidade máxima são as folhas e,
então,C(T ) ∩ F = φ.
Como todas as folhas foram removidas de T e nenhum caminho entre dois vértices interiores de T passam
por folhas, temos que eT1 (u) = eT (u) − 1. Ou seja, os vértices de excentricida de mı́nima em T1 são iguais
aos vértices de excentricidade mı́nima de T . Temos, então, que: C(T ) = C(T1 ) e, logo, vale o resultado
para T , n > 1.
Definição 5.1.15. Dada uma árvore T = (V, E), uma raiz de T é qualquer vértice v de T escolhido e
chamado, a partir da escolha, de raiz. A árvore T passa a ser dita, então, uma árvore enraizada.
Definição 5.1.16. Seja G = (V, E) um grafo. Uma aresta e ∈ E é dita uma ponte, ou uma aresta de
corte, se ω(G − e) > ω(G). Se G é conexo, dizemos apenas que e é uma aresta cuja remoção desconecta o
grafo G.
14
PAULO JORGE M. TEXEIRA
r
Figura 8
Exemplo 5.1.16.1.
e
u
v
removendo
a aresta
e
G
w(G) = 2
w(G - e) = 3
Figura 9
Teorema 5.1.17. Uma aresta e é uma ponte de G se e somente se não existir ciclo contendo a aresta e.
Prova: Seja e = {v, w} ∈ E(G) uma ponte de G. Logo, ω(G − e) > ω(G) e, além disso, v e w , os
vértices extremos da aresta e estão em componentes conexas distintos. Suponha, por contradição, que
existe um ciclo ω contendo a aresta e. Logo, ω − e é um caminho entre v e w em G − e, contradizendo o
fato de que estavam em componentes conexas distintas.
v
e
w
C-e
Figura 10
Suponha, agora, que não existe um ciclo contendo a aresta e
e que, por contradição, suponha que a aresta e não seja ponte de G. Então, ω(G − e) = ω(G). Entre v
e w em G existe a aresta e. Em G − e deve existir um caminho P entre v e w. Ou seja, P + e é um ciclo
em G. Isso é uma contradição !!! Portanto, e é uma ponte de G.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
v
e
15
w
P
Figura 11
Corolário 5.1.18. Seja G = (V, E) um grafo conexo. T é uma árvore se e somente se cada aresta de T
for uma ponte.
Prova: Suponha que T é uma árvore. Logo, por definição, T é grafo conexo e acı́clico e, portanto, pelo
Teorema 5.1.17, toda aresta de T é uma ponte. Por outro lado, suponha que toda aresta de T é uma
ponte. Daı́, pelo mesmo Teorema, não existe ciclo em T que contenha qualquer aresta de T e então T é
acı́clico e conexo. Portanto,T é uma árvore.
5.2. Segunda caracterização de árvores. Essa caracterização envolve a noção de folhas. Como visto
anteriormente, uma folha de um grafo G é um vértice de grau 1. É claro que toda árvore com mais de um
vértice tem pelo menos dois vértices folhas.
Uma caracterização recursiva de árvores é: Um grafo G (tendo um vértice folha v), com tamanho
n > 1, é uma árvore se e somente se removendo-se a folha v e a única aresta incidente na folha v, o grafo
remanescente é uma árvore de tamanho n − 1.
Os vértices sem filhos de uma árvore T são chamados folhas de T . Todos os outros vértices (com filhos)
são chamados vértices internos de T . Se cada vértice interno de uma árvore enraizada tem m filhos, a
árvore T é chamada de árvore m-ária.
Uma árvore enraizada é uma árvore com um vértice, a raiz, que será distinta dos outros vértices. Duas
árvores enraizadas são consideradas isomorfas se e somente se existe uma bijeção entre elas que preserva
adjacências correspondentes entre as arestas e, a raiz de uma é levada na raiz da outra.
Existem exatamente nn−2 árvores rotuladas com n vértices. Esse resultado, devido à Cayley, é um dos
mais célebres resultados em Teoria dos Grafos. Existem muitas provas para ele, uma delas devido à Prüfer,
que usa um particular código para representar árvores rotuladas, conhecido como Código de Prüfer. Mais
adiante veremos em detalhes como obter esse código e provar esse resultado. Usando a caracterização
recursiva de árvores mencionada acima, é fácil mostrar que é possı́vel determinar a árvore rotulada cujo
código é a seqüência de rótulos fornecida.
5.3. Terceira caracterização de árvores.
Teorema 5.3.1. - Uma árvore com n vértices tem n-1 arestas.
Prova: Considere que a árvore é enraizada (se ela é não direcionada, podemos torná-la enraizada como
descrito anteriormente). Cada vértice, exceto a raiz está na ponta inferior de uma única aresta (a partir
de seu pai). Há, então, n − 1 vértices sem raiz e, portanto, n − 1 arestas.
16
PAULO JORGE M. TEXEIRA
Teorema 5.3.2. Uma árvore m-ária T com k vértices internos tem n = mk + 1 vértices no total.
Prova: Cada vértice interno tem m filhos. Assim há mk filhos mais o vértice não-filho, a raiz. Logo,
há mk + 1 vértices no total.
Corolário 5.3.3. Seja T uma árvore m-ária. Então temos:
(a) Se T tem k vértices internos, ela tem j = (m − 1)k + 1 folhas.
mj − 1
j−1
vértices internos e
vértices no total.
(b) Se T tem j folhas, ele tem k =
m−1
m−1
(m − 1)n + 1
n−1
vértices internos e
folhas.
(c) Se T tem n vértices no total, ela tem
m
m
Prova:
(a) Sabemos que o total de vértices (n) é igual à soma dos vértices internos (k) com as folhas (j). Logo:
j = n − k. Mas n = mk + 1 do Teorema. Daı́: j = n − k = mk + 1 − k = (m − 1)k + 1.
j−1
(b) De (a), tem-se: j = (m − 1)k + 1. Logo, j − 1 = (m − 1)k. Daı́: k =
e como n = j + k , então
m−1
mj − 1
j−1
=
.
n=j+
m−1
m−1
(c) De n = j + k, vem: k = n − j = n − {(m − 1)k + 1} = n − (m − 1)k − 1. Logo: k + (m − 1)k = n − 1.
n−1
Daı́: k(1 + m − 1) = n − 1. Ou seja: k =
.
m
6. Problemas simples envolvendo o estudo das árvores
6.1. Introdução. Nesta seção utilizamos as fórmulas de contagem demonstradas na seção anterior e
aplicamos essas fórmulas em alguns problemas de decomposição. A seguir, mostramos como as árvores
podem ser usadas para decompor e sistematizar a análise de vários problemas de busca. Essas fórmulas
de contagem serão bastante úteis nas seções seguintes, quando da discussão de particularidades sobre as
árvores binárias.
6.2. Problemas simples.
6.2.1. O problema de uma cadeia de telefones.
Suponha que uma cadeia de telefones seja instalada por uma empresa que tenha 100 funcionários. Ela é
ativada por um lı́der que liga para um escolhido grupo de três pessoas. Cada uma dessas três pessoas liga
para grupos escolhidos de três outras pessoas, e assim por diante. Quantas ligações serão feitas ao todo?
Quantas pessoas não terão que fazer nenhuma ligação?
Solução: Tal cadeia telefônica é uma árvore enraizada com 100 vértices. Uma aresta corresponde a
uma ligação. Então, pelo Teorema 5.3.1, haverá 100 − 1 = 99 ligações.
Uma vez que a árvore é ternária (3-ária), do Corolário 5.3.3 parte (c), tem-se que há k =
67 folhas. Isto é, 67 pessoas não farão nenhuma ligação.
(3 − 1)100 − 1
=
3
6.2.2. O problema do torneio de tênis.
Se 56 pessoas se inscrevem para disputar um torneio de tênis, quantas partidas haverá?
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
17
CAMPEÃO
Figura 12. Árvore de um torneio de tênis.
Solução: torneio se desenrola de um modo binário contrário (semelhante a uma árvore) mas a construção
da árvore se faz no sentido contrário: das folhas para a raiz da árvore, como pode ser visto na Figura 7.
Todos os participantes são folhas e as partidas são os vértices internos. Pelo Corolário parte (b), se há
56 − 1
j = 56 folhas e a árvore é binária, então há k =
= 55 partidas a serem disputadas.
2−1
Como visto anteriormente, a altura de uma árvore enraizada é o comprimento do caminho mais longo,
ou, equivalentemente, o maior número de nı́vel indicado para qualquer vértice. Uma árvore enraizada de
altura h é chamada equilibrada se todas as folhas estão nos nı́veis h e h − 1. Árvores equilibradas são
”boas” árvores. A árvore da cadeia de telefones do problema 6.2.1 deveria ser equilibrada de modo a
fazer chegar a mensagem a todos os funcionários o mais rápido possı́vel. Uma árvore de torneio de tênis,
como do problema 6.2.2, deveria ser equilibrada para ser justa; de outra forma, alguns jogadores poderiam
chegar às finais jogando menos partidas que outros jogadores. Na prática, em Torneios do Grand Slam, os
melhores jogadores, segundo um ranking anual, só começam a jogar a partir da segunda rodada, ou seja,
são vértices internos sem terem sido folhas. Tornando-se uma árvore m-ária equilibrada, minimiza-se sua
altura, como veremos a seguir.
Teorema 6.2.3 Considere T uma árvore m-ária de altura h. Então: (a) T tem no máximo mh folhas; (b)
se T tem j folhas, então tem altura h > [log jm ]; (c) se T é uma árvore equilibrada, então h = [log jm ] .
Prova: É claro que uma árvore m-ária de altura igual a l tem m folhas (os filhos da raiz). Agora
vamos usar indução para mostrar que uma árvore m-ária de altura h, tem no máximo, mh folhas. As
folhas de uma árvore m-ária de altura h são apenas as folhas das sub-árvores de m enraizadas nos m filhos
18
PAULO JORGE M. TEXEIRA
da raiz. Estas m sub-árvores têm altura de no máximo h − 1. Por indução, elas têm no máximo mh−1
folhas cada uma ou no máximo m.mh−1 = mh folhas no total. A segunda parte do Teorema, agora segue
imediatamente (basta lembrar que h = [log jm ] implica em que mh−1 < j 6 mh ).
Exercı́cio 6.2.4 Mostre que a soma dos números de nı́vel de todas as j-folhas, numa árvore binária, é
pelo menos j(log2 j) e, portanto, o nı́vel médio de folhas é pelo menos log2 j.
Um dos usos mais comuns da aplicação de árvores é em procedimentos de testagens seqüenciais. Os
dois procedimentos de testagem seqüenciais mostrados a seguir (um deles um problema básico de ciência
da computação e o outro um quebra-cabeça de lógica), ilustram a variedade de tais aplicações de árvores.
6.2.5 - O problema da busca de dicionário
Examinemos o problema do compilador ”busca no dicionário”. Queremos identificar uma palavra desconhecida (número) X testando-a em um ramo de 3 caminhos indicados por: menor que, igual a e maior
que, contra ”palavras” num conjunto (dicionário) ao qual X pertence. O procedimento de teste pode ser
representado por uma árvore binária, ou quase binária. Por exemplo, se X fosse uma das 14 primeiras
letras do alfabeto, então a Figura 8 seria a tal árvore binária de busca. Cada vértice é rotulado com a
letra testada naquele estágio do procedimento. O procedimento começa por testar X contra H. A aresta
à esquerda de um vértice é colocada quando X é menor que a letra e a aresta da direita quando X é
maior. Tal árvore pode ter um vértice interno com apenas um filho se o número de vértices for par. Para
minimizar o número de testes necessários de modo a reconhecer qualquer X, ou seja, minimizar a altura
da árvore de busca, devemos tornar a árvore equilibrada. Suponha que X pertence a um conjunto de n
”palavras”. Qual o número máximo de testes que seriam necessários para reconhecer X?
H
D
B
A
C
L
F
E
G
J
L
K
N
M
Figura 13. Árvore de teste da busca do dicionário.
Solução:
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
19
n+1
(2 − 1)n + 1
=2
folhas.
2
2
Então, o número máximo de testes necessários para reconhecer X é a altura de uma árvore de busca
n+1
n+1
equilibrada de
folhas, ou seja: h = log2
= log2 [(n + 1)] − 1.
2
2
Pelo Corolário 5.3.3, uma árvore binária de busca com n vértices tem
6.2.6 - O Problema do quebra-cabeça
Um quebra-cabeça de lógica, muito conhecido, tem n moedas, sendo uma delas falsa (muito leve ou
muito pesada em relação às outras n − 1 moedas) e uma balança para comparar o peso de quaisquer dois
conjuntos de moedas (a balança pode inclinar-se para a direita, para a esquerda ou ficar equilibrada).
O problema a ser resolvido é: para um dado valor de n, determinar um procedimento para encontrar a
moeda falsa realizando-se um número mı́nimo de pesagens.
Em algumas variações deste problema, o enunciado informa que a moeda falsa é muito pesada ou leve
demais. Se, a priori, sabemos que a moeda falsa é muito leve, quantas pesagens serão necessárias, no
mı́nimo, para um conjunto com n moedas?
Solução:
Nosso procedimento para testagem vai formar uma árvore na qual o primeiro teste é a raiz da árvore.
Os demais outros testes são os outros vértices internos, e as soluções, isto é, qual moeda é falsa, são as
folhas.
Consideremos para a ilustração que será feita (veja a Figura 9), a testagem para oito moedas (numeradas
de 1 a 8), onde a formação da árvore obedecerá:
1 seguir pela aresta da esquerda quando o conjunto de moedas da esquerda, numa testagem, é mais leve;
2. seguir a aresta do meio quando os dois conjuntos de moedas têm o mesmo peso;
3. seguir pela aresta da direita quando o conjunto de moedas da direita é mais leve.
123
1
1
3
2
678
4
3 4
5
5
6
67
8
8
9
Figura 14. Árvore de teste com 8 moedas.
Repare que, por exemplo, quando pesamos as moedas 4 e 5 (e já sabemos que dentre as moedas 1,2,3,6,7,8
não está a moeda leve), a balança não pode ficar equilibrada. A árvore de teste é ternária, e com n moedas
20
PAULO JORGE M. TEXEIRA
haverá n folhas, isto é, n diferentes possibilidades de qual moeda é a falsa. O Teorema 6.2.3 garante que a
árvore de teste deve ter altura maior do log2 n que para conter n folhas. Não é automático que exista um
procedimento de teste que possa alcançar o limite de altura . Para o problema da moeda falsa sendo mais
pesada ou mais leve, este limite pode ser alcançado dividindo-se sucessivamente o subconjunto corrente,
onde se sabe estar a moeda falsa, em três pilhas quase iguais e comparando-se duas das pilhas de mesmo
tamanho.
Se a moeda falsa não pode ser identificada, a priori, como mais leve ou mais pesada, então o problema
seria muito mais difı́cil. Uma determinada moeda irá, geralmente (mas não sempre), aparecer em duas
folhas da árvore de teste: uma vez quando a moeda for mais leve e outra vez quando for mais pesada. A
Figura 9 ilustra o problema comentado.
6.2.6 - O Problema do compilador
Esse problema é um exemplo de construção de árvore de baixo para cima, começando por um conjunto
de folhas.
Ao construir uma tabela de sı́mbolos, um compilador inicialmente lista um grande número de diferentes
nomes de variáveis usados pelo programa (e outros nomes extras gerados pelo compilador). Mais tarde, o
compilador combina repetidamente dois nomes ou dois subconjuntos de nomes que deverão ser atribuı́dos
a um mesmo lugar na memória (em várias sub-seções do programa, nomes diferentes são usados para a
mesma variável). Considerando que um certo nome de variável possa ser submetido em diversas rodadas,
sendo renomeado e combinado com outros nomes, não é eficaz mudar um nome a cada vez que ele é
combinado. Ao invés disso, pode-se construir árvores como é mostrado nas Figuras 10. Se os nomes A
e B são equivalentes e ambos deveriam ser uma variável chamada A, combinamos as folhas A e B em
uma árvore, como mostrado na Figura 10, tomando A como raiz. Se A e B são combinados com o novo
nome A0 e depois A0 é combinado com C, e agora tanto A0 quanto C são equivalentes e agora chamados C,
construı́mos a árvore mostrada na Figura 10. Seguindo para cima até o topo da árvore, pode-se determinar
o nome atual de qualquer nome original. Seja COMB(W ; X; Y ) a operação de combinar os conjuntos de
variáveis atualmente chamadas X e Y em uma variável chamada W. Suponha que iniciamos com nomes
de variáveis A, B, C, D, E, F, G e sucessivamente serão feitas as seguintes operações: COMB(E; E, G),
COMB(B 0 ; B, C), COMB(D0 ; D, F ), COMB(B 0 ; B 0 , E), COMB(A0 ; A0 , B 0 ). Então terı́amos a famı́lia de
árvores mostrada na Figura 10. Por exemplo, a variável originalmente chamada G é agora chamada A0
(como são A, B, C, e E).
7. Resultados teóricos envolvendo o estudo sobre Árvores
7.1. Árvores Geradoras.
Definição 7.1.1. Uma árvore geradora de um grafo G conexo é um subgrafo gerador de G que é uma
árvore. De modo análogo, podemos definir uma floresta geradora. Assim, uma árvore geradora é o subgrafo
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
21
A
A
B
B
(a)
A
B
C
A´
C
A
C
A´
A B
B
B
(b)
A´
A
A
B´
B
C
E
G
A
A
(c)
Figura 15. Procedimentos de um compilador
gerador minimal conexo de um grafo G conexo onde qualquer aresta que seja recolocada na árvore, forma
um ciclo em G.
G
T
Figura 16
Corolário 7.1.2. Todo grafo conexo G possui uma árvore geradora.
Prova: Seja T um subgrafo gerador minimal conexo de G em relação à propriedade de ser conexo e em
relação à quantidade de arestas. Assim, T é conexo por construção. Vamos mostrar que T é acı́clico.
b um ciclo de T , e seja e uma aresta de C.
b Logo, pelo Teorema
Suponha que T não seja acı́clico e seja C
5.1.14, a aresta e não é uma ponte de T .
Logo ω(T − e) = ω(T ). Então, T − e é um subgrafo gerador conexo de G e possui menos arestas do que
o subgrafo T , contradizendo o fato de que T era minimal. Logo, T é acı́clico e conexo, ou seja, T é uma
árvore
22
PAULO JORGE M. TEXEIRA
Corolário 7.1.3. Se G é grafo conexo então m > n − 1, onde |E(G)| = m e |V (G)| = n.
Prova: Seja G um grafo conexo. Então, pelo Corolário 7.1.2, G tem uma árvore geradora T e, portanto,
tem-se que: m = |E(G)| ≥ |E(T )| = |V (T )| − 1 = ∗n − 1. Daı́ m > n − 1. A igualdade ∗ vem da Definição
7.1.1
Teorema 7.1.4. Seja T uma árvore geradora de G e uma aresta c ∈ E(G) − E(T ). Então, T + e contém
exatamente um ciclo.
Prova: Seja T uma árvore geradora de G.Sabemos que é um subgrafo gerador minimal conexo de G e,
portanto, a inclusão de uma aresta c ∈ E(G) − E(T ) gera um ciclo em T e esse ciclo, necessariamente,
contém a aresta e.
v
e
w
C-e
Figura 17
b um ciclo de T + e contendo a aresta e. Temos que C
b − e é um caminho em T entre os extremos
Seja C
da aresta e. Logo, esse caminho é único.
Portanto, o ciclo que contém a aresta e, é único, ou seja, T + e contém exatamente um ciclo.
Definição 7.1.5. Se T é uma árvore geradora de G então T (G) = (V, E(G) − E(T )) é chamado de
co-árvore de G.
Exemplo
G
T
T (G) é co-árvore de G
Figura 18
Teorema 7.1.6. Seja G um grafo conexo, T uma árvore geradora de G e uma aresta e de G. Então:
(i) T (G) não contém cortes de arestas de G;
(ii) T (G) + e contém um único corte de arestas minimal de G, dito um cociclo de G.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
23
Prova:
(i) Uma co-árvore T (G) não pode conter um corte de arestas de G, porque mesmo retirando todas as
arestas de , o grafo G permanece conexo, pois restarão as arestas de T , que é uma árvore geradora de G.
(ii) Seja e uma aresta de T tal que T − e é desconexo. Logo, a aresta e é ponte de T . Sejam S e S
os conjuntos de vértices dos componentes conexos de T − e respectivamente. Assim, como [S, S] é um
corte de arestas de G, por definição, e é minimal. De fato: [S, S] − e não é um corte por (i). Ou seja,
B = [S, S] − e ⊂ T (G) + e. Tome qualquer aresta e0 ∈ B. T − e + e0 é ainda uma árvore geradora mı́nima
de G, Logo, todo corte minimal de G contido em T (G) + e deve incluir essa aresta e. Logo, B é o único
corte minimal de G.
S
S
e
G
e
e
T
T- e
e
T (G)+ e
T (G)- e
Figura 19
[S, S] = T (G) + e.
Observação 7.1.7. Observe que existe uma analogia entre ciclos x árvores e corte minimais x co-árvores,
a saber:
ciclos x árvores
cortes minimais x co-árvores
T não contém ciclos.
T (G) não contém cortes minimais
T + e contém um único ciclo. T (G) + e contém um único corte minimal de G.
Teorema 7.1.8. Em uma árvore T , não trivial, um vértice v ∈ V (T ) é articulação se e somente se v não
é uma folha de T .
Prova: Seja T uma árvore não trivial. Seja v ∈ V (T ) uma articulação. Então existem dois vértices u e
w de T , tal que todo caminho entre os vértices u e w contém o vértice v. Logo, d(v) > 1. Então, v não é
uma folha de T .
Por outro lado, seja v ∈ V (T ) tal que v não é folha de T . Então, d(v) > 1. Logo, existem pelo menos dois
vértices u e w adjacentes ao vértice v e o caminho P : u, v, w em T . Como T é uma árvore, esse caminho
P entre u e w é único. Logo, a retirada do vértice v desconecta a árvore T , ou seja, v é articulação da
árvore T .
24
PAULO JORGE M. TEXEIRA
Corolário 7.1.9. Todo grafo conexo G, não trivial, possui pelo menos dois vértices que não são articulações.
Prova: Seja G um grafo conexo. Pelo Corolário 7.1.2, G possui uma árvore geradora T . E sabemos que
T tem pelo menos duas folhas. Sejam v1 e v2 essas folhas. Pelo Teorema 7.1.8, v1 não é uma articulação.
Logo, ω(T − v1 ) = ω(T ) = 1. Mas T − v1 é uma árvore geradora de G − v1 e ω(G − v1 ) 6 ω(T − v1 ) = 1.
Logo, ω(G − v1 ) = ω(G) = 1, ou seja, v1 não é articulação de G. De maneira análoga, v2 não é articulação
de G. Logo, vale o Corolário.
8. Codificação e Decodificação de Árvores
8.1. Introdução. Neste parágrafo apresentamos conceitos teóricos sobre codificação e decodificação de
árvores. Apresentamos o Código de Prüffer e mostramos sua utilização na codificação e decodificação em
árvores, as formas de armazenamento de árvores na memória do computador e a seguir mostramos como
as árvores podem ser usadas para decompor e sistematizar a análise de vários problemas de busca.
8.2. Os problemas de Geração e Contagem de Grafos.
Como dissemos no Parágrafo 2, o estudo de propriedades dos grafos de forma segmentada por diferentes
famı́lias ganha importância na Teoria dos Grafos e têm proporcionado avanços significativos na solução de
diferentes problemas reais que tomam elementos particulares dessas famı́lias como modelos de estudo.
Diferentes problemas de natureza combinatória são levantados sobre uma particular famı́lia de grafos.
Dentre esses, aqueles que tratam:
I) da contagem do número de elementos da famı́lia, ou seja: o de determinar qual o número total de
grafos distintos de uma famı́lia claramente definida que podem ser construı́dos com um número finito n
de vértices.
De grande importância também para estudos de caráter combinatório é o de verificar dentre todos os
grafos contados numa famı́lia com número finito de elementos quantos são e quantos não são isomorfos
entre si, procurando subdividi-los em subclasses não isomorfas. É claro que, também para famı́lias de
quantidades infinitas de grafos, essa subdivisão em subclasses respeitando-se o isomorfismo é de grande
importância para caracterizar propriedades.
II) o problema de criar condições que permitam (conhecido o número finito de vértices), a geração de
grafos de uma dada famı́lia atendendo às seguintes situações:
a) a geração aleatória uniforme de qualquer grafo da famı́lia com a propriedade de que qualquer grafo da
famı́lia possui igual probabilidade de ser gerado. Desse modo, a geração dos grafos cria uma distribuição
uniforme de elementos;
b) a geração de todos os grafos da famı́lia, um a seguir do outro, de modo único e de forma sistemática
através de uma lei de formação que pode ser única ou não, para todos os elementos, ou seja, enumerando
seus elementos.
Por exemplo, no caso de verificar se duas árvores são ou não isomorfas, o algoritmo que faz tal verificação
tem complexidade O(n) no número n de vértices de cada árvore. De modo similar, a enumeração de árvores
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
25
com um número finito de vértices é bastante simplificada. Igualmente interessantes seriam os problemas
que levantassem a possibilidade de inferir se, na geração (aleatória ou por enumeração) os grafos gerados
estariam ou não livres de serem isomorfos, ou seja, só gerar um novo grafo da famı́lia que não tenha um
grafo isomorfo a ele em alguma sub-famı́lia, caso contrário seria descartado por já conter um representante
com caracterı́sticas idênticas (a menos da rotulação de vértices). Portanto, só seriam considerados os
grafos a menos de isomorfismo.
Exemplos:
1. Seja V = {1, 2, 3, 4} um conjunto de 4 vértices. Vamos avaliar o problema da contagem de árvores em
V.
• Se o isomorfismo não é levado em conta, temos 44−2 = 16 árvores distintas;
• Do contrário, há apenas duas árvores distintas não isomorfas com quatro vértices, conforme indicadas
na figura abaixo.
1
4
1
4
1
4
1
4
2
3
2
3
2
3
2
3
1
4
1
4
1
4
1
4
2
3
2
3
2
3
2
3
1
4
1
4
1
4
1
4
2
3
2
3
2
3
2
3
1
4
1
4
1
4
1
4
2
3
2
3
2
3
2
3
Figura 20. Enumeração das árvores com 4 vértices
2. Consideremos a seguinte questão: quantas árvores há com V = {v1 , v2 , v3 , v4 , v5 } como conjunto de seus
vértices, e quais são elas?
Se o isomorfismo entre essas árvores é irrelevante, há 55−2 = 53 = 125 árvores distintas que se pode
construir com os vértices conhecidos.
Vamos considerar as seguintes sub-classes de árvores com 5 vértices:
• C1 = {árvores que têm um vértice de grau 4 e os demais grau 1}. Há um total de 5 árvores, conforme a
escolha do vértice raiz seja v1 ou v2 ou v3 ou v4 ou v5 .
• C2 = {árvores que têm um vértice de grau 3, um vértice de grau 2 e três vértices de grau 1}. Há um
total de 60 árvores, pois: há 5 modos de escolher um vértice de grau 3, entre os quatro vértices restantes,
26
PAULO JORGE M. TEXEIRA
Figura 21
há C4,3 modos de escolher os três vértices adjacentes ao vértice de grau 3 e, finalmente, há 3 modos de
escolher um desses vértices que terá grau 2. Assim, o total de árvores é: 5.C4,3 .3 = 5.4.3 = 60 árvores,
todas isomorfas entre si.
Figura 22
• C3 = {árvores que têm três vértices de grau 2 e dois vértices de grau 1}. Há um total de 60 árvores,
pois: há 5 modos de escolher um vértice de grau 1 e 4 modos de escolher o outro vértice de grau 1. Como
estes podem trocar de posição entre si, devemos dividir o resultado por 2. Os outros 3 vértices podem
permutar entre si, totalizando P3 modos possı́veis. Assim, o total de árvores é: 5 · 4 · P3 /2 = 5 · 4 · 6/2 = 60
árvores, todas isomorfas entre si.
Figura 23
8.3. Algoritmo de Huffman.
Para analisarmos mais uma aplicação de árvores binárias vamos considerar o problema de codificar uma
mensagem composta de uma seqüência de sı́mbolos de um alfabeto de n sı́mbolos. Esta mensagem será
transformada em uma seqüência de bits, depois que, a cada sı́mbolo, for atribuı́do um código binário e os
códigos dos sı́mbolos da mensagem forem concatenados.
Considere um alfabeto composto de quatro sı́mbolos A, B, C e D, sendo que a cada um dos sı́mbolos foi
atribuı́do o código indicado a seguir:
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
27
Sı́mbolo Código
A
00
B
01
C
10
D
11
A mensagem ABCADCA seria codificada da seguinte maneira: 00011000111000, tendo comprimento
de 14 bits. O objetivo do algoritmo é criar um código que minimize o comprimento da mensagem. Para
criar este código vamos levar em conta a freqüência de cada sı́mbolo na mensagem.
A Tabela a seguir mostra a freqüência de cada sı́mbolo na mensagem:
Sı́mbolo Freqüência
A
3
B
1
C
2
D
1
Desta tabela podemos verificar que se atribuirmos ao sı́mbolo A um código binário mais curto que os
atribuı́dos aos sı́mbolos B e D terı́amos uma mensagem menor. Isto provém do fato que o sı́mbolo A
aparece mais vezes do que os sı́mbolos B e D. Suponha que os seguintes códigos sejam atribuı́dos aos
sı́mbolos:
Sı́mbolo Código
A
0
B
110
C
10
D
111
Usando este código, a mensagem ABCADCA ficaria 0110100111100 que requer 13 bits. Em mensagens
longas com mais sı́mbolos não freqüentes, o ganho pode ser ainda maior. Um dos requerimentos deste
código é que nenhum código seja prefixo de outro, caso a decodificação seja feita da esquerda para direita.
Para decodificar a mensagem vamos começar da esquerda para a direita, caso o primeiro bit seja 0 o
código corresponde ao sı́mbolo A. No caso contrário devemos continuar a examinar os bits restantes. Se
o segundo bit for 0 o sı́mbolo é um C, caso contrário examinamos o terceiro bit. Se o terceiro bit for um
0 indica um B e se for 1 indica o D.
Resumindo, para encontrar o algoritmo ótimo, a partir do código acima, deve-se seguir os seguintes
passos:
1o ) Encontre os dois sı́mbolos que aparecem com menor freqüência, no nosso caso B e D.
2o ) Atribua 0 para B e 1 para D.
28
PAULO JORGE M. TEXEIRA
3o ) Combine estes dois sı́mbolos em um único sı́mbolo BD. Este novo sı́mbolo terá freqüência igual à soma
das freqüências de B e D, no caso 2. Temos agora os seguintes sı́mbolos: A (3), C (2) e BD (2) (os
números entre parênteses são as freqüências).
4o ) Novamente, escolha os sı́mbolos de menor freqüência, que são C e BD.
5o ) Atribua o código 0 ao sı́mbolo C e 1 ao BD. Isto significa adicionar 1 aos códigos de B e D, que
passam a valer 10 e 11, respectivamente.
6o ) Combine os dois sı́mbolos no sı́mbolo único CBD, de freqüência 4. Temos agora dois sı́mbolos: A(3)
e CBD (4).
7o ) Atribua 0 ao sı́mbolo A e 1 ao sı́mbolo CBD. O sı́mbolo ACBD é o único sı́mbolo restante e recebe
o código N U LL de comprimento 0. A Figura 24 mostra a árvore binária que pode ser construı́da a partir
deste exemplo. Cada vértice está representado pelo sı́mbolo e sua respectiva freqüência.
ACBD,7
A,3
CBD,4
C,2
BD,2
B,1
D,1
Figura 24
8.4. Enumeração e busca com Árvores.
8.4.1. Introdução.
Um primeiro trabalho que se utilizou implicitamente de árvores foi feito por Kirchoff em 1847 em
problemas de circuitos elétricos. Cayley foi o primeiro a se utilizar do termo árvore, em 1857, num
trabalho sobre cortes ordenados em árvores, usando funções geradoras.
Os métodos de busca começaram a ser vistos por volta desse ano, mas seu desenvolvimento de modo
sistemático só foi possı́vel ocorrer a alguns anos atrás através do amplo desenvolvimento da Ciência da
Computação. Há muitos bons livros que tratam de busca.
Nesta seção apresentamos rápidas considerações sobre duas abordagens básicas para a enumeração de
árvores e as aplicamos em 3(três) exemplos simples que envolvem jogos ao invés de aplicações em pesquisa
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
29
operacional, uma vez que a maioria dos problemas de enumeração nesta área envolvem árvores muito
grandes e utilizam algoritmos especiais de ”poda”, fugindo dos objetivos deste trabalho.
8.4.2. Enumeração com Árvores.
As árvores fornecem uma estrutura natural para encontrar soluções para problemas que envolvem uma
seqüência (finita) de escolhas. Para encontrar a saı́da de um labirinto, ótimas estratégias em um jogo ou o
menor percurso em um problema de rotas são tais exemplos de usos das árvores. A maioria dos problemas
de isomorfismo, circuitos hamiltonianos, de coloração mı́nima e outros, requerem busca baseada em árvores
para soluções através de programas computacionais.
Se queremos encontrar: uma solução, todas as soluções ou uma solução ótima para um problema, o
primeiro e mais importante desafio é ter certeza de que são checadas todas as maneiras possı́veis de gerar
uma solução, isto é: a enumeração tem que ser completa. Considerando as escolhas seqüenciais
como sendo os vértices internos em uma árvore enraizada e as soluções e os becos sem saı́da como sendo as
folhas (como no problema da pesagem das moedas, visto anteriormente), podemos organizar a enumeração
de possı́veis soluções. As árvores também tornam mais fácil discernir e implementar atalhos, tais como
”podar” subárvores que demonstram não levar a uma solução (ou não levar a uma solução ótima).
8.4.3. Enumeração por backtracking ou por largura.
Há duas abordagens básicas para a enumeração de árvores:
• Primeiramente o método chamado backtracking (também conhecido como de busca em profundidade),
que constrói um caminho da raiz até o mais longe possı́vel na árvore, isto é, até alguma folha. Se a folha
não for uma solução ou se precisamos prosseguir para encontrar todas as outras soluções, seguimos a trilha
de volta um nı́vel até o pai da folha ( a escolha anterior) e depois ramificamos ao longo de uma aresta
diferente construindo um caminho para uma nova folha. No backtracking se todas as arestas do vértice
anterior (escolha) já tiverem sido tentadas, então seguimos a trilha de volta a um nı́vel acima até um
nı́vel mais alto, e assim por diante. No final, este método vai gerar caminhos para todas as folhas, isto é,
enumerar uma árvore inteira de possı́veis seqüências de escolhas. Se precisamos de apenas uma solução, o
método do backtracking vai terminar assim que for encontrada uma folha que seja a solução. Existe uma
dificuldade maior contra a qual precisamos nos resguardar: andar em cı́rculos. Em jogos e em problemas
de rotas do mundo real, geralmente é inevitável que haja dois ou mais caminhos diferentes (seqüências de
escolhas) que levem a uma mesma ”posição”, por exemplo, o mesmo canto num labirinto. Tal redundância
é aceitável. Entretanto, é geralmente ruim visitar duas vezes a mesma posição num mesmo caminho. Isso
poderia levar a um caminho sem fim, que andasse em cı́rculos, dando voltas e voltas através dessa posição,
para sempre. Desta forma, deverı́amos sempre checar se cada posição sucessiva alcançada num caminho
não tenha aparecido, antes, no caminho. Se ela o fez, então trate a posição como uma folha (ou beco sem
saı́da) e refaça o caminho para trás.
• O outro método comum de enumeração com árvores, chamado de busca em largura, é o de determinar
todas as arestas que saem da raiz, isto é, todos os possı́veis filhos da raiz; a seguir deve determinar
todas as arestas que saem desses filhos e, assim por diante. Este procedimento se espalha como um leque
30
PAULO JORGE M. TEXEIRA
uniformemente a partir da raiz. De novo, não haverá um só caminho que repita uma determinada posição
(o retorno ao mesmo vértice). Numa busca em largura, às vezes é possı́vel que caminhos diferentes não
usem um vértice comum. Se a árvore de caminhos possı́veis é grande, então o método de busca em
largura rapidamente se torna difı́cil de controlar por causa de seu tamanho, peso ou forma. O método
do backtracking, que traça somente um caminho de cada vez, é muito mais fácil de usar à mão ou de
programar. Ainda mais nos casos em que precisamos encontrar apenas uma dentre as possı́veis soluções
do problema, vale mais a pena ir seguindo todo o caminho buscando uma solução do que gastar um tempo
longo construindo um grande número de caminhos parciais, em que apenas um deles realmente será usado
no final. Por outro lado, quando queremos uma solução envolvendo um caminho mais curto ou quando
podem haver caminhos com becos sem saı́da muito longos, (enquanto os caminhos de solução tendem a
ser relativamente curtos), o método em largura é, então, melhor de ser utilizado.
Exemplo 8.4.3.1 - Suponha que temos três latas de água, de capacidades 10 litros, 7 litros e 4 litros.
Inicialmente a lata de 10 litros está cheia e as outras duas vazias. Podemos colocar água de uma lata para
outra, derramando até a lata que recebe estar cheia (sem entornar) e a lata que transborda estar vazia.
Existe uma maneira de derramar a água entre latas para obter exatamente 2 litros nas latas de 7 ou 4
litros? Se há, encontre uma seqüência mı́nima de derramamentos para obter dois litros.
As posições, ou vértices, neste problema de enumeração são ternos ordenados (a, b, c), ou seja: as
quantidades de água nas três latas em ordem decrescente de suas capacidades. Na verdade, é suficiente
gravar apenas as quantidades dos pares ordenados (b, c), ou seja, as quantidades das latas de 7 e de 4
litros, uma vez que temos sempre a igualdade a = 10 − b − c. Uma aresta direcionada corresponde ao
derramamento de água de uma lata para uma outra. Vamos desenhar a árvore de dois modos: numa rede
de coordenadas b no sentido horizontal e c no sentido vertical e do modo usual com sua raiz sendo indicada
como mostrado na Figura 12. A rede é limitada por b = 7, c = 4 e b + c = 10. O derramamento entre as
latas de 10 e de 7 litros será uma aresta horizontal, entre 10 e 4 litros será uma aresta vertical, e entre 7
e 4 litros uma aresta diagonal com inclinação de −45 e +135 graus.
A raiz dessa árvore de busca é (0, 0). Partindo da raiz, podemos alcançar as posições (7, 0) e (0, 4). De
(7, 0), podemos chegar a novas posições (7, 3) e (3, 4) e de (0, 4) podemos chegar a novas posições (6, 4) e
(4, 0). De (7, 3), a única nova posição é (0, 3), e de (3, 4) a única nova posição é (3, 0). De (6, 4) a única
nova posição é (6, 0) e de (4, 0) a única nova posição é (4, 4). Agora já percorremos todos os caminhos de
comprimento 3. Agora, os únicos novos movimentos são: de (4, 4) a (7, 1) e de (6, 0) a (2, 4). Mas (2, 4)
tem dois litros em uma lata. Então, (0, 0) a (0, 4) a (6, 4) a (6, 0) a (2, 4) é uma seqüência mı́nima de
derramamentos para obter dois litros. É interessante reparar que soluções possı́veis não corresponderam
apenas a folhas na árvore de enumeração.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
[0,4]
[2,4]
[3,4]
[4,4]
31
[6,4]
4
3
[7,3]
[0,3]
2
1
[7,1]
0
[3,0]
0
1
2
3
[4,0]
4
5
[6,0]
6
[7,0]
7
Figura 25
[0,0]
[7,0]
[0,4]
[7,3]
[3,4]
[6,4]
[4,0]
[0,3]
[3,0]
[6,0]
[4,4]
[2,4]
[7,1]
Figura 26. Árvore para o exemplo 2.6.2.2.1
Exemplo 8.4.3.2 - Três esposas ciumentas e seus respectivos maridos chegam a um rio. O grupo tem
que atravessar o rio (da margem próxima à margem distante) num barco que pode levar no máximo duas
pessoas. Encontre uma seqüência de viagens de barco que levarão as seis pessoas ao outro lado do rio, sem
jamais deixar qualquer marido sozinho (sem sua respectiva esposa) na presença de outra esposa. Sejam
as esposas representadas pelas letras A, B e C, e seus respectivos maridos por a, b e c. Vamos assinalar
uma posição com os nomes das pessoas na margem próxima acompanhado de um asterisco (*), se o barco
estiver na margem próxima. Uma aresta é rotulada com a direção do barco e as pessoas no barco. A
cada posição, precisamos checar se as pessoas no barco não violarão a condição ”ciumenta”, removendo
uma esposa sem seu marido (deixando-o com outra esposa) ou colocando um marido desacompanhado,
em contato com outra esposa ou vice-versa. A Figura 13 mostra a árvore de posições viáveis (repare que
não há becos sem saı́da).
Na verdade, há outros caminhos similares possı́veis. Por exemplo, poderı́amos começar com Bb ou Cc
ao invés de Aa, ou começar com ac ou bc ao invés de ab, e assim por diante.
32
PAULO JORGE M. TEXEIRA
*ABCabc
ab
Aa
BCbc
ABCc
A
b
bc *ABCbc
ABC
a
ABCa
BC
Aa
Bb
Abab
AB
ab
c
bc
b
*abc
a
A
ab*
*Aa
ab
Aa
Figura 27
Exemplo 8.4.3.3 - Encontre todas as maneiras de colocar oito rainhas em posições de tal modo que
uma não ”capture” a outra, num tabuleiro de xadrez 8x8. (É bom lembrar que uma rainha pode capturar
outra rainha se ambas estiverem na mesma fileira (linha horizontal) ou na mesma coluna ou numa diagonal
comum).
Vamos apresentar um algoritmo usando enumeração de árvores de backtracking para listar todas as
soluções de posicionamento das oito rainhas em posições que uma não ”capture” a outra. Tentaremos
todas as maneiras de posicionar as rainhas sucessivamente na coluna 1, coluna 2, e assim por diante, até
a coluna 8. Seja ak a fileira da rainha na coluna k.
Para cada i, 1 6 i < k, é necessário que ak 6= ai e |ak − ai | =
6 k − i. Quando essas condições se mantêm
para ak , dizemos que” ak é compatı́vel com a1 , a2 , · · · , ak−1 ”. Quando um ak compatı́vel é encontrado,
descemos na árvore até o próximo nı́vel (próxima coluna). Quando nenhum ak compatı́vel é encontrado,
fazemos backtrack e tentamos o próximo maior valor (fila) para ak − 1. O algoritmo pode então ser
escrito como a seguir:
k ←− 1; a1 ←− 1;
DESCER: k ←− k + 1; ak ←− 1;
ADICIONAR RAINHA: enquanto ak 6 8 e ak não for compatı́vel com a1 , a2 , · · · , ak−1
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
33
faça ak ←− ak + 1;
se ak = 9 então
se k > 1 então faça backtrack ou vá para o FIM ;
se k < 8 então vá para DESCER;
imprima solução a1 , a2 , · · · , a8 ;
BACKTRACK: k ←− k − 1; ak ←− ak + 1; vá para ADICIONAR RAINHA;
FIM: PARE;
Se ak = 9, então não houve nenhum novo ak compatı́vel com a1 , a2 , · · · , ak−1 encontrado no procedimento
enquanto e precisamos realizar backtrack (ou se m, a busca está terminada).
Muito embora não seja objeto deste trabalho, enfatizamos que todos os algoritmos de otimização de
rede usam buscas em largura. Há 3(três) algoritmos de otimização que implicitamente utilizam árvores
para a busca através de grafos.
8.5. O CÓDIGO DE PRÜFER.
8.5.1. Introdução. A idéia de associar um código a grafos rotulados pertencentes a uma especı́fica famı́lia
já vem de 1918, com Prüfer. Ele provou a correspondência biunı́voca entre o conjunto de (n − 2) uplas de
inteiros {1, 2, ..., n} e o conjunto de todas as árvores rotuladas com n vértices. Um código deve representar
de maneira unı́voca um determinado grafo da famı́lia considerada e, reciprocamente, a cada grafo da
famı́lia deve ser atribuı́do um único código.
Uma vantagem que se apresenta com a codificação de um grafo é a possibilidade de uma representação
em memória mais compacta. Outra, é a solução mais eficiente de problemas algorı́tmicos.
Além disso, problemas clássicos combinatórios tais como: contagem de elementos, enumeração e geração
aleatória, são mais facilmente solucionados com o auxı́lio de um esquema de codificação. Seja T = (V, E)
uma árvore com |V | = n vértices, n > 2, em que seus vértices são rotulados de 1 a n.
O Código de Prüfer
O Código de Prüfer de T é uma seqüência com n-2
rótulos, construída com a sucessiva remoção da
folha de menor rótulo da árvore e a imediata
inclusão do rótulo de seu vértice adjacente ao
código. Esse processo de remoção de folhas é
interrompido quando restam duas folhas na árvore
e o código é, então, concluído.
Exemplo de construção do código de Prüfer:.
34
PAULO JORGE M. TEXEIRA
3
1
6
3
7
5
1
4
2
Passo 1: código: <>
Folhas: {2,5,6}
6
7
5
1
4
Passo 2: código: <4>
Folhas: {4,5,6}
3
1
3
6
1
5
Passo 3: código: <4,7>
Folhas: {5,6,7}
3
7
7
3
7
7
6
Passo 4: código: <4,7,1>
Folhas: {6,7}
Passo 5: código: <4,7,1,1>
Folhas: {1,7}
Passo 6: código: <4,7,1,1,3>
Folhas: {3,7}
Figura 28. Um exemplo de codificação de Prüfer .
A figura acima mostra um exemplo de como é obtido o código h4, 7, 1, 1, 3i para a primeira árvore.
Inicia-se com a árvore a ser codificada e com a (n − 2)-upla vazia. Como a árvore possui 7 vértices, o
código terá 5 posições ocupadas. Remove-se a folha de menor rótulo (vértice de rótulo 2) e adiciona-se
o rótulo de seu vizinho ao código, que é o 4, obtendo o código de Prüfer inicial e parcial h4i e exibi-se a
árvore a seguir, tendo retirado o vértice de rótulo 2 e sua aresta. Agora remove-se o vértice de rótulo 4
que é a folha de menor rótulo e adiciona-se ao código o rótulo 7, que é o rótulo de seu vizinho. Obtém-se
o código de Prüfer parcial h4, 7i e a terceira árvore. A seguir, são removidos os vértices de rótulos 5 e 6,
obtendo o código de Prüfer parcial h4, 7, 1, 1i e a quarta árvore. O vértice de rótulo 1 só passa a ser folha
após a remoção do vértice de rótulo 6. Finalmente, remove-se o vértice de rótulo 1, obtendo-se o código
de Prüfer h4, 7, 1, 1, 3i.
Observação 8.5.1. Para que a codificação de Prüfer se aplique em árvores enraizadas, basta estabelecer
que o vértice raiz não seja removido mesmo que em algum passo ele se torne folha.
Exemplo 8.5.2. Construção do código de Prüfer em uma árvore enraizada
Suponha a árvore a seguir está enraizada no vértice 5. A codificação ocorre da mesma forma que no
exemplo anterior, exceto o último passo, onde o rótulo 5 é acrescentado ao final do código gerado. O
vértice raiz jamais é removido, mesmo sendo folha, como no Passo 3. Assim, o Código de Prüfer para
árvores enraizadas é composto por (n − 1) rótulos de vértices, ou seja, um rótulo a mais que a codificação
das árvores sem raiz. Esse rótulo a mais é justamente a raiz da árvore, e ocupa a última posição do código.
A figura a seguir mostra passo a passo como o código h4, 7, 1, 1, 3, 5i é obtido.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
3
1
6
3
7
5
1
4
2
Passo 1: código: <>
Folhas: {2,6}
6
1
3
7
5
1
4
Passo 2: código: <4>
Folhas: {4,6}
3
35
6
7
5
Passo 3: código: <4,7>
Folhas: {6,7}
3
7
1
5
5
Passo 4: código: <4,7, 1>
Folhas: {7}
1
Passo 5: código: <4,7,1,3>
Folhas: {3}
5
Passo 6: código: <4,7,1,3,1>
Folhas: {1}
Passo 7: código <4, 7,1,3,1,5>
Figura 29. Um exemplo de codificação de Prüfer para uma árvore enraizada .
Observação 8.5.3. Sejam duas árvores T = (V, E) e T1 = (V, E) que possuem o mesmo conjunto de
vértices e arestas, sendo a primeira sem raiz e a segunda enraizada no vértice de rótulo n. Nesses casos, o
Código de Prüfer da primeira é dito um prefixo do Código de Prüfer da segunda. Nos exemplos anteriores,
o código de Prüfer h4, 7, 1, 1, 3i é um prefixo do código de Prüfer h4, 7, 1, 1, 3, 5i.
Observação 8.5.4. São conhecidos, na literatura, outros quatro esquemas de codificação para árvores
rotuladas e todos eles baseiam-se em remoções sucessivas de folhas, registrando no código gerado o rótulo
do vértice vizinho à folha removida.
Os três primeiros devidos à Neville e o quarto devido à Deo e Micikevicius:
1) Um vértice qualquer é eleito como raiz da árvore e jamais é removido ao longo do processo, ainda
que se torne folha. Quando o vértice escolhido como raiz é o de maior rótulo, o código obtido é idêntico
ao de Prüfer;
2) Um vértice qualquer é eleito como raiz da árvore e jamais é removido ao longo do processo, ainda que
se torne folha. Esse método opera em k iterações, onde k é o raio da árvore. A cada iteração, as folhas
são removidas em ordem crescente de rótulo, até que restem apenas dois vértices e uma aresta na árvore.
Este esquema permite deduzir o diâmetro de uma árvore diretamente a partir de seu código.
3) Um vértice qualquer é eleito como raiz da árvore e jamais é removido ao longo do processo, ainda
que se torne folha. Esse método remove, inicialmente, a folha de menor rótulo. Se o único vértice a ela
adjacente torna-se folha, ele será o próximo a ser removido; do contrário, a folha com segundo menor
rótulo é removida. O processo é repetido até que restem apenas dois vértices e uma aresta na árvore.
4) Deo e Micikevicius propuseram um esquema de codificação que utiliza uma fila. Inicialmente, inseremse todas as folhas da árvore na fila, em ordem crescente de rótulos. A cada passo, remove-se um vértice
da fila, registra-se o rótulo de seu vizinho no código e, se este se torna uma folha, ele é inserido na fila.
Para cada um destes esquemas é preciso que existam algoritmos de codificação e decodificação.
Caminiti et al. apresentaram uma abordagem unificada para os métodos mencionados, permitindo a
codificação e a decodificação em tempo linear.
36
PAULO JORGE M. TEXEIRA
8.5.4 - Algoritmo que obtém o código de Prüfer para uma árvore T = (V, E)
O primeiro problema algorı́tmico a ser observado ao se tratar de códigos é o desenvolvimento de algoritmos que tratem da codificação e decodificação. A seguir apresentamos um algoritmo para a obtenção
do Código de Prüfer:
Algoritmo Gera− Código− Prüfer;
Entrada: Árvore T = (V, E), com #(V ) ≥ 2;
Saı́da: Lista Código com a codificação de Prüfer;
Inı́cio Código = ∅;
Folhas = {v ∈ V /grau(v) = 1};
Enquanto #(V ) ≥ 2 faça
Encontre v Folhas com rótulo mı́nimo; (∗)
Seja u o único vértice adjacente a v;
Remova v de V e a aresta {v, u} de E; (∗∗)
Adicione rótulo (u) ao fim da lista Código;
Se grau (u) = 1 então Folhas =Folhas ∪ (u);
Fim
Ao final do algoritmo, a lista Código contém uma seqüência com n − 2 rótulos, que é o código de Prüfer
para a árvore T = (V, E). Com o algoritmo acima e as considerações iniciais o Lema 8.5.5, a seguir, é
imediato.
Lema 8.5.5. Seja T = (V, E) uma árvore e d(v) o grau do vértice v ∈ V . O rótulo do vértice v ocorre
d(v) − 1 vezes no Código de Prüfer de T .
Prova: Toda vez que uma folha é removida de uma árvore T = (V, E) durante o processo de codificação
de Prüfer, o rótulo do vértice vizinho à folha é inserido no código que está sendo construı́do. Assim, o
rótulo de uma folha nunca figura no código e os rótulos dos outros vértices vizinhos aos vértices folhas são
inseridos cada vez que uma folha vizinha a eles é removida. Mas, como o grau de um vértice é o número
de vizinhos desse vértice, até que ele se torne folha (pela remoção de folhas vizinhas a ele), ele terá seu
rótulo sendo inserido no código e, portanto, o rótulo de um vértice v aparecerá d(v) − 1 vezes no Código
de Prüfer.
8.5.6 - Algoritmo que obtém a árvore T = (V, E) para um dado Código de Prüfer
O algoritmo a seguir mostra como construir uma árvore a partir do seu Código de Prüfer. Este procedimento é chamado de DECODIFICAÇÃO da árvore.
Seja t o tamanho da seqüência armazenada em Código. Como o Código de Prüfer é formado por n − 2
rótulos de vértices, tem-se que n − 2 = t. Logo: n = t + 2 e, assume-se então que V = {1, 2, · · · , t + 2}.
(Desta forma, sem perda de generalidade, identificam-se os vértices e seus rótulos).
Na fase de codificação, os rótulos das folhas da árvore nunca são inseridos. Assim, o conjunto das folhas
da árvore é facilmente encontrado por: Folhas = V −Código. Inicia-se a decodificação com o conjunto de
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
37
arestas E vazio e constrói-se a árvore pela adição sucessiva de arestas do tipo {u, v}, obtidas seguindo os
seguintes procedimentos:
1. Escolhe-se a folha v que possui o menor rótulo no conjunto Folhas;
(o vértice v é vizinho do vértice cujo rótulo correspondente é aquele indicado na primeira posição do
Código. Chamemos esse vértice de u).
2. Remove-se a folha v do conjunto Folhas e o vértice u da lista Código para o conjunto Folhas, caso seu
rótulo não apareça mais na lista Código; (Isto indica que, para a seqüência que sobrou, este vértice é uma
folha e, portanto, não deve figurar mais na lista Código. Caso o rótulo deste vértice ainda apareça na lista
Código, é porque seu grau é maior do que ou igual a 3 e, portanto, ainda deve figurar na lista Código, de
modo que, ao menos um vértice folha vizinho a ele ainda seja retirado do conjunto Folhas).
3. Assim, se o rótulo do vértice u não aparece mais na lista Código, o vértice u é então inserido em Folhas.
4. Após todos os rótulos da lista Código serem comparados e, a seguir, removidos, insere-se a última aresta
que é adjacente aos dois últimos vértices folha ainda não comparados.
Algoritmo Decodifica− Codigo− Prufer;
Entrada: Lista Codigo com o codigo de Prufer;
Saida: Arvore T = (V, E);
Inicio
T =tamanho da lista Codigo;
V = {1, 2, ....., t + 2};
E = ∅;
Folhas = V − Codigo;
Enquanto Codigo 6= ∅ faça
Retire primeiro elemento u da lista Codigo;
Encontre v ∈ Folhas com rotulo minimo:
Folhas = Folhas −{v};
E = E ∪ {{u, v}};
Se u ∈ Código, então Folhas = Folhas ∪{u};
Seja Folhas = {u, v};
E = E ∪ {{u, v}};
Fim
Com o algoritmo acima e as considerações anteriores, o Corolário 8.5.6, a seguir, é imediato:
Corolário 8.5.6. Seja T = (V, E) uma árvore e um vértice v ∈ V . Se o rótulo de v não é incluı́do no
código de Prüfer de T , então v é um vértice folha.
Prova:
Suponha que o rótulo de um vértice v não aparece no Código de Prüfer, ou seja, aparece 0 (zero) vezes.
Plo Lema 8.5.5, o número de vezes em que o rótulo de um vértice figura no código é dado por d(v) − 1.
Logo, d(v) − 1 = 0, e então: d(v) = 1. Portanto, por definição, o vértice v é um vértice folha.
38
PAULO JORGE M. TEXEIRA
9. CONTAGEM E GERAÇÃO DE ÁRVORES
Uma aplicação extremamente importante e necessária da Codificação de Prüfer é aquela que permite
determinar o total de árvores geradoras de um grafo, conhecendo-se seu número de vértices. Outra
aplicação, igualmente e também importante, é a possibilidade de gerar essas árvores aleatoriamente (a
geração de uma árvore é equivalente à geração de um novo Código de Prüfer), não só para árvores quaisquer
como também para árvores que possuam determinadas restrições especı́ficas a serem consideradas (algumas
dessas caracterı́sticas serão aqui abordadas através de teoremas adiante apresentados). A seguir vamos
analisar como é possı́vel contar o total de árvores e gerá-las aleatoriamente, com essas árvores tendo ou
não restrições especı́ficas.
9.1. Árvores sem restrições.
Denotemos por T (n) a quantidade de árvores distintas com n > 2 vértices rotulados de 1 a n. A fórmula
T (n) = nn−2 é conhecida e atribuı́da a Cayley (1889).
Teorema 9.1.1. T (n) = nn−2 .
Prova:
Como demonstrado por Prüfer em 1918, existe uma relação biunı́voca entre o conjunto de todas as
árvores com vértices cujos rótulos estão no conjunto dos inteiros {1, 2, · · · , n} e o conjunto de todas as
(n − 2)-uplas formadas por esses inteiros. Como há n possibilidades de escolha para ocupar cada posição
na (n − 2)-upla (quando todas as posições estão ocupadas por um mesmo rótulo, estamos diante de uma
particular árvore conhecida como estrela, onde n é o rótulo de grau n − 1, e há (n − 2) posições no código,
então, há T (n) = nn−2 distintas uplas e, portanto, árvores.
Pelo Teorema acima, a geração aleatória de qualquer seqüência de (n − 2) rótulos dentre os n rótulos
relativos aos n vértices implica em gerar o correspondente Código de Prüfer de uma qualquer árvore com
n vértices. A complexidade dessa geração é O(n). Nesse caso, assumimos que há um gerador de números
inteiros uniformemente distribuı́dos em um dado intervalo [a, b] de modo a utilizar um procedimento
uniforme (1, n) como o dado a seguir:
Algoritmo_Gera_Árvore_ Qualquer;
Entrada: n, número de vértices da árvore a gerar;
Saída: (n-2)-upla na forma de um vetor Código que contém
Código de Prüfer da árvore gerada;
Início
Para j = 1, n-2 faça
Código [j] = procedimento uniforme (1,n)
Fim.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
39
9.2. Árvores em que a seqüência de graus é dada. Seja uma árvore com n vértices rotulados. A
n
X
seqüência de inteiros (d(1), · · · , d(n)) é chamada seqüência de graus da árvore. Como
d(i) =
i→1
2n − 2, diz-se que uma seqüência de graus é válida quando satisfaz a essa igualdade. É claro que
diferentes árvores podem ter a mesma seqüência de graus, porém, como é esperado, com Códigos diferentes.
Exemplo 9.2.1. - Considere a seqüência de graus (3, 2, 1, 2, 1, 2, 1) de um grafo. A Figura abaixo
mostra quatro árvores que têm essa seqüência de graus e seus respectivos códigos.
1
3
2
6
4
4
5
3
código: <1,4,1,6,2,1>
3
1
7
7
2
6
2
5
6
7
código: <4,1,2,6,1,7>
1
6
1
3
7
4
2
4
5
5
código: <2,1,4,1,6,7>
código: <1,1,2,4,6,7>
Figura 30
Teorema 9.2.2. A quantidade de árvores rotuladas com n vértices que possuem a seqüência de graus
válida (d1 , d2 , · · · , dn ) é dada por:
Ã
n−2
!
d(1) − 1, · · · , d(n) − 1
Prova:
A prova é construtiva. Inicia-se com um Código de Prüfer em que as (n − 2) posições da (n − 2)-upla
estão vazias. Cada vértice v, cujo grau é d(v), tem seu correspondente rótulo figurando d(v) − 1 vezes no
código (Lema 8.5.5), ou seja, para cada um dos n vértices v, são escolhidas d(v) − 1 posições no código
(relativamente à atribuição de d(v) − 1 rótulos), dentre as posições ainda vazias no código. Pelo Lema,
n
X
tem-se:
dj (v) = 2m = 2(n − 1) + 2n − 2 = n + n − 2
Logo,
j→1
n
X
j→1
n
X
dj (v) − n = n − 2 ⇒
[dj (v) − 1] = n − 2.
j→1
Assim, todas as (n − 2) posições do código são ocupadas por um ou mais rótulos e, portanto, os
correspondentes valores dos rótulos são conhecidos, vez que se tem, a priori, a seqüência de graus dos
vértices das árvores que se quer contar, como válida. Esses valores dos rótulos podem, então, gerar (n − 2)!
40
PAULO JORGE M. TEXEIRA
códigos de árvores. Por outro lado, cada vértice v tem seu rótulo representado de (d(v) − 1)! modos em
códigos iguais, o que, em linguagem de Análise Combinatória indica as permutações com repetição de
elementos. Assim, o total de Códigos de Prüfer gerados aleatoriamente e, de modo similar, o total de
árvores geradas, será de
Ã
!
n−2
.
d(1) − 1, · · · , d(n) − 1
Exemplo 9.2.3. Geração aleatória de uma árvore com seis vértices cuja seqüência de graus é (1, 1, 1, 2, 4, 1).
O total de árvores com esta seqüência de graus é obtido através do Teorema 9.2.2, como:
Ã
6−2
0, 0, 0, 1, 3, 0
!
=
4!
= 4.
0!0!0!1!3!0!
Vamos obter essas quatro árvores. Inicialmente a tabela a seguir é construida.
v
1 2 3 4 5 6
d(v)
1 1 1 2 4 1
d(v) − 1 0 0 0 1 3 0
Observação: Todos que são zeros são folhas.
Os Códigos de Prüfer devem ter 4 posições (há 6 vértices) e, pela tabela acima, o rótulo 4 deve aparecer
uma só vez, enquanto o rótulo 5 deve aparecer 3 vezes no código.
A seqüência de passos é a seguinte:
Passo 1: Código de Prüfer vazio ( , , , )
Passo 2: Sorteio de uma posição para o rótulo 4 ( , 4, , )
Passo 3: Sorteio de três posições para o rótulo 5 (5, 4, 5, 5)
Os respectivos códigos de Prüfer para as árvores cuja seqüência de graus é (1, 1, 1, 2, 4, 1) são:
5
2
3
6
<4,5,5,5>
1
4
1
4
5
1
3
6
<5,4,5,5>
2
2
4
5
2
1
6
<5,5,4,5>
3
3
4
5
2
3
1
<5,5,5,4>
6
6
Figura 31
Os rótulos das folhas adjacentes ao vértice de rótulo 4 estão indicadas abaixo das setas na figura acima.
9.3. Árvores em que um determinado vértice tem o seu grau estipulado. Pelo Lema 8.5.5, o
rótulo de um vértice v ocorre d(v) − 1 vezes no Código de Prüfer da árvore.
Seja Q(n, q) a quantidade de árvores rotuladas com n vértices, onde um vértice especı́fico tem o seu
grau igual a q. O total de árvores rotuladas com essa propriedade é dado por:
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
Teorema 9.3.1. Q(n, q) =
Ã
!
n−2
q−1
41
(n − 1)n−q−1 , para 1 6 q 6 n − 1.
Prova:
A prova é construtiva. Inicia-se com um Código de Prüfer em que as (n − 2) posições da (n-2)-upla estão
vazias. Seja o vértice de rótulo n aquele vértice escolhido cujo grau é igual a q, 1 6 q 6 n − 1 (não há
problema na escolha do vértice cujo rótulo é o maior possı́vel: n, pois, caso não o seja, podemos ao final
fazer a alteração devida). Então, o rótulo n figura no Código de Prüfer exatamente (q − 1) vezes, conforme
o Lema 9.6 e, assim, precisamos escolher (q −1) posições do código, dentre as (n−2) disponı́veis, de modo a
q−1
inserir o rótulo n. Isso é feito de Cn−2
modos possı́veis. Restam, então, (n−2)−(q−1) = n−q−1 posições no
código para serem preenchidas pelos (n − 1) demais rótulos. Portanto, temos (n − 1)n−q−1 modos possı́veis
de preencher as restantes posições do código. Assim, pelo Princı́pio Multiplicativo, o total de árvores
q−1
rotuladas com n vértices em que um dado vértice tem grau q é dado por: Q(n, q) = Cn−2
(n − 1)n−q−1 .
Logo, a geração aleatória do Código de Prüfer e, consequentemente, de árvores nas condições do Teorema
9.3.1 pode ser feita segundo os seguintes passos:
1) o Código de Prüfer inicia-se com as (n − 2) posições vazias;
2) aleatoriamente atribui-se a (q − 1) posições do código o rótulo n (aquele rótulo do vértice com o grau
especificado);
3) para cada uma das (n − q − 1) posições disponı́veis no código, de modo aleatório atribui-se rótulos
escolhidos entre 1 e n − 1 (ou então n − 1 rótulos escolhidos, exceto aquele rótulo atribuı́do ao vértice de
grau considerado).
Exemplo 9.3.2. Geração de uma árvore com 5 vértices onde d(v5 ) = 3. Calcula-se o total de árvores com
Ã
!
5−2
(5 − 1)5−3−1 =
5 vértices, onde d(v5) = 3 e Q(5,3), através do Teorema 9.3.1, como: Q(5, 3) =
3−1
3x4 = 12
Os respectivos códigos de Prüfer são:
h1, 5, 5i, h2, 5, 5i, h3, 5, 5i, h4, 5, 5i, h5, 1, 5i, h5, 2, 5i, h5, 3, 5i, h5, 4, 5i, h5, 5, 1i, h5, 5, 2i, h5, 5, 3i, h5, 5, 4i.
Geração aleatória de uma árvore, dentre as 12 (doze) calculadas acima, nas quais o vértice rotulado por
5 tem grau igual a 3:
Passo 1: Código de Prüfer vazio ( , , )
Passo 2: Sorteio de 2 (duas) posições para o rótulo 5 uma vez que seu grau é igual a 3: (5, , 5)
Passo 3: Preencher, aleatoriamente, a posição restante do código com um dos rótulos 1,2,3 ou 4: (5, 1, 5)
ou (5, 2, 5) ou (5, 3, 5) ou (5, 4, 5).
Na figura abaixo estão representadas 4 (quatro) árvores e seus respectivos códigos, conforme a escolha
do rótulo central do código tenha sido 1, 2, 3 ou 4.
9.4. Árvores com número de folhas determinado.
42
PAULO JORGE M. TEXEIRA
3
2
3
4
<5,2,5>
5
2
4
<5,3,5>
4
3
<5,1,5>
1
1
4
1
5
5
5
2
2
3
<5,4,5>
1
Figura 32
O Teorema 9.4.1 trata da contagem de árvores para as quais o número de folhas é determinado,
utilizando-se os Números de Stirling de segunda espécie S(a, b) que fornecem o número de maneiras de
particionar um conjunto de a elementos em exatamente b subconjuntos. Calcula-se os valores para S(a, b)
assim:
S(a, b) =
(
1
, se a = b ou b = 1
bS(a − 1, b) + S(a − 1, b − 1) , se a 6= b e b < 1
Antes de apresentar e demonstrar o Teorema será mostrado, a seguir, um exemplo de como obter os
Números de Stirling de segunda espécie.
Considere um conjunto A = {a, b, c, d, e} com 5 elementos. Vamos considerar partições desse conjunto
em subconjuntos que contém 1, 2, 3, 4 e 5 subconjuntos, utilizando-se a definição dada acima.
• S(5, 1) = 1 (uma) partição em 1(um) conjunto, a saber: {a, b, c, d, e};
• S(5, 2) = 2 · S(4, 2) + S(4, 1) = 2 · {2 · S(3, 2) + S(3, 1)} + 1 = 4 · S(3, 2) + 2 · S(3, 1) + 1 =
4 · {2 · S(2, 2) + S(2, 1)} + 2 · 1 + 1 = 4 · {2 · 1 + 1} + 2 + 1 = 12 + 2 + 1 = 15 partições que contém 2
conjuntos cada, a saber:
{{a}, {b, c, d, e}}, {{b}, {a, c, d, e}}, {{c}, {a, b, d, e}}, {{d}, {a, b, c, e}}, {{e}, {a, b, c, d}};
{{a, b}, {c, d, e}}, {{a, c}, {b, d, e}}, {{a, d}, {b, c, e}}, {{a, e}, {b, c, d}}, {{b, c}, {a, d, e}},
{{b, d}, {a, c, e}}, {{b, e}, {a, c, d}}, {{c, d}, {a, b, e}}, {{c, e}, {a, b, d}}, {{d, e}, {a, b, c}}.
• S(5, 3) = 3 · S(4, 3) + S(4, 2) = 3 · {3 · S(3, 3) + S(3, 2)} + 2 · S(3, 2) + S(3, 1) = 9 + 5 · S(3, 2) + 1 =
10 + 5 · {2 · S(2, 2) + S(2, 1)} = 10 + 10 + 5 = 25 partições que contém 3 conjuntos cada, a saber:
{{a}, {b}, {c, d, e}}, {{a}, {c}, {b, d, e}}, {{a}, {d}, {b, c, e}}, {{a}, {e}, {b, c, d}}, {{b}, {c}, {a, d, e}},
{{b}, {d}, {a, c, e}}, {{b}, {e}, {a, c, d}}, {{c}, {d}, {a, b, e}}, {{c}, {e}, {a, b, d}}, {{d}, {e}, {a, b, c}};
{{a}, {b, c}, {d, e}}, {{a}, {b, d}, {c, e}}, {{a}, {b, e}, {c, d}}, {{b}, {a, c}, {d, e}}, {{b}, {a, d}, {c, e}},
{{b}, {a, e}, {c, d}}, {{c}, {a, b}, {d, e}}, {{c}, {a, d}, {b, e}}, {{c}, {a, e}, {b, d}}, {{d}, {a, b}, {c, e}},
{{d}, {a, c}, {b, e}}, {{d}, {a, e}, {b, c}}, {{e}, {a, b}, {c, d}}, {{e}, {a, c}, {b, d}}, {{e}, {a, d}, {b, c}}.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
43
• S(5, 4) = 4.S(4, 4) + S(4, 3) = 4 + 3.S(3, 3) + S(3, 2) = 7 + 3 = 10 partições que contém 4 conjuntos
cada, a saber:
{{a}, {b}, {c}, {d, e}}, {{a}, {b}, {d}, {c, e}}, {{a}, {b}, {e}, {c, d}}, {{a}, {c}, {d}, {b, e}},
{{a}, {c}, {e}, {b, d}}, {{a}, {d}, {e}, {b, c}}, {{b}, {c}, {d}, {a, e}}, {{b}, {c}, {e}, {a, d}},
{{b}, {d}, {e}, {a, c}}, {{c}, {d}, {e}, {a, b}},.
• S(5, 5) = 1 (uma) partição em 5 conjuntos unitários, a saber: {a}, {b}, {c}, {d}, {e}.
Teorema 9.4.1. Seja R(n, q) a quantidade de árvores rotuladas com n vértices e exatamente q folhas.
n!
Então: R(n, q) = S(n − 2, n − q), para 2 6 q 6 n − 1.
q!
Prova: Suponha que a árvore T = (V, E) com n vértices tenha exatamente q folhas, 2 6 q 6 n − 1.
O número de modos de escolher os rótulos desses q vértices que serão vértices folhas, entre os n vértices
n!
disponı́veis, é dado por Cn,p =
. Há um total de (n − q) vértices que terão seus respectivos
(n − q!)q!
rótulos figurando no Código de Prüfer e sua aparição no código pode ser feita de (n − q)! modos possı́veis.
n!
Assim, o número de modos de arrumar os (n − q) rótulos no código é de (n − q)!.Cn−q = . (∗)
q!
Como os rótulos das folhas escolhidos para as (n−2) posições do código. Como q > 2, então n−q 6 n−2
e daı́, utilizando-se os números de Stirling tem-se que as (n−2) posições do código formam um conjunto que
deve ser particionado em (n − q) conjuntos Ci que indicam as posições a serem ocupadas pelos respectivos
rótulos dos vértices. Considere, então, o Código de Prüfer de uma árvore da forma ha1 , a2 , · · · , an−2 i que
deve conter, exatamente, (n − q) rótulos distintos {r1 , r2 , · · · , rn−q }. Definem-se os (n − q) conjuntos Ci
formados pelas posições ocupadas pelo rótulo ri no código, isto é: i ∈ Ci se e somente se ai = ri . Portanto,
os conjuntos Ci satisfazem às seguintes propriedades:
(1): C1 ∩ C2 ∩ · · · ∩ Cn−q = φ;
(2): Ci 6= φ, para todo i, 1 6 i 6 n − q;
(3): C1 ∪ C2 ∪ · · · ∪ Cn−q = {1, 2, · · · , n − 2}.
Assim, a cada Código de Prüfer faz-se corresponder, únicamente, uma coleção de conjuntos Ci , ou
seja, dado o Código de Prüfer ha1 , a2 , · · · , an−2 i (que possui exatamente (n − q) distintos rótulos), há uma
única correspondência biunı́voca entre cada rótulo do conjunto {r1 , r2 , · · · , rn−q } e cada subconjunto do
conjunto {C1 , C2 , · · · , Cn−q } que satisfaz às propriedades acima. Portanto, há um total de S(n − 2, n − q)
modos de escolher os subconjuntos C1 , C2 , · · · , Cn−q . (**)
Concluindo, de (*) e (**), o número de árvores rotuladas com n vértices e exatamente q folhas é dado
n!
por R(n, q) = S(n − 2, n − q), para 2 6 q 6 n − 1.
q!
Logo, a geração aleatória do Código de Prüfer e, consequentemente, de árvores nas condições do Teorema
9.4.1 pode ser feita seguindo os seguintes passos:
1) o Código de Prüfer inicia-se com as (n − 2) posições vazias;
44
PAULO JORGE M. TEXEIRA
2) dentre os n vértices, escolhem-se aleatoriamente (n − q) vértices v1 , v2 , · · · , vn−q cujos rótulos irão
figurar no Código de Prüfer a ser criado (isso indica a escolha dos q vértices não-folha); escolhendo-se,
aleatoriamente, a cada vez, uma das posições disponı́veis no código, e atribuindo-se a cada código essa
posição escolhida;
3) para cada um dos (n − q) vértices, seus respectivos rótulos irão figurar no Código de Prüfer uma
única vez cada, dentre as (n − 2) posições disponı́veis. Isso pode
ser feito escolhendo-se, aleatoriamente, a cada vez, uma das posições disponı́veis no código, e atribuindose a cada código essa posição escolhida.
4) completado o Passo 3, todos os (n − q) rótulos dos respectivos vértices não-folha da árvore, já figuram
no código uma única vez cada. Resta agora escolher, aleatoriamente, para as (n − 2) − (n − q) = q − 2
posições vazias do código, os rótulos que ocuparão essas posições, dentre os rótulos desses mesmos (n − q)
vértices, podendo ou não se repetirem, esses rótulos. Isso equivale a atribuir o rótulo de um vértice
aleatoriamente escolhido (dentre os (n − q) vértices disponı́veis {v1 , v2 , · · · , vn−q }) a cada uma das (q − 2)
posições restantes do código, tomando o cuidado de continuar sempre a selecionar um novo vértice entre
os vértices disponı́veis de um total inicial de (n − q) vértices, até que todas as posições do código sejam
preenchidas.
Exemplo 9.4.2. Vamos apresentar a geração de uma árvore com 5 vértices e exatamente três folhas.
5!
Sabendo-se que S(3, 2) = 3, e utilizando o Teorema 9.4.1, vem: R(5, 3) = S(5 − 2, 5 − 3) = 20 · S(3, 2) =
3!
20 · 3 = 60.
Logo, há um total de 60 árvores que podem ser geradas tendo cada uma delas 5 vértices, sendo que
3(três) deles são vértices folha.
Passo 1: Código de Prüfer vazio ( , , ).
Passo 2: Vértices interiores que terão seus rótulos no código. Há n − q = 5 − 3 = 2 rótulos a serem
escolhidos de cada vez. Suponha que tenhamos escolhido o conjunto {1, 4}.
Passo 3: Preencher 2 (duas) posições no código de modo a colocar cada rótulo uma única vez (1, , 4).
Passo 4: Preencher as posições restantes com os mesmos rótulos, podendo ou não repeti-los (nesse
exemplo não há como fazer pois dispomos de apenas uma escolha) (1, 4, 4)
A figura abaixo mostra as 6(seis) árvores, geradas aleatoriamente, que têm os vértices 1 e 4 como vértices
interiores:
10. Conclusões
Neste trabalho apresentamos importantes e diferentes propriedades das árvores e o Código de Prüfer
que permite codificar e decodificar árvores, por exemplo, que tenham grande tamanho, facilitando o envio
de informações através de seus respectivos códigos e com a utilização de pequenos espaços de memória.
Muito importante também é verificar que a geração aleatória de uma árvore fica bastante facilitada com
a geração aleatória de números para ocupar as (n − 2) posições de uma (n − 2)-upla e que, esse método,
relaciona de modo unı́voco, uma única árvore a cada código.
CONTAGEM E CODIFICAÇÃO DE ÁRVORES
4
5
3
<1,1,4>
1
2
3
<1,4,4>
1
2
4
5
1
4
5
3
<4,4,1>
1
2
4
3
5
<4,1,4>
2
4
3
5
<1,4,1>
4
2
5
<4,1,1>
45
1
2
1
3
Figura 33
Uma questão que se coloca é: se precisarmos gerar árvores (a partir de grafos completos. Se o grafo
não for completo, podemos torná-lo, criando arestas fictı́cias) que possuam exatamente uma quantidade
finita de vértices folhas e, a priori, identificados, como fazer?! Outro problema sobre o qual estamos
agora nos debruçando é se é possı́vel gerar aleatoriamente árvores valoradas em suas arestas e como
seriam os processos de codificação e decodificação?! E aı́ surge a seguinte questão: E dentre as árvores
mencionadas acima, qual delas tem custo mı́nimo?! É um problema de otimização bastante complexo.
Estes e outros problemas fazem das árvores uma atraente área de investigação da Teoria das Grafos.
Esperamos ter proporcionado ao leitor o contato inicial no mundo das árvores e, assim, a partir da leitura
e compreensão desse texto possa se sentir fascinado para enveredar na investigação de outras situações
igualmente interessantes de pesquisa.
Referências
[1] Bondy, J.A., U.S.R. Murty. 1976. Graph Theory with Applications. London: Macmillan.
[2] Garey, M.R., D.S. Johnson. 1970. Computers and Intractability: A Guide to the Theory of NP-Completeness. New
York: W.H. Freeman.
[3] Moon, J. W.,1970. Counting Labelled Trees, Canadian Mathematical Monographs, Montreal,
[4] Szwarcfiter, J. L., Grafos e Algoritmos Computacionais, Editora Campus, 1984.
[5] Gross, J., Yellen, J., Graph Theory and its Applications, the CRC Press series on Discrete Mathematics and its
Applications, 1998.
[6] Deo, N., Micikevicius, P., Prüfer Like-Codes for Labelled Trees, Congressus Numerantium, 151, 65-73, 2001.
[7] Deo, N., Micikevicius, P., A New Enconding for Labeled Trees Employing a Stack and a Queue, Bulletin of the Institute
od Combinatorics and its Applications, 34,77-85,2002.
[8] Caminiti, S., Finocchi, I., Petreschi, R., A Unified Approach to Coding Labeled Trees, Proceedings of 6th Latin American
Symposium on Theoretical Informatics, 339-348, Buenos Aires, Argentina, 2004.