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

Sea un grafo finito simple dirigido con una función . Un modelo del grafo es una función tal que para todo . Demostrar las siguientes afirmaciones:

1. Existe un modelo si y sólo si el grafo no tiene ciclos negativos pesando las aristas con .


2. Supongamos que hay un modelo. Sean tales que hay un camino mínimo de a . Entonces hay un modelo que maximiza y .


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

en tiempo .


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