Sesión Matemática DiscretaUn problema de conexión-desconexión en grafos y su resolución
Diego Barrios
Universidad Nacional del Litoral , Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El Hex es un juego de mesa abstracto para dos jugadores que se juega en un tablero en forma de rombo cubierto por hexágonos. Cada jugador tiene como objetivo conectar con sus fichas los lados opuestos del tablero que le corresponden, impidiendo al mismo tiempo que el rival logre su conexión. El juego garantiza siempre un ganador. La dinámica del Hex se puede representar a través de la teoría de grafos.
Inspirados en este juego, en este trabajo se define el siguiente problema: Dado un grafo conexo $G = (V,E)$ y dos pares de vértices $(R_1,R_2),(B_1,B_2)$, hallar el mínimo conjunto de aristas de $E$ que conectan el primer par de nodos y al mismo tiempo, al ser removidas, desconectan al otro par. Llamamos a este problema: problema de conexión-desconexión en grafos.
En primer lugar, se analiza la relación entre el problema planteado, y los problemas de grafos de mínimo corte y de mínimo camino entre dos vértices. Para estos dos últimos problemas existen algoritmos eficientes conocidos, para los cuales se han propuesto numerosas implementaciones y mejoras ([1]-[5]).
En segundo lugar, se propone un algoritmo para resolver el problema. Este algoritmo aplica los métodos conocidos de mínimo corte y mínimo camino para resolver subproblemas inducidos en cada iteración, con el objeto de determinar la solución al problema de conexión-desconexión de forma eficiente. Paralelamente, se formula un problema de programación entera binaria que representa el problema. Se aplican ambos abordajes para resolver varios casos de estudio ilustrativos, así como otros numerosos casos generados aleatoriamente. Se compara la performance de estas metodologías y se analizan las ventajas, alcances y limitaciones del algoritmo propuesto. Se plantean los aspectos que podrían mejorarse y que serán objeto de estudios futuros.
Finalmente, se analiza la aplicación de la metodología propuesta para diseñar una estrategia de juego del Hex.
Trabajo en conjunto con: Dra. Marian Marcovecchio (Universidad Nacional del Litoral).
Referencias
[1] Ford, L. R., Jr., and Fulkerson, D. R. Flows in networks. Princeton University Press, 1962.
[2] Edmonds, J. and Karp, R.M. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2): 248-264, 1972.
[3] Ibrahim, I.Y and Ibrahim M.I. Zebari, I.M.I. A Comprehensive Review of the Ford-Fulkerson Algorithm for Network Flow Problems. Asian Journal of Research in Computer Science 18 (3):335–344, 2025.
[4] Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271, 1959.
[5] Duan, R., Mao, J., Mao, X., Shu, X. and Yin, L. Breaking the sorting barrier for directed single source shortest paths [Preprint]. arXiv. https://arxiv.org/abs/2504.17033, 2025.