Comment créer un graphe à partir de composants biconnectés ?

Question

Je dispose d'un graphe et j'ai identifié toutes ses composantes biconnectées et tous ses sommets/articulations critiques à l'aide de l'algorithme de Tarjan.

J'essaie de créer un nouveau graphe en utilisant les composants biconnectés : les composants seront les nouveaux sommets et deux composants biconnectés sont liés s'ils partagent au moins un point d'articulation.

Par exemple, pour le graphe de l'image ci-dessous, les listes d'adjacence du nouveau graphe seraient les suivantes :

(1, 3) -> (3, 4, 5), (1, 2)

(1, 2) -> (1, 3)

(3, 4, 5) -> (1, 3)

où (1, 3), (1, 2), (3, 4, 5) sont les composantes biconnectées et 1, 3 sont les points d'articulation. Comment puis-je créer le nouveau graphe/les listes d'adjacence d'une manière relativement optimale ? Puis-je le faire pendant que j'exécute Tarjan sur le graphe ?

Edit : Une composante biconnectée est un sous-ensemble de sommets du graphe où chaque sommet de ce sous-ensemble restera connecté même si l'on supprime un sommet du graphe. Page wiki pour composant biconnecté

Answer 1

Oui, vous pouvez le faire assez facilement en utilisant la structure de données DSU (Disjoint Set Union, alias Union Find).

L'essentiel est de faire quelques observations :

• Le nouveau graphe sera un arbre ou une forêt d'arbres (pourquoi ? - tout cycle est biconnecté, il appartiendra donc à la même composante).
• Les arêtes de l'arbre résultant seront les ponts du graphe original (l'arbre résultant est également connu sous le nom d'"arbre pont").

Nous pouvons d'ores et déjà effectuer quelques modifications sur les tarjans :

• pour chaque bord (u,v) s'il s'agit d'un pont, l'enregistrer pour une utilisation ultérieure
• s'il ne s'agit pas d'un pont, utiliser DSU pour fusionner des ensembles disjoints u y v appartiennent à
• Pour construire l'arbre résultant après la fin de tarjan, nous pouvons utiliser les ponts sauvegardés et les ensembles disjoints restants,
• (opt) nous pouvons énumérer des ensembles disjoints si nous le souhaitons, mais comme il n'y aura jamais 2 ponts entre 2 ensembles disjoints (ce qui formerait un cycle, d'où une contradiction), nous pouvons simplement utiliser les sommets d'identité des ensembles disjoints pour le nouveau graphe.