En teoría de grafos , un ciclo de peso medio mínimo es un ciclo cuyo peso medio (peso total dividido por la longitud) es el más pequeño entre todos los ciclos del grafo. [1] Un problema análogo es el ciclo de peso medio máximo . Estos problemas tienen aplicaciones en sistemas integrados [2] y en el diseño de chips lógicos. [3]
Sea G = (V,E) un grafo dirigido en el que cada arista tiene un peso (positivo o negativo). El peso de cualquier trayectoria o ciclo p = (e 1 ,...,e k ), es la suma de los pesos de las aristas: w(p) = w(e 1 ) + ... + w(e k ). El peso medio de p es el peso de p dividido por el número de aristas que contiene: w(p)/len(p). [ cita requerida ]
El peso medio del ciclo mínimo en G es el mínimo, sobre todos los ciclos dirigidos p en G, de w(p)/len(p). Un ciclo de peso medio mínimo es cualquier ciclo con el peso medio mínimo. [ cita requerida ]
Lawler presentó un algoritmo para calcular un ciclo de peso medio mínimo utilizando llamadas O(log |V| ) a un algoritmo para resolver el problema del ciclo negativo . [4] Existe un algoritmo que se ejecuta en un tiempo O( |V||E| ), por lo que el tiempo de ejecución total del algoritmo de Lawler es O( |E||V| log |V| ).
Karp [1] presentó una caracterización del peso medio del ciclo mínimo y presentó un algoritmo que se ejecuta en el tiempo O( |V||E| ). Se puede utilizar un algoritmo análogo para encontrar un ciclo de peso medio máximo.
Sea G cualquier grafo dirigido y sea s un vértice fijo en G. Para cada entero no negativo k y cada vértice v en G, defina H k (v) como el costo máximo de un camino de longitud k desde s a v; si no existe tal camino, entonces H k (v) = menos infinito.
El lema principal dice que el peso máximo del ciclo medio de G es igual a
(*)
Demostración . Es suficiente demostrar el lema para el caso en que el peso medio máximo del ciclo sea igual a 0. Esto se debe a que al agregar un peso constante a cada arista se agrega la misma constante tanto al costo medio máximo del ciclo como a la expresión en (*).
Supongamos que el peso medio máximo del ciclo es 0. Entonces hay un ciclo con un coste exactamente 0, pero no hay ciclos con un coste positivo.
Primero demostramos que (*) es como máximo 0. Como G no tiene ciclos de costo positivo, para cada nodo v, hay un camino de costo máximo de longitud menor que n desde s a v. Sea k v la longitud de este camino de costo máximo. Entonces H kv (v) >= H n (v), por lo que la expresión dentro del mínimo en (*) es como máximo 0 cuando k = k v . Como k v <= n-1, el mínimo en (*) es como máximo 0. Como esto se cumple para cada nodo v, el máximo en (*) es como máximo 0 también.
Ahora demostramos que (*) es al menos 0. G tiene un ciclo de coste cero; sea w un nodo de ese ciclo. Sea P 0 una ruta de coste máximo de s a w. Para cada t >= 1, sea P t una concatenación de P 0 con t copias del ciclo; como el coste de P t es igual al coste de P 0 , también es una ruta de coste máximo de s a w. Todo prefijo de una ruta de coste máximo es también una ruta de coste máximo de s a su punto final. Cuando t es suficientemente grande, P t tiene un prefijo de longitud n; es una ruta de coste máximo de s a un nodo w'. Entonces H n (w') >= H k (w') para todo k, por lo que la expresión dentro del mínimo en (*) es al menos 0 para todo k, por lo que el mínimo en (*) es al menos 0. Tomando v=w' en el máximo se muestra que el máximo en (*) es al menos 0 también.
Por lo tanto, cuando el coste medio máximo del ciclo es 0, (*) es igual a 0, lo cual es suficiente para completar la prueba.
Es posible calcular H k mediante programación dinámica en tiempo O(|E||V|); luego es posible encontrar el peso medio máximo del ciclo utilizando (*). El ciclo en sí se puede encontrar de la siguiente manera:
Dasdan y Gupta estudian el ciclo de peso medio máximo y presentan un algoritmo que es demostrablemente siempre más rápido que el algoritmo de Karp. [2]
Albrecht, Korte, Schietke y Vygen [3] relacionan el problema del ciclo de peso medio máximo con el problema de equilibrio mínimo : encuentran una función potencial [ necesitamos desambiguación ] tal que las "holguras" de todos los bordes estén óptimamente equilibradas. Ambos problemas se pueden resolver mediante un algoritmo de ruta más corta paramétrica . Demuestran que la ruta más corta paramétrica se puede utilizar para resolver variantes más generales de estos problemas, con restricciones que son relevantes para optimizar la programación del reloj de un chip lógico.
