algorithm - representacion - Teoría de los gráficos: dividir un gráfico

representacion grafica de operaciones con 3 conjuntos

Question

Tengo este problema Tengo una gráfica de n nodos que quiero dividir en dos subgrafos de x nodos y nx nodos sujetos a la restricción de que el número de bordes restantes está maximizado (o minimizar el número de bordes que se cortan).

No estoy seguro si eso tiene sentido. No es una persona de teoría de grafos, pero esta es la versión abstracta de mi problema. ¿Qué algoritmos debo mirar que me puedan ayudar?

Esto NO es un problema de tarea. Problema interesante aunque creo!

Planeo implementar en C.

Answer 1

Básicamente estás viendo una versión modificada del problema min-cut.

Una forma sería modificar el algoritmo de Karger. En algo de Karger, usted contrae vértices a lo largo de bordes al azar hasta que termine con solo dos vértices, los bordes restantes representan el corte. Ya que es aleatorio, simplemente hace esto muchas veces y mantiene la solución con el menor número de bordes en el corte.

En la versión modificada, una vez que un vértice se haya colapsado x veces, usted podría dejar de colapsar y contar los bordes salientes (esto sería el corte en su caso), hágalo una cantidad adecuada de veces y tendrá una solución. La parte difícil es calcular cuántas veces repetir los cálculos para aumentar la confianza hasta un límite satisfactorio.

Answer 2

El caso especial donde x = n - x se llama el problema de bisección mínima y es NP-duro. Esto hace que tu problema NP-duro también. Hay varias heurísticas descritas en el artículo de Wikipedia sobre partición de gráficos , incluida la búsqueda local (por ejemplo, comenzar con un corte aleatorio e intercambiar repetidamente pares de vértices que disminuyen el tamaño del corte) y métodos espectrales (por ejemplo, calcular y establecer un umbral para el segundo vector propio). ). Si n es pequeño, la programación de enteros también es una posibilidad.

Answer 3

Tal vez una primera búsqueda en profundidad sobre los nodos. Asignamos nodos de uno en uno y contamos el número de cortes hasta el momento. Si ese número supera el número de la mejor solución, abortamos este y retrocedemos.

1. Dado el conjunto completo de nodos S, sea P y P ''los conjuntos de nodos, inicialmente vacíos, y K por el número de bordes cortados, inicialmente 0.
2. Sea S *, K * la mejor solución conocida y su número de bordes cortados, con K * inicialmente infinito.
3. Elija un nodo N para comenzar y asignarlo a S.
4. Para cada nodo no asignado M:
   1. Asigne M a S '', y agregue el número de bordes de M a nodos en S a K.
   2. Si K> K *, entonces ninguna solución basada en ésta vencerá a la mejor, así que asigne M a S.
   3. Si | S | > X, entonces el conjunto ha crecido demasiado grande; volver hacia atrás.
   4. De lo contrario, repetir de 4.
5. Si todos los nodos están asignados y K <K *, entonces deje S * = S y K * = K.

He estado imaginando esto como un algoritmo de tipo Prolog, pero hacerlo en C no debería ser demasiado difícil. Retroceder simplemente significa desasignar el último nodo asignado.