El algoritmo Húngaro

Question

En la lectura de la prueba de la húngara algoritmo para el problema de la asignación de un peso a bigraph, yo no podía entender por qué el algoritmo termina. En el algoritmo que hemos de elegir una cubierta (es decir, las etiquetas de los vértices de la bigraph: $u_1\cdots u_n$, $v_1,\cdots v_n$ con $u_i+v_j\ge $peso de una arista $x_iy_j\forall i,j$) y de seguir ajustando hasta que la igualdad subgrafo (la que abarca subgrafo de $K_{n,n}$, cuyos bordes son pares $x_iy_j$ tal que $u_i+v_j=$peso de $x_iy_j$) tiene un perfecto maridaje. Mi pregunta es después de cada ajuste, ¿por qué el costo de la cubierta de la $\sum(u_i+v_i)$ reducir?

(Asumimos que los pesos son todos los números enteros).

Gracias.

Answer 1

Deje que los dos conjuntos de vértices ser$X$$Y$. Si la igualdad subgrafo no tiene un perfecto maridaje, que debe violar Hall del matrimonio condición, por lo que hay algunos $X'\subseteq X$ adyacente a menos de $|X'|$ vértices en $Y$. Deje $Y'$ el conjunto de vértices en $Y$ adyacente a $X'$ en la igualdad subgrafo. El ajuste de la cubierta consiste en la sustitución de $u_k$ $u_k-\alpha$ por cada $x_k\in X'$ $v_k$ $v_k+\alpha$ por cada $y_k\in Y'$ donde $\alpha=\min\{u_k+v_j-\operatorname{wt}(x_ky_j):u_k\in X'\text{ and }y_j\in Y'\}$. El cambio neto en el costo de la cubierta es por lo tanto $\left(-|U'|+|V'|\right)\alpha<0$, y el costo de la nueva portada es, por tanto, menor que el costo de la edad.

Este PDF tiene una presentación que creo que es ligeramente diferente de la que usted tiene en mente; se llega a la optimalidad por una ruta diferente que puede ser más fácil de seguir, sobre todo con el buen ejemplo al final.