*21. Suponha que
seja uma
-árvore com alça
. Mostre que
pode ser obtida de árvores disjuntas
, em que
não está em nenhuma dessas árvores e em que
é uma
-árvore para
, conectando
a
a
para
.
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.
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
-árvore
com alça
. O objetivo é mostrar que existem árvores disjuntas
, nenhuma contendo
, tais que cada
é uma
-árvore com raiz
, e que
se obtém ligando-se
a
e, para cada
, conectando-se
a
. 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
o caminho que vai da raiz
de
até
. Como
é a alça de comprimento
, este é o caminho de
a
de maior comprimento em
, e nele estão exatamente
arestas:
para
.
Passo 3
Remova todas as arestas do caminho, isto é, remova
para
. Assim
se separa em
componentes conexas. Para
, defina
como a componente que contém
. A componente que fica com
é apenas o vértice isolado
, e as demais são disjuntas e não contêm
.
Passo 4
Cada
é então uma
-árvore com raiz
: na componente que sobra em torno de
, a maior distância de
a qualquer folha é exatamente
, pois na árvore original a subcadeia do caminho de
a
tem comprimento
e não há caminho mais longo em
que comece em
.
Passo 5
Para recompor
, basta recolocar as arestas removidas, isto é, ligar
e para cada
ligar
Essas conexões recriam exatamente as arestas da alça original, sem gerar ciclos e juntando os
e
numa única árvore
.
Resposta
A construção acima mostra que
se obtém de
(cada uma
-árvore) e do vértice
ligando-se
a
e
a
para
, conforme pedido.