*21. Suponha que T seja uma S_{k}-árvore com alça v. Mostre que T pode ser obtida de árvores disjuntas T_{0}, T_{1}, \ldots, T_{k-1}, em que v não está em nenhuma dessas árvores e em que T_{i} é uma S_{i}-árvore para i=0,1, \ldots, k-1, conectando v a r_{0} \mathrm{e} r_{i} a r_{i+1} para i=0,1, \ldots, k-2.
A listagem de vértices de uma árvore enraizada ordenada em ordem de nível começa com a raiz, seguida pelos vértices de ordem 1 , da esquerda para a direita, pelos vértices de nível 2 , da esquerda para a direita, e assim por diante.

Passo 1

Temos uma S_{k}-árvore T com alça v. O objetivo é mostrar que existem árvores disjuntas T_{0},T_{1},\dots,T_{k-1}, nenhuma contendo v, tais que cada T_{i} é uma S_{i}-árvore com raiz r_{i}, e que T se obtém ligando-se v a r_{0} e, para cada i=0,1,\dots,k-2, conectando-se r_{i} a r_{i+1}. O enunciado também registra a definição de listagem em ordem de nível, mas para esta decomposição só precisamos de conceitos de caminho, remoção de arestas e componentes conexas.

Passo 2

Seja (x_{0},x_{1},\dots,x_{k}) o caminho que vai da raiz x_{0} de T até x_{k}=v. Como v é a alça de comprimento k, este é o caminho de x_{0} a v de maior comprimento em T, e nele estão exatamente k arestas: \{x_{i-1},x_{i}\} para i=1,\dots,k.

Passo 3

Remova todas as arestas do caminho, isto é, remova \{x_{i-1},x_{i}\} para i=1,\dots,k. Assim T se separa em k+1 componentes conexas. Para i=0,1,\dots,k-1, defina T_{i} como a componente que contém x_{i}. A componente que fica com x_{k}=v é apenas o vértice isolado v, e as demais são disjuntas e não contêm v.

Passo 4

Cada T_{i} é então uma S_{i}-árvore com raiz r_{i}=x_{i}: na componente que sobra em torno de x_{i}, a maior distância de x_{i} a qualquer folha é exatamente i, pois na árvore original a subcadeia do caminho de x_{0} a x_{i} tem comprimento i e não há caminho mais longo em T que comece em x_{i}.

Passo 5

Para recompor T, basta recolocar as arestas removidas, isto é, ligar
v\;=\;x_{k}\quad\text{a}\quad r_{0}=x_{0},
e para cada i=0,1,\dots,k-2 ligar
r_{i}=x_{i}\quad\text{a}\quad r_{i+1}=x_{i+1}.
Essas conexões recriam exatamente as arestas da alça original, sem gerar ciclos e juntando os T_{i} e v numa única árvore T.

Resposta

A construção acima mostra que T se obtém de T_{0},T_{1},\dots,T_{k-1} (cada uma S_{i}-árvore) e do vértice v ligando-se v a r_{0} e r_{i} a r_{i+1} para i=0,\dots,k-2, conforme pedido.

Exercícios de Livros Relacionados