Connectivité dynamique - Dynamic connectivity

En informatique et en théorie des graphes , une structure de connectivité dynamique est une structure de données qui maintient dynamiquement des informations sur les composants connectés d'un graphe.

L'ensemble V des sommets du graphe est fixe, mais l'ensemble E des arêtes peut changer. Les trois cas, par ordre de difficulté, sont:

• Les arêtes ne sont ajoutées qu'au graphique (cela peut être appelé connectivité incrémentielle );
• Les arêtes sont uniquement supprimées du graphique (cela peut être appelé connectivité décrémentielle );
• Les bords peuvent être ajoutés ou supprimés (cela peut être appelé une connectivité entièrement dynamique ).

Après chaque ajout / suppression d'une arête, la structure de connectivité dynamique doit s'adapter de manière à pouvoir donner des réponses rapides aux requêtes de la forme "y a-t-il un chemin entre x et y ?" (de manière équivalente: "les sommets x et y appartiennent-ils au même composant connexe?").

Connectivité incrémentale

Si des arêtes ne peuvent être ajoutées que, le problème de connectivité dynamique peut être résolu par une structure de données à jeu disjoint . Chaque ensemble représente un composant connecté; il y a un chemin entre x et y si et seulement s'ils appartiennent au même ensemble. Le temps amorti par opération est , où n est le nombre de sommets et α est la fonction Ackermann inverse . ${\ displaystyle \ Theta (\ alpha (n))}$

Connectivité décrémentielle

Le cas dans lequel les arêtes ne peuvent être supprimées que par Shimon Even et Yossi Shiloach .

La structure utilise une table qui spécifie, pour chaque sommet, le nom du composant auquel il appartient. Ainsi, une requête de connectivité prend un temps constant. Le défi consiste à mettre à jour la table lorsqu'une arête est supprimée.

Graphiques acycliques (forêts)

Lorsque l'arête u - v est supprimée dans une forêt , l'arborescence contenant cette arête est divisée en deux arbres: l'un d'eux contient u et l'autre contient v . Le tableau est mis à jour de la manière suivante.

• Scannez l'arborescence à partir de u (en utilisant n'importe quel algorithme de scan d'arborescence, tel que DFS ).
• Parcourez l'arborescence à partir de v .
• Effectuez les deux procédures ci-dessus en parallèle, c'est-à-dire soit en utilisant deux processus parallèles, soit en imbriquant leurs étapes (faites une étape de premier balayage, puis une étape de deuxième balayage, puis une étape de premier balayage, etc.).
• Supposons que le premier balayage qui se termine soit le balayage à partir de u (nous savons donc que l'arbre contenant u est le plus petit). Attribuez un nouveau nom de composant à chaque nœud du sous-arbre de u .

Puisque nous renommons toujours le plus petit sous-composant, le temps amorti pour une opération de suppression est . ${\ displaystyle O (\ log (n))}$

Graphiques généraux

Lorsqu'une arête est supprimée dans un graphe général, nous ne savons pas si son composant reste un composant unique (connecté par d'autres arêtes) ou s'il est brisé en deux composants. Nous utilisons donc deux processus qui s'exécutent en parallèle (ou de manière entrelacée). Le processus A vérifie si la suppression de l'arête rompt un composant et, si c'est le cas, les deux processus s'arrêtent. Le processus B vérifie si la suppression de bord ne rompt pas le composant auquel il appartient, et si ce n'est pas le cas, les deux processus s'arrêtent à nouveau.

Processus A

est similaire au cas du graphe acyclique: il y a deux sous-processus qui balaient à partir des deux extrémités de l'arête supprimée. Si l'un des sous-processus se termine avant d'atteindre l'autre extrémité, cela signifie que le composant est divisé en deux sous-composants et que le nom du plus petit sous-composant est mis à jour, comme précédemment. Ainsi, le temps amorti pour une opération de suppression est à nouveau . ${\ displaystyle O (\ log (n))}$

Processus B

utilise une structure en largeur d'abord (BFS), qui est initialisée comme suit. Un sommet r est choisi et le BFS en part. Le seul sommet du niveau 0 est r . Tous les sommets de distance i de la racine sont au niveau i . Si G n'est pas connecté, une nouvelle analyse est lancée à un sommet v non analysé , v est placé au niveau 1 et une arête artificielle connecte v à la racine r ; tous les sommets de distance i à v sont maintenant au niveau i +1, etc. Des arêtes artificielles sont introduites afin de conserver tous les composants connectés dans une structure BFS et ne sont utilisées qu'à cette fin. De toute évidence, les bords artificiels ne sont utilisés que dans le processus B.

La structure a les propriétés suivantes. Un sommet v au niveau i , i > 0, n'a que trois types d'arêtes: les arêtes arrière qui le relient au niveau i −1 (il y a au moins une arête de ce type, qui peut être artificielle), les arêtes locales qui le relient à d'autres arêtes au niveau i (il y a zéro ou plus de ces arêtes), ou arêtes avant qui le relient aux arêtes au niveau i +1 (il y a zéro ou plus de ces arêtes). Donc pour chaque sommet v , nous maintenons trois ensembles d'arêtes (arrière, local et avant).

Lorsqu'une arête u - v est supprimée, il existe deux options: soit u et v sont au même niveau, soit ils sont dans des niveaux dont le nombre diffère de 1.

Cas 1

à la fois u et v sont sur le même niveau. Dans ce cas, la suppression des arêtes ne peut pas modifier les composants. L'arête est simplement supprimée des ensembles d'arêtes locales de u et v , et le processus B s'arrête (et donc le processus A est également arrêté). Notre structure BFS est toujours valide.

Cas 2

u et v sont à des niveaux différents. Sans perte de généralité, supposons que u est au niveau i −1 et v est au niveau i ; par conséquent, le bord doit être retiré de l'avant ( u ) et de l'arrière ( v ).

Cas 2.1

Si le nouveau vers l'arrière ( v ) n'est pas vide, alors les composants n'ont pas changé: il y a d'autres arêtes qui relient v vers l'arrière. Le processus B s'arrête (et le processus A est également arrêté).

Cas 2.2

Si le nouveau vers l'arrière ( v ) est vide, alors v n'est plus relié au niveau i −1, et donc sa distance à la racine n'est plus i ; il doit être au moins i +1. De plus, il peut y avoir d'autres sommets, connectés à v , dont la distance de la racine augmente à la suite de la suppression. Pour calculer les distances mises à jour, nous utilisons une file d'attente Q, qui ne contient initialement que le sommet v .

Tant que Q n'est pas vide:

1. w  : = retirer la file d'attente (Q)
2. Retirez w de son niveau (disons j ) et placez-le au niveau suivant ( j +1).
3. Mettre à jour les voisins locaux:
   • Pour chaque arête w - x de local ( w ), supprimez-la de local ( x ) et mettez-la en avant ( x ).
   • en arrière ( w ): = local ( w )
4. Mettre à jour les voisins avant:
   • Pour chaque arête w - x en avant ( w ), retirez-la de l'arrière ( x ) et mettez-la en local ( x ); si le nouveau vers l'arrière ( x ) est vide, mettez x en file d'attente sur Q.
   • local ( w ): = avant ( w )
   • forward ( w ): = ensemble vide
5. Si le nouveau vers l'arrière ( w ) est vide, mettez à nouveau w en file d'attente sur Q.

Si la suppression des bords ne casse aucun composant et que nous sommes dans le cas 2.2, la procédure s'arrêtera finalement. Dans ce cas, il est facile de voir que la structure BFS est correctement maintenue. Si sa suppression casse un composant, la procédure ne s'arrêtera pas d'elle-même. Cependant, le processus A, reconnaissant la rupture, s'arrêtera et les deux processus s'arrêteront. Dans ce cas, toutes les modifications apportées à la structure BFS sont ignorées, et nous revenons à la structure BFS que nous avions juste avant la suppression, sauf que l'arête supprimée est maintenant remplacée par une arête artificielle. Clairement, dans ce cas, v est maintenant la racine d'un arbre qui inclut le nouveau composant, et peut-être des composants supplémentaires, à travers d'autres arêtes artificielles. En outre, il n'y a pas de bords reliant les descendants de v avec des sommets qui ne sont pas v descendants de, à l' exception du bord artificiel . ${\ displaystyle uv}$

chaque fois qu'une arête est traitée dans la procédure, l'un de ses points de terminaison chute d'un niveau. Puisque le niveau le plus bas qu'un sommet peut atteindre dans les exécutions qui se terminent par le processus B est , le coût par arête est limité par . Par conséquent, le temps amorti par opération de suppression est . ${\ displaystyle | V | -1}$${\ displaystyle 2 | V |}$${\ displaystyle O (n)}$

Connectivité entièrement dynamique

Graphiques acycliques (forêts)

Une forêt peut être représentée à l'aide d'une collection d' arbres coupés par Link ou d'arbres de tournée Euler . Ensuite, le problème de connectivité dynamique peut être résolu facilement, car tous les deux nœuds x, y, x sont connectés à y si et seulement si FindRoot (x) = FindRoot (y). Le temps de mise à jour amorti et le temps de requête sont tous deux O (log ( n )).

Graphiques généraux

Un graphe général peut être représenté par sa forêt étendue - une forêt qui contient un arbre pour chaque composant connecté du graphe. Nous appelons cette forêt couvrante F . F lui-même peut être représenté par une forêt d' arbres de tour d'Euler .

Les opérations de requête et d' insertion sont mises en œuvre en utilisant les opérations correspondantes sur les arbres ET représentant F . L'opération de suppression difficile est, en particulier, la suppression d' un bord qui est contenu dans l' un des arbres de recouvrement de F . Cela divise l'arbre couvrant en deux arbres, mais il est possible qu'il y ait un autre bord qui les relie. Le défi est de trouver rapidement un tel bord de remplacement, s'il existe. Cela nécessite une structure de données plus complexe. Plusieurs de ces structures sont décrites ci-dessous.

La structure Level

Chaque arête du graphique se voit attribuer un niveau . Soit L = lg n . Le niveau de chaque arête insérée dans le graphe est initialisé à L , et peut diminuer vers 0 lors des opérations de suppression.

Pour chaque i compris entre 0 et L , définissez Gi comme le sous-graphe constitué d'arêtes qui sont au niveau i ou moins, et Fi une forêt s'étendant de Gi . Notre forêt F d'avant s'appelle désormais FL . On conservera une séquence décroissante de forêts FL ⊇ ... ⊇ F 0.

Opérations

Les opérations Query et Insert n'utilisent que la plus grande forêt FL . Les sous-graphes plus petits ne sont consultés que lors d'une opération de suppression, et en particulier de suppression d'une arête qui est contenue dans l'un des arbres couvrant de FL .

Lorsqu'une telle arête e = x - y est supprimée, elle est d'abord supprimée de FL et de toutes les petites forêts étendues auxquelles elle appartient, c'est-à-dire de chaque Fi avec i ≥ niveau ( e ). Ensuite, nous recherchons un bord de remplacement.

Commencez par la plus petite forêt couvrant qui contenait e , à savoir, Fi avec i = niveau ( e ). L'arête e appartient à un certain arbre T ⊆ Fi . Après la suppression de e , l'arbre T est divisé en deux arbres plus petits: Tx qui contient le nœud x et Ty qui contient le nœud y . Une arête de Gi est une arête de remplacement, si et seulement si elle connecte un nœud dans Tx avec un nœud dans Ty . Supposons que wlog que Tx soit le plus petit arbre (c'est-à-dire qu'il contienne au plus la moitié des nœuds de T ; nous pouvons dire la taille de chaque sous-arbre par une annotation ajoutée aux arbres d'Euler).

On boucle sur toutes les arêtes ε de niveau i et au moins un nœud dans Tx :

• Si l'autre nœud de ε est dans Ty , alors une arête de remplacement est trouvée! Ajoutez ce bord à Fi et à toutes les forêts contenant jusqu'à FL , et terminez. Les forêts étendues sont fixes. Notez que pour payer cette recherche, nous diminuons le niveau des arêtes visitées lors de la recherche.
• Si l'autre nœud de ε est dans Tx , alors ce n'est pas une arête de remplacement, et pour le «pénaliser» pour avoir perdu notre temps, on diminue son niveau de 1.

Analyse

Le niveau de chaque arête sera diminué au plus lg n fois. Pourquoi? Car à chaque diminution, il tombe dans un arbre dont la taille est au plus égale à la moitié de la taille de son arbre au niveau précédent. Ainsi, à chaque niveau i , le nombre de nœuds dans chaque composant connecté est d'au plus 2 ⁱ . Par conséquent, le niveau d'une arête est toujours au moins égal à 0.

Chaque arête dont le niveau est diminué prend du temps à trouver (en utilisant les opérations de l'arborescence ET). Au total, chaque front inséré prend du temps jusqu'à ce qu'il soit supprimé, donc le temps amorti pour la suppression est . La partie restante de la suppression prend également du temps, car nous devons supprimer l'arête de la plupart des niveaux et la suppression de chaque niveau prend (à nouveau en utilisant les opérations ET). ${\ Displaystyle O (\ lg n)}$${\ displaystyle O (\ lg ^ {2} n)}$${\ displaystyle O (\ lg ^ {2} n)}$${\ displaystyle O (\ lg ^ {2} n)}$${\ Displaystyle O (\ lg n)}$${\ Displaystyle O (\ lg n)}$

Au total, le temps amorti par mise à jour est de . Le temps par requête peut être amélioré à . ${\ displaystyle O (\ lg ^ {2} n)}$${\ Displaystyle O (\ lg n / \ lg \ lg n)}$

Cependant, le pire des cas par mise à jour pourrait être . La question de savoir si le moment le plus défavorable peut être amélioré était une question ouverte, jusqu'à ce qu'elle soit résolue par l'affirmative par la structure Cutset. ${\ displaystyle O (n)}$

La structure Cutset

Étant donné un graphe G (V, E) et un sous-ensemble T⊆V, définissez le cutset (T) comme l'ensemble des arêtes qui connectent T avec V \ T. La structure cutset est une structure de données qui, sans garder le graphe entier en mémoire, peut trouver rapidement une arête dans le cutset, si une telle arête existe.

Commencez par donner un nombre à chaque sommet. Supposons qu'il y ait n sommets; alors chaque sommet peut être représenté par un nombre avec lg ( n ) bits. Ensuite, donnez un nombre à chaque arête, qui est une concaténation des nombres de ses sommets - un nombre avec 2 lg ( n ) bits.

Pour chaque sommet v , calculez et conservez xor ( v ), qui est le xor des nombres de toutes les arêtes qui lui sont adjacentes.

Maintenant, pour chaque sous-ensemble T⊆V, il est possible de calculer xor (T) = le xor des valeurs de tous les sommets de T. Considérons une arête e = u - v qui est une arête interne de T (c'est-à-dire à la fois u et v sont en T). Le nombre de e est inclus deux fois dans xor (T) - une fois pour u et une fois pour v . Puisque le xor de chaque nombre avec lui-même est 0, e disparaît et n'affecte pas xor (T). Ainsi, xor (T) est en fait le xor de toutes les arêtes de cutset (T). Il existe plusieurs options:

• Si xor (T) = 0, alors nous pouvons répondre en toute confiance que cutset (T) est vide.
• Si xor (T) est le numéro d'une arête réelle e , alors probablement e est la seule arête de cutset (T), et nous pouvons renvoyer e . On peut également lire les extrémités de e à partir du nombre de e par le fractionnement à l'lg ( n ) des bits les plus à gauche et le lg ( n ) des bits les plus à droite.
• La troisième option est que xor (T) est un nombre différent de zéro qui ne représente pas une arête réelle. Cela ne peut se produire que s'il y a deux arêtes ou plus dans le jeu de coupes (T), car dans ce cas xor (T) est le xor de plusieurs nombres d'arêtes. Dans ce cas, nous signalons une «défaillance», car nous savons qu'il y a des arêtes dans le cutset mais ne pouvons identifier aucune arête unique.

Notre objectif est maintenant de gérer cette troisième option.

Tout d'abord, créez une séquence de niveaux lg ( n ) des structures cutset, dont chacun contient environ la moitié des bords du niveau supérieur (c'est-à-dire, pour chaque niveau, choisissez chaque bord du niveau supérieur avec une probabilité de 1/2). Si au premier niveau xor (T) renvoie une valeur illégale, ce qui signifie que cutset (T) a deux arêtes ou plus, alors il y a une chance qu'au niveau suivant, qui contient moins d'arêtes, xor (T) renverra une valeur légale valeur puisque cutset (T) contiendra un seul bord. Si xor (T) renvoie toujours une valeur illégale, passez au niveau suivant, etc. Puisque le nombre d'arêtes diminue, il y a deux cas:

• Le bon cas est que nous trouvons finalement un niveau dans lequel le cutset (T) contient une seule arête; puis nous retournons ce bord et finissons.
• Le mauvais cas est que nous trouvons finalement un niveau dans lequel le jeu de coupes (T) ne contient aucune arête; puis nous signalons "échec", car nous savons qu'il y a des arêtes dans le cutset mais ne pouvons identifier aucune arête unique.

Il est possible de prouver que la probabilité de succès est d'au moins 1/9.

Ensuite, créez une collection de versions indépendantes C  lg ( n ) de la structure de niveau, où C est une constante. Dans chaque version, effectuez une réduction aléatoire indépendante des arêtes d'un niveau à l'autre. Essayez chaque requête sur chacune des versions jusqu'à ce que l'une d'elles réussisse. La probabilité que toutes les versions échouent est au plus:

${\ displaystyle (1-1 / 9) ^ {C \ lg {n}} = 2 ^ {- 0,17C \ lg {n}} = n ^ {- 0,17C}}$

En sélectionnant correctement C, nous pouvons rendre la probabilité de défaillance arbitrairement proche de 0.

Opérations

Nous pouvons ajouter une structure cutset à une structure de connectivité dynamique.

Les opérations d'insertion et de suppression sur la structure du jeu de coupes se font exactement de la même manière: l'arête insérée / supprimée est XORed dans ses deux extrémités.

Lorsqu'une arête est supprimée de la forêt couvrant utilisée pour la structure de connectivité dynamique, la structure de jeu de coupes est utilisée pour rechercher une arête de remplacement.

Analyse

Une seule structure de cutset ne nécessite que de la mémoire O ( n lg n ) - un seul nombre, avec 2 lg n bits, pour chacun des n sommets. Nous n'avons pas à garder les bords eux-mêmes. Pour les graphes denses, c'est beaucoup moins cher que de garder le graphe entier en mémoire.

Nous devons conserver les versions lg ( n ), chacune contenant des niveaux lg ( n ). Par conséquent, la mémoire totale requise est . ${\ Displaystyle O (n \ lg ^ {3} n)}$

Le temps de requête est O (polylog ( n )) dans le pire des cas. Ceci est en contraste avec la structure The Level , dans laquelle le temps de requête est O (polylog ( n )) amorti, mais le temps le plus défavorable est O ( n ).

Connectivité dynamique hors ligne

Si l'ordre dans lequel les arêtes seront supprimées est connu à l'avance, nous pouvons résoudre le problème de connectivité dynamique dans log (n) par requête. Si nous pouvons maintenir une forêt couvrant maximum où les arêtes sont ordonnées par leur temps de suppression, nous savons que lorsque nous supprimons une arête qui se trouve dans la forêt, il n'y a pas d'arête possible qui puisse la remplacer. S'il y avait une arête qui connecte les deux mêmes composants que l'arête supprimée, alors cette autre arête aurait fait partie de la forêt couvrant maximum au lieu de l'arête que nous avons supprimée. Cela rend l'opération de suppression triviale: nous devons simplement diviser l'arborescence en ses deux parties si l'arête à supprimer fait partie de notre forêt, ou ignorer l'opération dans le cas contraire.

L'ajout d'un bord est légèrement plus compliqué. Si nous ajoutons une arête de bord e de u à v, alors si u et v ne sont pas connectés, alors cette arête fera partie de la forêt de couverture maximale. S'ils sont connectés, nous voulons ajouter u-> v à notre forêt si cela peut améliorer notre forêt maximale. Pour ce faire, nous devons vérifier rapidement quelle arête a le plus petit temps de suppression sur le chemin de u à v.Si le temps de suppression de cette arête vient après le temps de suppression de e, alors e ne peut pas améliorer notre forêt couvrant minimum. Sinon, l'autre arête doit être supprimée et remplacée par e.

Cela nous oblige à effectuer les opérations suivantes: ajouter une arête, couper une arête et interroger l'arête minimale sur un chemin, ce qui peut être fait assez facilement avec un arbre coupé par lien dans log (n) par opération.

Voir également

• Problème dynamique (algorithmes)
• Raffinement de la partition

Les références

• Voir aussi: Thorup, M. (2000). Connectivité graphique entièrement dynamique presque optimale . Actes du trente-deuxième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '00. p. 343. doi : 10.1145 / 335305.335345 . ISBN   1581131844 .