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

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.

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".

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.