Teoría de gráficos: dividir un gráfico

Tengo este problema. Tengo un gráfico de n nodos que quiero dividir en dos subgrafos de x nodos y n-x nodos sujetos a la restriccin de que el nmero de bordes restantes se maximiza (o minimiza el nmero de bordes que se cortan).Teoría de gráficos: dividir un gráfico

No estoy seguro si eso tiene sentido. No es una persona de la teoría de grafos, pero esta es la versión abstracta de mi problema. ¿Qué algoritmos debería ver para ayudarme?

esto no es un problema de tarea. ¡Problema interesante, aunque creo!

Mi plan es implementar en C.

Fuente

2012-04-17 JoshDG

¿Tiene x un parámetro o simplemente está buscando 2 sub graphes? Si x no es un parámetro, ¿no buscarías el nodo con el menor número de aristas y lo cortarías del gráfico? – brianestey

sí ... lo siento, debería haber dejado eso más claro. Digamos que x es 10 y el total de nodos es 25. Quiero dos gráficos, uno con 10 nodos y uno con 15 ... al "cortar" el menor número de aristas. – JoshDG

Definitivamente un problema interesante. En realidad, mi primera suposición sobre la búsqueda de un solo nodo es incorrecta: se me ocurrió un gráfico donde eso no es cierto. ¡Buena suerte para encontrar una solución! – brianestey

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

Fuente

2012-04-17 12:42:38 uty

Esta es la respuesta. –

Yikes. Probablemente demasiado avanzado para un científico no informático. ¿Sería mejor utilizar un algoritmo genético si x es pequeño? Simplemente tome un grupo de conjuntos aleatorios de x = 10 y, para los casos en que el gráfico se particione en exactamente dos partes, tome el 10% superior en términos de cortes mínimos, y luego muévalos para un grupo de generaciones. ¿Crees que eso podría ser efectivo? O, depende completamente del conjunto de datos. Creo que puedo intentarlo. – JoshDG

La búsqueda local es bastante fácil de implementar: simplemente comience con un corte y trate de mejorarlo haciendo pequeños cambios. La computación de autovectores no es tan mala pero requiere cierto conocimiento matemático. La programación de enteros es difícil, pero hay bibliotecas gratuitas. No me gustan los algoritmos genéticos para los problemas combinatorios, pero podrían ser mejores que la búsqueda local si estás dispuesto a lanzarles suficientes ciclos. – uty

Quizás 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 excede el número de la mejor solución, entonces cancelamos este y retrocedemos.

Dado el conjunto completo de los nodos S, permiten P y P' sean setsuts de nodos, inicialmente vacío, y K por el número de bordes cortados, inicialmente 0.
Let S *, K * sea el la mejor solución conocida y su número de bordes cortados, con K * inicialmente infinito.
Escoja un nodo N para comenzar, y asignarla a S.
Para cada nodo M no asignada:
1. Assign M a S', y añadir el número de aristas de M a nodos en S a K.
2. Si K> K *, entonces ninguna solución basada en este batirá mejor, así que asigne M a S.
3. If | S | > X, entonces el set ha crecido demasiado; volver hacia atrás.
4. De lo contrario, Recurse de 4.
Si todos los nodos están asignados y K < K *, entonces que S * = S y K * = K.

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

Fuente

2012-04-17 06:08:15 Edmund

básicamente está buscando una versión modificada del problema de corte mínimo.

Una forma sería modificar karger's algorythm En el proceso de Karger contratas vértices a lo largo de los bordes aleatorios hasta que terminas con solo dos vértices, los bordes restantes representan el corte. Como es aleatorio, solo haz esto muchas veces y mantén la solución con los bordes más pequeños en el corte.

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

Fuente

2012-04-17 06:56:57 AntonioD

Los problemas de corte mínimo no tienen 'x' [cantidad de vértices en uno de los lados del corte] fijados, y tienen' fuente' y 'sumidero 'específico. Si tiene una reducción en su mente para reducir el problema, por favor agréguelo a su respuesta. – amit

Creo que algún tipo de modificación en Karger podría resolver este problema. No existe un sumidero ni una fuente en los problemas de corte mínimo per se, es solo que algunos algoritmos reducen el problema a uno de flujo máximo. Editaré la respuesta si puedo encontrar una buena modificación para karger's que maneja la caja x fija (hay una manera obvia, pero no estoy seguro de que arroje resultados correctos) – AntonioD

Teoría de gráficos: dividir un gráfico

Respuesta

Cuestiones relacionadas