Etiquetar grupos de vértices en un gráfico de manera eficiente sin BFS/DFS

Question

Tengo un gráfico con un conjunto de vértices. $\mathcal{V}$ y un conjunto de bordes $\mathcal{E}$.Existe un camino entre cada 2 vértices del gráfico.A cada borde hay un peso asociado $w(e), e \en \mathcal{E}$.Defino un umbral (global) $t$ tal que si $w((u,v)) <T$ los dos vértices $u,v \en \mathcal{V}$ están en el mismo grupo: $g \in \mathcal{V} ightarrow \mathbb{Z}, g(v_1) = g(v_2)$.Este comportamiento es transitivo.El objetivo es etiquetar los distintos grupos comenzando desde cero (el orden de los grupos es irrelevante).Sé que esto se puede lograr de manera trivial con BFS o DFS, pero quiero evitar usarlos.

La idea que se me ocurrió es iterar sobre los vértices, recorrer su vecindario de 1 anillo y crear un nuevo grupo cada vez que eso $w((u,v)) <T$ para cualquiera de los bordes y ninguno $u$ ni $v$ se le ha asignado un grupo (por ejemplo $g(u) = g(v) = -1$).Además, a cada grupo se le asigna una etiqueta, que inicialmente es igual al índice del grupo: $h:\mathbb{N} ightarrow \mathbb{N}, h(g(u)) = g(u)$.Si en algún momento $w((x,y)) <T$ y $w((y,z)) <T$, pero $g(x) e g(z)$ luego establece $h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$ y $h(g(z)) \flecha izquierda h(g(x))$.Después de este procedimiento debería contener: $h(g(u))=h(g(v)), u,v \in \mathcal{V}$ si existe un camino desde $u$ a $v$: $\pi = e_1,...,e_n$ tal que $w(e_i) <T$.¿El algoritmo que se me ocurrió es correcto o me perdí algo?Como está actualmente requiere $|\mathcal{V}|$ memoria para cada matriz $g,h$.¿Hay alguna manera de optimizar esto aún más?

Answer 1

Como resalta en sus comentarios , un enfoque razonable es eliminar todos los bordes con peso $ \ ge t $ , luego calculeLos componentes conectados del gráfico resultante (utilizando cualquier algoritmo estándar para computar componentes conectados).

Answer 2

Creo que mi algoritmo es correcto.A continuación se presenta un bosquejo de la prueba:

Hay 2 casos:cualquiera $u e v \in \mathcal{V}$ deben ser del mismo grupo, o deben ser de diferentes grupos (dependiendo de si existe un camino entre ellos de modo que $w(e) < T, \forall e \en \pi$).Es necesario demostrar que el algoritmo produce los grupos resultantes (la prueba para cada caso se hará por contradicción).

1. Caso 1:Dejar $u,v \en \mathcal{V}$ y hay un camino desde $u$ a $v$: $\pi=e_1,...,e_n$ tal que $w(e_i) <T$.Entonces $h(g(u))$ debe ser igual $h(g(v))$ para que el algoritmo sea correcto.

2. Supuesto de incorrección del algoritmo:Supongamos que este no es el caso y que $u$, $v$ pertenecen a diferentes grupos según el resultado del algoritmo.Por simplicidad supongamos que $\pi = \pi_1,x,y,z,\pi_2;\, x,y,z\in \mathcal{V}$ tal que todos los vértices de $\pi_1,x$ pertenece a $h(g(u))$ y todos los vértices en $y,z,\pi_2$ pertenece a $h(g(v))$ basado en el algoritmo.El caso que sigue el supuesto anterior será probado, pero debe quedar claro que lo mismo se cumplirá por inducción incluso si $\pi$ se divide en más grupos según el algoritmo.

Prueba por contradicción:De (1), se sigue $w(x,y)<T, w(y,z)<T$, y de (2) se sigue: $h(g(x)) e h(g(z))$.De la definición del algoritmo se deduce que nunca divide grupos y fusiona dos grupos si $w(x,y) < T, w(y,z)<T$ pero $h(g(x)) e h(g(z))$.Dado que el algoritmo recorre todos los bordes, debería haberse fusionado $h(g(x))$ y $h(g(z))$.

3. Caso 2: $u,v \en \mathcal{V}$ y no hay camino $\pi$ de $u$ a $v$ tal que $w(e) < T, \forall e \en \pi$, entonces $h(g(u)) = h(g(v))$.

4. Supuesto de incorrección del algoritmo:Asumir $h(g(u)) = h(g(v))$.

Prueba por contradicción:Tanto en la creación del grupo como en la fusión del grupo (las únicas dos formas en que los vértices terminan en el mismo grupo) es necesario que exista un camino entre $u$ y $v$ tal que $w(e)<T, \forall e \en \pi$.(3) afirma que no existe tal camino, entonces $h(g(u)) e h(g(v))$.

Claramente la prueba es bastante informal, por lo que es posible que me haya perdido algo.Dejaré la pregunta abierta por un tiempo, porque 1) a alguien se le puede ocurrir un algoritmo mejor y más optimizado, y 2) puede que tenga algún error en mi prueba.