Algoritmo linear de rotulagem de tempo para uma árvore?

Eu tenho uma árvore não direcionada cujos vértices eu quero rotular. Os nós das folhas devem ser rotulados como um. Então, assuma que as folhas foram removidas. Na árvore que resta, as folhas devem ser rotuladas como duas. Esse processo continua da maneira óbvia até que todos os vértices tenham um rótulo. A razão pela qual faço isso é que desejo armazenar os vértices em uma fila e passar por eles "sai primeiro". Existe uma maneira fácil de fazer esse tempo ?$O(n+m)$

Eu posso resolver o problema executando um BFS em cada etapa. Mas, na pior das hipóteses, em cada passo que passo em cada vértice, removo exatamente duas folhas e enfileirá-las. Eu acredito que isso leva tempo quadrático.

Outra idéia foi primeiro encontrar todas as folhas e depois fazer um BFS de cada folha. Isso não me dá a solução desejada. Por exemplo, considere um tipo de "gráfico da coroa", como na figura abaixo. A solução desejada é mostrada, mas o lançamento de um BFS de cada folha resultaria em apenas dois rótulos usados.

Idealmente, o algoritmo de tempo linear também seria fácil de explicar e implementar.

Árvores não enraizadas

Você pode usar uma fila de prioridade para resolver isso em :$O(E+V\log V)$

• Coloque todos os vértices em uma fila de prioridade, com a prioridade sendo o grau.
• Enquanto a fila não estiver vazia:
  • Remova um vértice de prioridade mínima, que deve ser 1 (ou 0 no final).$v$$1$$0$
  • Seja , onde u passa por todos os vizinhos originais de v .$\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Subtraia da prioridade do vizinho restante único de u (se houver).$1$$u$

De fato, não precisamos realmente de uma fila prioritária, e esse algoritmo pode ser implementado usando uma fila simples no tempo :$O(E+V)$

• Inicialize uma matriz de comprimento com os graus de todos os vértices.$V$
• Inicialize outra matriz de comprimento com "vivo".$V$
• Passe uma vez pela primeira matriz e empurre todos os vértices do grau para uma fila.$1$
• Enquanto a fila não estiver vazia:
  • Estourar um vértice .$v$
  • Seja , onde u passa por todos os vizinhos originais de v .$\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Marque como "morto".$v$
  • Se tiver algum vizinho "vivo" u , subtraia 1 do grau de u .$v$$u$$1$$u$
  • Se o novo grau de for 1 , pressione u na fila.$u$$1$$u$

Árvores enraizadas

Use o DFS. Aqui está um esboço do algoritmo.

• Dado um nó , se v for uma folha, defina d ( v ) = 1 .$v$$v$$d(v) = 1$
• Se não for uma folha, execute o algoritmo em todos os seus filhos e, em seguida, deixe d ( v ) = 1 + max d ( u ) , onde u passa sobre o conjunto de todos os filhos.$v$$d(v) = 1 + \max d(u)$$u$

Você executa esse algoritmo na raiz.

Uma resposta direta é a seguinte:

• $(u,v)$$u$$v$

• Classifique topologicamente o gráfico.

• $v$$v$

$O(n+m)$$O(n+m)$