Etichetta gruppi di vertici in un grafico in modo efficiente senza BFS / DFS

Question

Ho un grafico con un set di vertici $ \ mathcal {v} $ e un set di bordi $ \ Mathcal {e} $ . Esiste un percorso tra ogni 2 vertici nel grafico. Per ogni bordo c'è un peso associato $ w (e), e \ in \ mathcal {e} $ . Definisco una soglia (globale) $ T $ in modo tale che se $ w ((u, v)) I due vertici $ u, v \ in \ mathcal {v} $ sono nello stesso gruppo: $ g \ in \ Mathcal {V} \ RightArrow \ MathBB {Z}, G (V_1)= G (V_2) $ . Questo comportamento è transitivo. L'obiettivo è di etichettare i gruppi distinti a partire da zero (l'ordine dei gruppi è irrilevante). So che questo può essere ottenuto banalmente con BFS o DFS, ma voglio evitare di usare quelli.

L'idea di cui ho inventato è di iterare sui vertici, vai oltre il loro quartiere a 1 anello e creare un nuovo gruppo ogni volta che $ w (u, v) ) per uno qualsiasi dei bordi e né $ U $ né $ V $ Sono stati assegnati un gruppo (ad esempio $ G (U)= G (V)= -1 $ ). Inoltre, ciascun gruppo viene assegnato un'etichetta, che è inizialmente uguale all'indice del gruppo: $ h: \ mathbb {n} \ raddrizza \ mathbb {n}, h (g ( u))= g (u) $ . Se ad un certo punto $ w ((x, y)) e $ w ((y, z)) , ma $ g (x) \ ne g (z) $ quindi impostare $ h ( g (x)) \ sinistra frewrow \ min (h (g (x)), h (g (z)) $ e $ h (g (z)) \ Levinarrow H (G (x)) $ . Dopo questa procedura dovrebbe tenere: $ h (g (u))= h (g (v)), u, v \ in \ mathcal {v} $ Se esiste un percorso da $ u $ a $ V $ : $ \ PI= E_1, ..., E_N $ In tal modo che $ W (E_I) . L'algoritmo che ho trovato corretto o mi manca qualcosa? Poiché attualmente richiede $ | \ mathcal {v} | $ memoria | per ogni array $ G, H $ . C'è un modo per ottimizzare questo ulteriormente?

Answer 1

Mentre si evidenzia in I tuoi commenti , un approccio ragionevole è quello di eliminare tutti i bordi con il peso $ \ ge T $ , quindi calcolareI componenti collegati del grafico risultante (utilizzando qualsiasi algoritmo standard per compensare componenti collegati).

Answer 2

Credo che il mio algoritmo sia corretto. Di seguito è presentato uno schizzo della prova:

Ci sono 2 casi: o $ u \ ne v \ in \ mathcal {v} $ deve essere dallo stesso gruppo, o devono essere da Gruppi diversi (a seconda che esista un percorso tra loro tale che $ w (e) ). Deve essere dimostrato che l'algoritmo produce i gruppi risultanti (la prova per ogni caso verrà effettuata per contraddizione).

.

1. Caso 1: Let $ U, V \ in \ Mathcal {V} $ e c'è un percorso da $ U $ a $ V $ : $ \ PI= E_1, ..., E_N $ in modo tale che $ w (e_i) . Quindi $ h (G (u)) $ uguale $ h (g (v)) $ per L'algoritmo deve essere corretto.

2. Assunzione di algoritmo errata: supponiamo che questo non sia il caso, e che $ U $ , $ V $ appartengono a diversi gruppi in base al risultato dell'algoritmo. Per semplicità assumere che $ \ PI=pi_1, x, y, z, \ pi_2; \, x, y, z \ in \ mathcal {v} $ tali che tutti i vertici da $ \ pi_1, x $ appartengono a $ h (G (u)) $ e Tutti i vertici su $ y, z, \ pi_2 $ appartengono a $ h (g (v)) $ basato sull'algoritmo. Il caso seguendo l'ipotesi di cui sopra sarà dimostrato, ma dovrebbe essere chiaro che lo stesso vale per induzione anche se $ \ PI $ è diviso in più gruppi in base al algoritmo.

Prova per contraddizione: da (1), segue $ w (x, y) , e da (2) Segue: $ h (g (x)) \ ne h (g (z)) $ . Dalla definizione dell'algoritmo segue che non si divide mai i gruppi e unisce due gruppi se $ w (x, y) ma $ h (g (x)) \ ne h (g (z)) $ . Dal momento che l'algoritmo va su tutti i bordi, avrebbe dovuto fondere $ h (g (x)) $ e $ h (g ( z)) $ .

3. Caso 2: $ u, v \ in \ mathcal {v} $ e non c'è percorso $ \ PI $ da $ U $ a $ V $ in modo tale che $ w (e) , quindi $ h (g (u))= h (g (v)) $ .

4. Assunzione di algoritmo errato: assumere $ h (g (u))= h (g (v)) $ .

Prova per contraddizione: sia alla creazione di gruppo che a una fusione di gruppo (gli unici due modi per i vertici di finire nello stesso gruppo) è necessario esistere un percorso tra $ U $ e $ V $ in modo tale che $ w (e) . (3) afferma che non esiste tale percorso, allora $ h (G (u)) \ ne h (g (v)) $ .

chiaramente la prova è abbastanza informale, quindi potrei aver perso qualcosa. Lascerò la domanda aperta per un po ', perché 1) qualcuno può inventare un algoritm migliore e più ottimizzato e 2) potrei avere qualche errore nella mia prova.