Tema

Programación lineal rala y caminos mínimos en un grafo

0 respuestas 4067 visitas 2010-04-27

#1 pterosaurio 2010-04-27 22:15

(Esto iría en una sección investigación operativa o AED3, que no hay.)

Sea \(G=(V,E)\) un grafo finito simple dirigido con una función \(a : E \to \mathbb R\). Un modelo del grafo es una función \(x : V \to \mathbb R\) tal que \(x(i)-x(j)\leqq a(ji)\) para todo \(ji\in E\). Demostrar las siguientes afirmaciones:

Existe un modelo si y sólo si el grafo no tiene ciclos negativos pesando las aristas con \(a\).
Una implicación es obvia, porque si hay un ciclo negativo \(c_1,\ldots,c_n\) y un modelo tenés \(0=x(c_2)-x(c_1)+\cdots+x(c_n)-x(c_{n-1})+x(c_1)-x(c_n)\leqq\) \(a(c_1c_2)+\cdots+a(c_{n-1}c_n)+a(c_nc_1)<0\), lo cual es absurdo. Veamos la otra implicación: formamos \(G'\) con vértices \(V\cup\{u\}\) para un \(u\not\in V\) y con aristas \(E\cup \bigcup_{v\in V}uv\); extendemos \(a\) con \(a(uv)=0\) para cada \(v\in V\). Como no hay ciclos negativos en \(G\) por hipótesis, no va a haber ciclos negativos en \(G'\) porque las cosas que agregamos no agregan nuevos ciclos; entonces existen caminos de \(u\) a todos los vértices con peso mínimo; sea \(d : V \to \R\) la función distancia de \(u\) a cada \(v\in V\). Tenemos \(d(i)\leqq d(j)+a(ji)\) por desigualdad triangular así que \(d(i)-d(j)\leqq a(ji)\). Luego \(d\) es un modelo. Así que existe un modelo, que es lo que había que demostrar.
Supongamos que hay un modelo. Sean \(i,j\in V\) tales que hay un camino mínimo \(p\) de \(j\) a \(i\). Entonces hay un modelo \(x\) que maximiza \(x(i)-x(j)\) y \(x(i)-x(j)=a(p)\).
Supongamos que hay un modelo con \(x(i)-x(j)>a(p)\). Sea \(i,p_1,\ldots,p_n,j\) el camino \(p\). Tenemos \(a(p)<x(i)-x(j)=x(p_1)-x(j)+x(p_2)-x(p_1)+\cdots+x(i)-x(p_n)=\) \(a(jp_1)+a(p_1p_2)+\cdots+a(p_ni)=a(p)\), que implica \(a(p)<a(p),\) absurdo. Veamos que existe un modelo con \(x(i)-x(j)=a(p)\). Si \(ij\in E\) cambiamos \(a(ij)\) por \(\text{m\'in}\{a(ij),-a(p)\}\); si no, agregamos \(ij\) a \(E\) y ponemos \(a(ij)=-a(p)\). Veamos que hay un modelo. Por lo anterior basta ver que no aparecen ciclos negativos. Como asumimos que hay un modelo, si hay un ciclo negativo tiene que involucrar a la arista \(ij\). Entonces el ciclo es \(ij\) más un camino \(p'\) de \(j\) a \(i\) y tenemos \(a(ij)+a(p')<0\). Ahora por definición de \(p\) tenemos \(a(p)\leqq a(p')\) así que \(a(ij)+a(p)\leqq a(ij)+a(p')<0\). Si \(a(ij)=-a(p)\) resulta que \(a(ij)+a(p)=0\), lo cual es una contradicción; luego \(a(ij)\) vale lo que valía antes en el grafo, pero \(a(ij)+a(p)<0\) muestra que el ciclo era negativo antes de cambiar \(a(ij)\), lo cual se asumía falso. Entonces no hay ciclos negativos y hay un modelo con el \(a(ij)\) cambiado como dijimos. Pero entonces \(x(j)-x(i)\leqq a(ij)\leqq -a(p)\) y \(x(i)-x(j)\geqq a(p)\). Como vimos que \(x(j)-x(i)\leqq a(p)\) resulta que \(x(j)-x(i)=a(p)\), que es lo que había que demostrar.

La conclusión tiene que ser que podemos resolver el problema lineal

\begin{array}{rrcl} \text{maximizar} & x_i - x_j & & \\ \text{dado} & x_{i_1}-x_{j_1}&\leqq& a_{i_1j_1} \\ & & \vdots & \\ & x_{i_m}-x_{j_m}& \leqq &a_{i_mj_m} \\ & x_1,\ldots,x_n&\in&\mathbb R\end{array}

en tiempo \(O(nm)\). Usamos Bellman Ford dos veces, primero para sacar el camino mínimo de \(j\) a \(i\) y luego para ver que no tiene ciclos negativos, agregando el vértice \(u\) con aristas a todos los demás con peso cero.

(Estoy usando el foro como google docs con latex, pero bueno, capaz que incidentalmente le interesa a alguien.)

Firma

"En el principio existía la Palabra, y todo era texto." (San Juan Derrida)