mantendo uma árvore de expansão equilibrada de um gráfico não direcionado crescente

19

Estou procurando maneiras de manter uma árvore de abrangência relativamente equilibrada de um gráfico, à medida que adiciono novos nós / arestas ao gráfico.

Eu tenho um gráfico não direcionado que começa como um único nó, a "raiz".

Em cada etapa, adiciono ao gráfico um novo nó e uma aresta conectando-o ao gráfico ou apenas uma nova aresta conectando dois nós antigos. À medida que cresço no gráfico, mantenho uma árvore de abrangência. Na maioria das vezes, isso significa que, quando adiciono um novo nó e uma borda, defino o novo nó como filho do nó antigo ao qual ele se conecta.

Como não tenho controle sobre a ordem em que os novos nós são adicionados, o algoritmo de construção de árvore acima pode obviamente levar a árvores de extensão desequilibradas.

Alguém conhece heurísticas online que manterão a árvore de abrangência "relativamente equilibrada", enquanto minimizam a quantidade de trabalho realizado na re-arborização? Eu tenho controle total sobre a estrutura da árvore. O que não controlo é a conectividade gráfica ou a ordem em que novos nós são adicionados.

Observe que as respostas padrão do Google a termos como "equilibrado", "extensão" e "árvore" parecem ser árvores binárias e árvores B, e nenhuma delas se aplica. Os nós do meu gráfico podem ter qualquer número de vizinhos; portanto, os nós da árvore podem ter qualquer número de filhos, e não 2 como árvores binárias. As árvores B mantêm o equilíbrio alterando suas listas de adjacências e não consigo alterar a conectividade do gráfico.

SuperElectric
fonte
3
Talvez ajude se você fosse mais específico sobre qual seria sua árvore de abrangência balanceada ideal de um gráfico estático. Uma árvore BFS é automaticamente uma boa escolha como uma árvore balanceada (é a mais superficial possível, se você escolher a raiz correta ou com um fator de dois, independentemente da raiz)? Você precisa que o número de nós em cada subárvore seja menor por um fator constante do que o número de nós no pai, em qualquer lugar da árvore e, em caso afirmativo, o que você faz para gráficos que não possuem essas árvores?
David Eppstein
Uma árvore BFS seria, de fato, uma árvore de abrangência balanceada ideal se eu estivesse executando esta offline, com o gráfico inteiro fornecido de uma só vez. Não é necessário que o número de nós em cada subárvore seja menor por um fator constante do que o número de nós no pai.
SuperElectric
Você examinou as árvores de topo? pt.wikipedia.org/wiki/Top_tree
Somerlund dos pares

Respostas:

4

Toda vez que você adiciona um novo vértice com uma aresta, você não tem opções. Toda vez que você adiciona uma nova aresta, se a distância atual à raiz for maior que a distância através da nova aresta, você remove a aresta antiga no caminho mais curto antigo e adiciona a nova. Caso contrário, você apenas manterá sua árvore inalterada. Eu acho que dessa maneira você obtém algo muito semelhante a uma árvore BFS, no sentido de que os níveis da árvore conterão os mesmos vértices e a distância de um vértice à raiz será a mesma que a distância na árvore BFS (e em o gráfico), mas não sei se isso é suficiente para satisfazer sua condição de "árvore de expansão equilibrada ideal".

Vinicius dos Santos
fonte
2

Acabei fazendo o seguinte:

A resposta de Vinicius Santos é a primeira parte. Como ele diz, em qualquer quadro eu adiciono um novo nó e uma borda pai-filho conectada a ele, ou apenas adiciono uma borda cruzada entre dois nós existentes. As arestas pai-filho não oferecem oportunidades para alterar a estrutura da árvore, apenas as arestas cruzadas. Considere adicionar um E de borda cruzada entre os nós A e B, onde B tem a maior profundidade da árvore. Se (A.depth + 1) <B.depth, podemos diminuir B.depth tornando-o filho de A.

Tendo diminuído a profundidade de B, agora devemos verificar os vizinhos de B, para ver se eles podem diminuir sua profundidade ao se tornar filhos de B. Portanto, realizamos uma travessia pela primeira vez de B, que atravessa uma borda de X a Y se X. depth + 1 <Y.depth e define Y como filho de X.

SuperElectric
fonte