Se considerarmos uma árvore como um conjunto ordenado parcial, ela se torna um caso especial de junção-semilático. Para uma junção semilática, queremos poder calcular o limite superior mínimo (único) de dois elementos (mais ou menos) com eficiência. No caso de uma árvore, uma estrutura de dados que permitiria isso seria armazenar para cada elemento no nó correspondente um ponteiro para o pai e uma medida de distância para a raiz. (Na verdade, uma rotulagem baseada na classificação topológica geralmente usada para "uma medida de distância até a raiz", efetivamente tudo o que é necessário é uma ordem parcial compatível que possa ser avaliada com eficiência).
Cada união-semilática finita pode ser representada como um conjunto de subconjuntos de um conjunto finito com contenção como ordem, de modo que o menor limite superior seja dado pela união dos conjuntos. Portanto, representar cada elemento por um número finito de tags e calcular o limite superior mínimo pela união das tags correspondentes seria uma estrutura de dados possível. (Observando o complemento, percebe-se que definir o limite superior mínimo como a interseção das tags correspondentes também seria possível.) Uma estrutura de dados muito mais comum é simplesmente usar uma matriz para armazenar todos os resultados de "a <= b "ou até todos os resultados de" junção (a, b) ".
No entanto, usar essa estrutura de dados para representar uma árvore seria meio estranho. Existem estruturas de dados semelhantes a árvores para junções semiláticas, que ainda permitem (mais ou menos) computação eficiente do (único) limite superior mínimo de dois elementos? (Talvez algum tipo de gráfico acíclico direcionado com informações adicionais nos nós seja semelhante à medida de distância da raiz da árvore?)
fonte
Respostas:
Este post no blog sobre teoria das redes possui uma seção de referência útil, que contém, entre outros, "Teoria da Rede com Aplicações", de Vijay K. Garg. O Capítulo 2 "Representando Posets" descreve algumas estruturas de dados para representar posets e discute como calcular a junção (x, y) usando essa estrutura de dados.
As duas primeiras estruturas de dados discutidas são a representação da lista de adjacências do gráfico de redução transitiva (= diagrama Hasse / relação de cobertura) e o gráfico de fechamento transitivo (= relação de poset). Uma observação sobre as vantagens de usar uma classificação topológica para rotular os nós precede essa discussão. Observe que os rótulos de classificação topológica seriam bons o suficiente como "uma medida de distância da raiz", que era uma parte da estrutura de dados de uma árvore na pergunta.
As outras representações discutidas são "Representação esquelética", "Representação matricial" e "Representação baseada em dimensão". A "Representação esquelética" é interessante e útil, mas baseada em uma decomposição em cadeia do poset (= qualquer). A "Representação matricial" pode parecer trivial, mas provavelmente é a melhor representação para os problemas mais práticos. A "Representação Baseada em Dimensões" representa o poset como subconjunto do produto cartesiano de ordens lineares, mas calcular a representação mínima desse tipo é difícil para NP.
Em conclusão, a representação mais semelhante a uma árvore é a representação da redução transitiva na lista de adjacências, juntamente com uma rotulação dos nós por uma classificação topológica (em vez de "uma medida de distância até a raiz"). Esta é realmente uma das representações usadas pelo Sage (a outra é a "Representação Matricial").
fonte