Ciclo de peso máximo en un gráfico

Question

Dado un grafo ponderado (dirigido o no dirigido) Necesito encontrar el ciclo de la gráfica con el peso máximo.

El peso de un ciclo es la suma del peso de los bordes de la gráfica.

Puede ser cualquier ciclo, no solo ciclo de base para lo que puede

• encontrar todo el ciclo de base (ver Algoritmos Identificar a todas las bases de ciclo en un gráfico no dirigido )
• calcular el peso de cada ciclo de base y encontrar el máximo

I podría tratar de enumerar todos los ciclos de la gráfica y luego calcular el máximo pero el número total de ciclos puede ser muy grande (si la gráfica es completa entonces cualquier secuencia de vértices en el que el primero y último son idénticos es un ciclo ).

¿Tiene alguna idea de encontrar ese ciclo máximo de peso sin la enumeración de todos los ciclos?

Si necesita hipótesis sobre la gráfica (positivos pesos, por ejemplo) por favor, indica.

Answer 1

Este es NP-duro.

Ciclo hamiltoniano problema puede reducirse a esto.

Dado un gráfico para el cual necesitamos comprobar si existe un ciclo de Hamilton o no, el peso de asignación 1 a cada borde.

Ahora ejecute el algoritmo para obtener el máximo ciclo de peso. Si el peso es

Answer 2

Si usted puede encontrar el camino ponderada mínima en su caso específico, simplemente revertir los signos de todos los pesos y aplicar el algoritmo. Por supuesto que están haciendo algunas suposiciones no porque el argumento de Morón es correcto (sin doble sentido). Los supuestos que están haciendo los pesos podrían ser positivos o no hay ciclos de peso negativo. Creo que se debe hacer un esfuerzo para establecer que en lugar de dejar la búsqueda de personas en el espacio infinito de posibles supuestos. En cuanto a los resultados de dureza, esto también es difícil de aproximar en una serie de manera, visita este documento . El mismo documento contiene varios resultados positivos para importantes tipos de gráficos, pero se ocupa de los caminos más largos sin ponderar así que yo creo que la mayoría de los algoritmos en el papel no directamente ayuda en su caso. Si busca "ciclos pesados" se dará cuenta de una serie de artículos interesantes, pero son más de carácter matemático. Si sus pesos son números enteros pequeños (hasta un polinomio en el tamaño del gráfico), se puede tratar de reemplazar a todas las aristas con una ruta no ponderado para reducir el problema al caso no ponderado. Espero que esto ayude a cierto grado, pero es posible que tenga un problema de investigación abierta en sus manos.