Grupos de etiquetas de vértices em um gráfico de maneira eficiente sem BFS / DFS

Question

Eu tenho um gráfico com um conjunto de vértices $ \ mathcal {v} $ e um conjunto de bordas $ \ mathcal {e} $ . Existe um caminho entre cada 2 vértices no gráfico. Para cada borda, há um peso associado $ W (E), e \ in \ mathcal {e} $ . Eu defino um limiar (global) $ t $ tal que, se $ w ((u, v)) os dois vértices $ u, v \ in \ mathcal {v} $ estão no mesmo grupo: $ g \ in \ mathcal {v} \ righttarrow \ mathbb {z}, g (v_1)= g (v_2) $ . Esse comportamento é transitivo. O objetivo é rotular os grupos distintos a partir de zero (a ordem dos grupos é irrelevante). Eu sei que isso pode ser alcançado trivialmente com BFS ou DFS, mas eu quero evitar usar aqueles.

A ideia que eu inventei é para iterar sobre os vértices, passar por cima do bairro de 1 anel e criar um novo grupo toda vez que $ w ((u, v) ) Para qualquer uma das bordas e nem $ U $ nem $ v $ foram atribuídos a um grupo (por exemplo $ g (u)= g (v)= -1 $ ). Além disso, cada grupo é atribuído uma etiqueta, que é inicialmente igual ao índice do grupo: $ h: \ mathbb {n} \ rightarrow \ mathbb {n}, h (g (g u))= g (u) $ . Se em algum momento $ w ((x, y)) e $ w ((y, z)) , mas $ g (x) \ ne g (z) $ Defina $ h ( g (x)) \ esquerda \ min (H (g (g (x)), h (g (z)) $ e $ h (g (z)) \ de esquerda h (g (x)) $ . Após este procedimento, deve segurar: $ h (g (u))= h (g (v)), u, v \ in \ mathcal {v} $ se existe um caminho de $ u $ para $ v $ : $ \ pi= e_1, e_n $ tal que $ W (E_I) . O algoritmo que eu inventei ou perdi alguma coisa? Como é atualmente requer $ | \ mathcal {v} | $ memória Para cada matriz $ g, H $ . Existe uma maneira de otimizar isso ainda mais?

Answer 1

Como você destaca em Seus comentários , Uma abordagem razoável é excluir todas as bordas com peso $ \ GE T $ e, em seguida, calcularos componentes conectados do gráfico resultante (usando qualquer algoritmo padrão para computar componentes conectados).

Answer 2

Eu acredito que meu algoritmo está correto. Um esboço da prova é apresentado abaixo:

Existem 2 casos: ou $ u \ ne v \ in \ mathcal {v} $ precisa ser do mesmo grupo, ou eles precisam ser de Diferentes grupos (dependendo se existe um caminho entre eles, tal que $ w (e) ). É necessário mostrar que o algoritmo produz os grupos resultantes (a prova de cada caso será feita por contradição).

.

1. caso 1: Deixe $ u, v \ in \ mathcal {v} $ e há um caminho do recipiente de matemática $ u $ para $ v $ : $ \ pi= e_1, e_n $ tal que $ W (E_I) . Então $ h (g (u)) $ deve ser igual $ h (g (v)) $ para O algoritmo está correto.

2. suposição de algoritmo incorretamente: Suponha que este não seja o caso, e que $ u $ , $ V $ pertencem a diferentes grupos com base no resultado do algoritmo. Para simplicidade assumir que $ \ pi=pi_1, x, y, z, \ pi_2; \, x, y, z \ in \ mathcal {v} $ que todos os vértices da $ \ pi_1, x $ pertencem à $ h (g (u)) $ e Todos os vértices em $ y, z, \ pi_2 $ pertencem à $ h (g (v)) $ com base no algoritmo. O caso após a suposição acima será comprovado, mas deve ser claro que o mesmo manterá por indução mesmo se $ \ pi $ é dividido em mais grupos com base no algoritmo.

Prova por contradição: de (1), segue $ w (x, y) e de (2) Segue: $ h (g (x)) \ ne h (g (z)) $ . Da definição do algoritmo, segue que nunca divide grupos, e fundir dois grupos se $ w (x, y) mas $ h (g (x)) \ ne h (g (z)) $ . Como o algoritmo passa por todas as bordas, deve ter mesclado $ h (g (x)) $ e $ h (g (g ( z)) $ .

3. caso 2: $ u, v \ in \ mathcal {v} $ e não há caminho $ \ PI $ de $ u $ para $ v $ tal que $ W (E) , então $ h (g (u))= h (g (v)) $ .

4. suposição de algoritmo incorretamente: assumir $ h (g (u))= h (g (v)) $ .

Prova por contradição: tanto na criação do grupo quanto na mesclagem em grupo (as únicas duas maneiras para os vértices acabam no mesmo grupo), é necessário existir um caminho entre $ U $ e $ v $ tal que $ w (e) . (3) afirma que não existe tal caminho, então $ h (g (u)) \ ne h h (g (v)) $ .

Claramente a prova é bastante informal, então eu posso ter perdido alguma coisa. Vou deixar a questão aberta por um tempo, porque 1) alguém pode chegar a um algoritm melhor e mais otimizado, e 2) eu posso ter algum erro na minha prova.