| UBA - CienciaS http://ubacs.com.ar/ubacs/ |
|
| Programación lineal rala y caminos mínimos en un grafo http://ubacs.com.ar/ubacs/viewtopic.php?f=36&t=1934 |
Página 1 de 1 |
| Autor: | pterosaurio [ 27 Abr 2010, 19:15 ] |
| Asunto: | Programación lineal rala y caminos mínimos en un grafo |
(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.) |
|
| Página 1 de 1 | Todos los horarios son UTC - 3 horas |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|