maintien d'un arbre couvrant équilibré d'un graphique non orienté croissant

19

Je cherche des moyens de maintenir un arbre couvrant relativement équilibré d'un graphique, alors que j'ajoute de nouveaux nœuds / arêtes au graphique.

J'ai un graphique non orienté qui commence comme un seul nœud, la "racine".

À chaque étape, j'ajoute au graphique soit un nouveau nœud et un bord le connectant au graphique, soit juste un nouveau bord, connectant deux anciens nœuds. Au fur et à mesure que je développe le graphique, je maintiens un arbre couvrant. La plupart du temps, cela signifie que lorsque j'ajoute un nouveau nœud et un nouveau bord, je définis le nouveau nœud comme l'enfant de l'ancien nœud auquel il se connecte.

Je n'ai aucun contrôle sur l'ordre dans lequel les nouveaux nœuds sont ajoutés, donc l'algorithme de construction d'arbre ci-dessus peut évidemment conduire à des arbres s'étendant sur un déséquilibre.

Quelqu'un connaît-il l'heuristique en ligne qui gardera l'arbre couvrant "relativement équilibré", tout en minimisant la quantité de travail effectuée dans la ré-arborescence? J'ai un contrôle total sur la structure arborescente. Ce que je ne contrôle pas, c'est la connectivité du graphique ou l'ordre dans lequel de nouveaux nœuds sont ajoutés.

Notez que les réponses standard de Google à des termes tels que "équilibré" "couvrant" et "arbre" semblent être des arbres binaires et des arbres B, ni l'un ni l'autre. Mes nœuds de graphe peuvent avoir n'importe quel nombre de voisins, donc les nœuds d'arbre peuvent avoir n'importe quel nombre d'enfants, pas 2 comme les arbres binaires. Les arbres B maintiennent l'équilibre en modifiant leurs listes d'adjacence, et je ne peux pas changer la connectivité du graphique.

SuperElectric
la source
3
Il serait peut-être utile que vous soyez plus précis sur ce que serait votre arbre couvrant équilibré idéal d'un graphe statique. Un arbre BFS est-il automatiquement un bon choix comme arbre équilibré (il est aussi peu profond que possible, si vous choisissez la bonne racine, ou dans un facteur de deux indépendamment de la racine)? Avez-vous besoin que le nombre de nœuds dans chaque sous-arbre soit plus petit d'un facteur constant que le nombre de nœuds au niveau du parent, partout dans l'arbre, et si oui, que faites-vous pour les graphiques qui n'ont pas de tels arbres?
David Eppstein
Un arbre BFS serait en effet un arbre couvrant équilibré idéal si je l'exécutais hors ligne, avec le graphique entier donné à la fois. Il n'est pas nécessaire que le nombre de nœuds dans chaque sous-arbre soit plus petit d'un facteur constant que le nombre de nœuds dans le parent.
SuperElectric
Avez-vous examiné les meilleurs arbres? en.wikipedia.org/wiki/Top_tree
Peer Sommerlund

Réponses:

4

Chaque fois que vous ajoutez un nouveau sommet avec une arête, vous n'avez pas d'options. Chaque fois que vous ajoutez un nouveau bord, si la distance actuelle à la racine est supérieure à la distance passant par le nouveau bord, vous supprimez l'ancien bord dans l'ancien chemin le plus court et ajoutez le nouveau. Sinon, vous gardez simplement votre arbre inchangé. Je pense que de cette façon, vous obtenez quelque chose de très similaire à un arbre BFS dans le sens où les niveaux de l'arbre contiendront les mêmes sommets et la distance d'un sommet à la racine sera la même que la distance dans l'arbre BFS (et dans le graphique), mais je ne sais pas si cela suffit pour satisfaire votre condition "d'arbre couvrant idéal".

Vinicius dos Santos
la source
2

J'ai fini par faire ce qui suit:

La réponse de Vinicius Santos en est la première partie. Comme il le dit, à n'importe quelle image, j'ajoute un nouveau nœud et un bord parent-enfant qui s'y connecte, ou j'ajoute simplement un bord transversal entre deux nœuds existants. Les bords parent-enfant n'offrent aucune possibilité de modifier la structure de l'arborescence, seuls les bords croisés le font. Pensez à ajouter un bord transversal E entre les nœuds A et B, où B a la plus grande profondeur d'arbre. Si (A.depth + 1) <B.depth, alors nous pouvons diminuer B.depth en en faisant un enfant de A.

Après avoir diminué la profondeur de B, nous devons maintenant vérifier les voisins de B, pour voir s'ils peuvent diminuer leur profondeur en devenant les enfants de B. Nous effectuons donc une traversée en largeur de B, qui traverse un bord de X à Y si X. depth + 1 <Y.depth, et définit Y comme un enfant de X.

SuperElectric
la source