ciclo de peso medio mínimo

En teoría de grafos , un ciclo de peso medio mínimo es un ciclo cuyo peso promedio (peso total dividido por la longitud) es el menor 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 embebidos ^{[ 2 ]} y diseño de chips lógicos. ^{[ 3 ]}

Definiciones

Sea G = (V,E) un grafo dirigido en el que cada arista tiene un peso (positivo o negativo). El peso de cualquier camino o ciclo p = (e ₁ ,...,e _k ), es la suma de los pesos de las aristas: w(p) = w(e ₁ ) + ... + w(e _k ). El peso medio de p es el peso de p dividido por el número de aristas que lo componen: w(p)/len(p).

El peso medio mínimo de un ciclo 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.

Algoritmos

Lawler presentó un algoritmo para calcular un ciclo de peso medio mínimo utilizando O(log |V| ) llamadas a un algoritmo para resolver el problema del ciclo negativo . ^{[ 4 ]} Existe un algoritmo que se ejecuta en tiempo O( |V||E| ), por lo que el tiempo de ejecución total del algoritmo de Lawler es O( |E||V| log |V| ).

El algoritmo de Karp

Karp ^{[ 1 ]} presentó una caracterización del peso medio mínimo del ciclo y presentó un algoritmo que se ejecuta en tiempo O( |V||E| ). Se puede utilizar un algoritmo análogo para encontrar un ciclo de peso medio máximo.

Sea G un grafo dirigido cualquiera y sea s un vértice fijo en G. Para cada entero no negativo k y cada vértice v en G, definimos H _k (v) como el costo máximo de un camino de longitud k desde s hasta 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

(*) $\max _{v\in V}\min _{0\leq k\leq n-1}{\frac {H_{n}(v)-H_{k}(v)}{nk}}$

Demostración . Basta con demostrar el lema para el caso en que el peso medio máximo del ciclo sea igual a 0. Esto se debe a que añadir un peso constante a cada arista añade la misma constante tanto al coste 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 igual a 0, pero ningún ciclo con un coste positivo.

Primero demostramos que (*) es como máximo 0. Como G no tiene ciclos de costo positivo, para cada nodo v, existe un camino de costo máximo de longitud menor que n desde s hasta 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 min 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 (*) también es como máximo 0.

Ahora demostramos que (*) es al menos 0. G tiene un ciclo de costo cero; sea w un nodo en ese ciclo. Sea P ₀ un camino de costo máximo de s a w. Para cada t >= 1, sea P _t una concatenación de P ₀ con t copias del ciclo; como el costo de P _t es igual al costo de P ₀ , también es un camino de costo máximo de s a w. Cada prefijo de un camino de costo máximo es también un camino de costo máximo de s a su punto final. Cuando t es suficientemente grande, P _t tiene un prefijo de longitud n; es un camino de costo máximo de s a algún nodo w'. Entonces H _n (w') >= H _k (w') para todo k, por lo que la expresión dentro del min 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 (*) también es al menos 0.

Por lo tanto, cuando el costo medio máximo del ciclo es 0, (*) es igual a 0, lo cual es suficiente para completar la demostración.

Es posible calcular H _k usando programación dinámica en tiempo O(|E||V|); luego es posible encontrar el peso máximo del ciclo medio usando (*). El ciclo en sí se puede encontrar de la siguiente manera:

Encuentra el valor máximo de v y el valor mínimo de k en (*).
Dado que el resultado para este v y este k es finito, tanto H _n (v) como H _k (v) son finitos. Esto significa que existe un camino de peso máximo de longitud n desde s hasta v, y un camino de peso máximo de longitud k desde s hasta v. Por lo tanto, el camino de longitud n contiene un ciclo de longitud nk; este es el ciclo de peso medio máximo.

Chaturvedi y McConnell ^{[ 5 ]} identificaron un error en el algoritmo de Karp para construir un ciclo que alcanzara el peso medio mínimo. Presentaron un algoritmo corregido.

Nuevos algoritmos

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 del equilibrio mínimo : encontrar una función potencial tal que las holguras de todas las aristas estén óptimamente equilibradas. Ambos problemas pueden resolverse mediante un algoritmo paramétrico de ruta más corta . Demuestran que este algoritmo puede utilizarse para resolver variantes más generales de estos problemas, con restricciones relevantes para la optimización de la programación del reloj de un chip lógico.

Véase también

Ciclo negativo

Referencias

1 2 Karp, Richard M. (1978-01-01). "Una caracterización de la media cíclica mínima en un digrafo" . Matemáticas Discretas . 23 (3): 309– 311. doi : 10.1016/0012-365X(78)90011-0 . ISSN 0012-365X .
1 2 Dasdan, A.; Gupta, RK (1998). "Algoritmos más rápidos de ciclo medio máximo y mínimo para el análisis del rendimiento del sistema". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 17 (10): 889– 899. doi : 10.1109/43.728912 .
1 2 Albrecht, Christoph; Korte, Bernhard; Schietke, Jürgen; Vygen, Jens (2002-11-15). "Ciclo de peso medio máximo en un digrafo y minimización del tiempo de ciclo de un chip lógico" . Matemáticas Aplicadas Discretas . 123 (1): 103– 127. doi : 10.1016/S0166-218X(01)00339-0 . ISSN 0166-218X .
↑ v. Golitschek, M. (1982-02-01). "Ciclos óptimos en grafos doblemente ponderados y aproximación de funciones bivariadas mediante funciones univariadas" . Numerische Mathematik . 39 (1): 65–84 . doi : 10.1007/BF01399312 . ISSN 0945-3245 .
↑ Chaturvedi, Mmanu; McConnell, Ross M. (2017-11-01). "Una nota sobre cómo encontrar el ciclo medio mínimo" . Information Processing Letters . 127 : 21–22 . doi : 10.1016/j.ipl.2017.06.007 . ISSN 0020-0190 .

[:0-1] 1 2 Karp, Richard M. (1978-01-01). "Una caracterización de la media cíclica mínima en un digrafo" . Matemáticas Discretas . 23 (3): 309– 311. doi : 10.1016/0012-365X(78)90011-0 . ISSN 0012-365X .

[:1-2] 1 2 Dasdan, A.; Gupta, RK (1998). "Algoritmos más rápidos de ciclo medio máximo y mínimo para el análisis del rendimiento del sistema". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 17 (10): 889– 899. doi : 10.1109/43.728912 .

[:2-3] 1 2 Albrecht, Christoph; Korte, Bernhard; Schietke, Jürgen; Vygen, Jens (2002-11-15). "Ciclo de peso medio máximo en un digrafo y minimización del tiempo de ciclo de un chip lógico" . Matemáticas Aplicadas Discretas . 123 (1): 103– 127. doi : 10.1016/S0166-218X(01)00339-0 . ISSN 0166-218X .

[4] v. Golitschek, M. (1982-02-01). "Ciclos óptimos en grafos doblemente ponderados y aproximación de funciones bivariadas mediante funciones univariadas" . Numerische Mathematik . 39 (1): 65–84 . doi : 10.1007/BF01399312 . ISSN 0945-3245 .

[5] Chaturvedi, Mmanu; McConnell, Ross M. (2017-11-01). "Una nota sobre cómo encontrar el ciclo medio mínimo" . Information Processing Letters . 127 : 21–22 . doi : 10.1016/j.ipl.2017.06.007 . ISSN 0020-0190 .

[ 4 ]

[ 5 ]