Étiquettes de sommets de sommets dans un graphique de manière efficace sans bfs / dfs

Question

J'ai un graphique avec un ensemble de sommets $ \ mathcal {v} $ et un ensemble d'arêtes $ \ mathcal {e} $ . Il existe un chemin entre tous les 2 sommets du graphique. À chaque bord, il y a un poids associé $ w (e), e \ in \ mathcal {e} $ . Je définis un seuil (global) $ t $ tel que si $ w (u, v)) les deux sommets u, v \ in \ mathcal {v} $ sont dans le même groupe: $ g \ in \ mathcal {v} \ RightARrow \ mathbb {z}, g (v_1)= g (v_2) $ . Ce comportement est transitif. L'objectif est d'étiqueter les groupes distincts à partir de zéro (l'ordre des groupes n'est pas pertinent). Je sais que cela peut être atteint de manière trivialité avec BFS ou DFS, mais je veux éviter d'utiliser ceux-ci.

L'idée que j'ai proposée est de itérer sur les sommets, passez sur leur quartier à 1 anneau et créez un nouveau groupe à chaque fois que $ W (U, V) ) pour l'un des bords et non $ u $ ni $ v $ Ont reçu un groupe (par exemple $ g (u)= g (v)= -1 $ ). En outre, chaque groupe est attribué à une étiquette, qui est initialement égale à l'index du groupe: $ h: \ mathbb {n} \ restard \ mathbb {n}, h (g (g (g ( u))= g (u) $ . Si à un moment donné $ w ((x, y)) et $ w ((y, z)) , mais $ g (x) \ ne g (z) $ puis réglez $ h ( g (x)) \ gaufrérow \ min (h (g (x)), H (g (z)) $ et $ h (g (z)) \ Leftarrow h (g (x)) $ . Après cette procédure, elle devrait contenir: $ h (g (u))= H (g (v)), U, v \ in \ mathcal {v} $ S'il existe un chemin d'accès de $ u $ to $ v $ : $ \ pi= e_1, ..., e_n $ telle que $ w (e_i) . Est-ce que l'algorithme que j'ai proposé est correct ou que j'ai manqué quelque chose? Comme il est actuellement nécessite $ | \ mathcal {v} | $ mémoire Pour chaque tableau $ g, h $ . Existe-t-il un moyen d'optimiser cela plus loin?

Answer 1

Comme vous le soulignez dans Vos commentaires , une approche raisonnable consiste à supprimer tous les bords avec poids $ \ ge t $ , puis calculerles composants connectés du graphe résultant (utilisant n'importe quel algorithme standard pour calculer les composants connectés).

Answer 2

Je crois que mon algorithme est correct. Un croquis de la preuve est présenté ci-dessous:

Il y a 2 cas: soit $ u \ ne v \ in \ mathcal {v} $ doit être du même groupe, ou ils doivent être de Différents groupes (selon qu'il existe un chemin d'accès entre eux de telle que $ w (e) ). Il est à montrer que l'algorithme produit les groupes résultants (la preuve pour chaque cas sera effectuée par contradiction).

1. cas 1: laissez u $ u, v \ in \ mathcal {v} $ et il y a un chemin de $ U $ à $ v $ : $ \ pi= e_1, ..., e_n $, ..., e_n $ tel que $ w (e_i) . Alors $ H (g (u)) $ devrait être égal $ h (g (v) $) $ pour l'algorithme doit être correct.

2. Assomption d'algorithme Incorrecté: supposez que ce n'est pas le cas, et que $ u $ , $ v $ appartiennent à différents groupes basés sur le résultat de l'algorithme. Pour la simplicité suppose que $ \ pi=pi_1, x, y, z, \ pi_2; \, x, y, z \ in \ mathcal {v} $ telle que tous les sommets de $ \ pi_1, x $ appartiennent à $ h (u) $ et Tous les sommets sur $ y, z, \ pi_2 $ appartiennent à $ h (g (v) $) $ basé sur l'algorithme. Le cas après l'hypothèse ci-dessus sera prouvé, mais il convient de préciser que la même chose tiendra par induction, même si $ \ pi $ est divisé en plus de groupes basés sur le algorithme.

Proof par contradiction: de (1), il suit $ w (x, y) et de (2) Il suit: $ h (g (x)) \ ne h (g (z)) $ . Dans la définition de l'algorithme, il s'ensuit qu'il ne divise jamais des groupes et fusionne deux groupes si $ w (x, y) mais H (g (x)) \ ne h (g (z)) $ . Étant donné que l'algorithme passe sur tous les bords, il aurait dû fusionné $ h (g (x)) $ et $ h (g (g (g (g ( z)) $ .

3. cas 2: u $ u, v \ mathcal {v} $ et il n'y a pas de chemin $ \ pi $ de $ U $ to $ v $ tel que $ w (e) , puis $ h (g (u))= H (g (v)) $ .

4. Assomption d'algorithme Incorrecté: supposez H (G (U))= H (g (V)) $

   .
   .

Preuve par contradiction: à la fois à la création de groupe et à la fusion du groupe (les seules deux manières pour les sommets de se retrouver dans le même groupe), il doit exister un chemin entre $ U $ et $ V $ tel que $ w (e) . (3) indique qu'aucun chemin de ce type n'existe, alors $ H (g (u)) \ ne h (g (v)) $ .

.

Il est clair que la preuve est assez informelle, alors j'ai peut-être manqué quelque chose. Je laisserai la question ouverte pendant un moment, car 1) quelqu'un peut proposer un algoritme meilleur et plus optimisé, et 2), je peux avoir une erreur dans ma preuve.