Prog3: Primer Parcial 2019 Ejercicios 1 y 3

Buenas, la solución de este parcial me generó un par de dudas.

En primer lugar, para el ejercicio 1 la solución menciona la propiedad de que en $S^*$ , el resultado de G-S con los hombres proponiendo, se cumple que $(m,w) \in S^* \iff w = \text{best}(m) \text{ y worst}(w)=m$ y analogamente para el caso de las mujeres proponiendo, y que como para ambos casos de proponentes el resultado $S^*$ es el mismo entonces existe un único emparejamiento estable. No entiendo cómo se lleva esta propiedad que solo cumple el algoritmo G-S a afirmar que el emparejamiento estable es único. Por qué no puede existir un emparejamiento estable, hallado de alguna manera distinta a G-S, que sea distinto?

En segundo lugar, no entiendo la solución de la parte (c) del ejercicio 3. Pues en la letra menciona que debe usarse un comodín que permite que cualquier arista valga cero, pero la solución no menciona usarlo en ninguna parte.

Podés acceder al parcial aquí.

Re: Primer Parcial 2019 Ejercicios 1 y 3

de Fernando Fernandez - lunes, 23 de septiembre de 2024, 05:58

Hola Ezequiel.
Con respecto al primer ejercicio. El concepto de pareja válida no está restringido a los emparejamientos estables obtenidos mediante G-S (que serían solo dos, uno cuando los proponentes son los del conjunto M, y otro cuando son del conjunto W), sino a todos, obtenidos mediante cualquier método. Entonces, si la mejor pareja, de todas las válidas, es la misma que la peor, de todas las válidas, se concluye que hay una única pareja válida, y, como esto se cumple para cada w, por definición de pareja válida, hay un único emparejamiento estable.

Con respecto al otro, el tercero. El comodín se usa en el paso 4.

$d_u$ es la distancia desde s hasta u y

$d'_v$ es la distancia desde v hasta t. Al tomar la suma

$d_u + d'_v$ como la distancia de un camino entre s y t se está asignando longitud 0 a la arista (u,v).

Saludos,
Fernando