Emparejamientos estables

Abstract

RESUMEN: En este trabajo se pretende mostrar al lector diferentes tipos de problemas de asignación, cuyas aplicaciones se siguen utilizando a día de hoy en la vida real. Se comienza introduciendo una serie de nociones y resultados importantes de la Teoría de Emparejamientos y su relación con la Teoría de Grafos, en particular bipartitos. A continuación, se trata el primero de los problemas de asignación bipartitos del trabajo, el Problema del Matrimonio Estable, donde se estudiará el concepto de la estabilidad en un emparejamiento, así como el Algoritmo de Gale-Shapley que lo resuelve. Este primer problema da lugar a una extensión bipartita que también se tratará en este texto, el Problema de los Hospitales y Residentes, también conocido como el Problema de la Asignación de Estudiantes a Universidades. Por último, se desarrolla una extensión no bipartita, el Problema de los Compañeros de Habitación, en el cual se presentará el Algoritmo de Irving que ofrece una solución al problema en caso de que esta exista.

ABSTRACT: This paper aims to show the reader different types of assignment problems whose applications are still used actually in real life. It begins by introducing several important notions and results of the Matching Theory and its relationship with the Graph Theory, in particular bipartite. Next, we discuss the first of the bipartite assignment problems of the work, the Stable Marriage Problem, where the concept of stability in a match will be studied, as well as the Gale-Shapley Algorithm that solves it. This first problem gives rise to an bipartite extension that will also be discussed in this text, the Hospitals and Residents Problem, also known as the Assigning Students to Universities Problem. Finally, a non bipartite extension is developed, the Rommates Problem, in which the Irving Algorithm will be presented, which offers a solution to the problem if it exists.