Sanket y la rosa: ¿es probable encontrarnos?

Ponente(s): Sinuhe Alex Quintero Carbajal

Sanket es un joven que se encuentra varado en los archipiélagos, lugar conformado por islas y puentes. Él desea reunirse con su novia, la cuál se ubica en otra isla. Por otra parte en algunos puentes se hallan rosas tiradas; el plan de Sanket es recoger una rosa y llevársela a su amada. Sin embargo, los puentes son inestables y una vez que los cruza estos caen inmediatamente. Dadas estas dificultades ¿será factible que se encuentren?. El problema fue propuesto por un usuario en el sitio web "hacker earth", liga actualmente deshabilitada, y posteriormente fue retomado por la Olimpiada Mexicana de Informática en una plática. En esta ponencia se busca ahondar en la existencia de soluciones mediante teoría, relativamente robusta, de redes. A la red, que modela el problema, se le puede asociar un problema de flujo máximo/cortadura mínima y ser resuelto con Ford-Fulkerson. Sucede que cada cadena aumentante que resulta del algoritmo de Ford-Fulkerson equivale a una cadena arco-ajena entre Sanket y su novia. Tras terminar el algoritmo se habrán encontrado la cantidad máxima de caminos entre él y su novia (sin necesariamente cumplir la condición de la rosa). De aquí, se analizan las cadenas arco-ajenas obtenidas, mediante criterios que involucran resolución de rutas más cortas, para determinar si hay o no solución; en el caso afirmativo se indica la construcción de la solución por medio de nuevas combinaciones de cadenas.