¿Invariante para el algoritmo de Gale-Shapley (algoritmo del ritual de apareamiento)?

Question

Encontré la siguiente invariante para el algoritmo Mating Ritual ( Lehman, Leighton y Meyer, Matemáticas para la informática , §6.4) mientras se revisa el material de lectura del MIT:

Definición . Dejemos que $P$ sea el predicado: Para cada mujer, $w$ y todos los hombres, $m$ Si $w$ se tacha $m$ de la lista, entonces $w$ tiene un pretendiente al que ella prefiere sobre $m$ .

Lema : $P$ es una invariante para el Ritual de Ritual.

Prueba . Por inducción en el número de días.
Caso base : Al principio (es decir, al final del día 0), todas las mujeres están en todas las lista-ninguna ha sido tachada y por tanto $P$ es una verdad vacía.
Paso inductivo : Supongamos que $P$ es cierto al final del día $d$ y que $w$ ser una mujer que ha sido tachada de un hombre $m$ de la lista del día $d + 1$ .
Caso 1: $w$ fue tachado $m$ de la lista del día $d + 1$ . Entonces, $w$ debe tener un pretendiente que ella prefiere el día $d + 1$ .
Caso 2: $w$ fue tachado $m$ de la lista antes del día $d + 1$ . Desde $P$ es cierto al final del día $d$ Esto significa que $w$ tiene un pretendiente que prefiere $m$ el día $d$ . Por lo tanto, ella tiene el mismo pretendiente o alguien que ella prefiere mejor al final del día $d + 1$ .

En ambos casos, P es verdadera al final del día $d + 1$ y así $P$ debe ser una invariante

No puedo entender por qué el autor considera el caso 2.
En el paso inductivo primero estamos asumiendo lo siguiente:

"Deja que $w$ ser una mujer que ha sido tachada de hombre $m$ de la lista al final del día del día $d + 1$ "

Y luego, en el caso 2, estamos considerando la posibilidad de $w$ que se cruzan del día anterior a $d+1$ . Me parece contradictorio. ¿Podría entenderlo?

Answer 1

Queremos demostrar que en cualquier punto del algoritmo, si es cierto que $m$ ha tachado $w$ de su lista en algún momento del pasado, entonces $w$ tiene un pretendiente que le gusta más que $m$ .

Así que la suposición al principio del paso inductivo es simplemente describir la situación al final del día $d+1$ : suponemos que, en este punto del algoritmo, $w$ aparece el nombre de $m$ con una línea que lo atraviesa.

Entonces los dos casos están considerando diferentes posibilidades de cuándo se produjo el cruce:

1. El día actual, el día $d+1$ es, de hecho, el día en que $w$ El nombre de la mujer fue tachado. Entonces, deberíamos ver cómo sucedió esto: $w$ se tacha el nombre de la mujer porque rechaza $m$ y $w$ rechaza $m$ porque ha conocido a un mejor pretendiente $m'$ .
2. En realidad, $w$ se tachó el nombre de un día anterior (y se mantiene tachado el día $d+1$ (porque una vez que se tacha un nombre, se queda tachado para siempre). En este caso, se aplica la hipótesis inductiva, y ahí tienes el resto de la prueba.