Sala de ' s thereom de matrimonio con máximo flujo-mínimo corte

Question

He oído que Teorema del matrimonio de Hall se puede demostrar por el teorema de máximo flujo-mínimo corte. ¿Podría exponer cómo eso es posible?

Teorema de Hall dice que en un grafo bipartito existe un juego completo (cubre todos los vértices del lado menor) si y sólo si (nombre de un lado de la bipartición A y el otro B) para cada subconjunto $A_s$ de vértices en el A hay al menos $\lvert A_s\rvert$ vértices B rea Chablé forma $A_s $ (a través de un borde).

Answer 1

Deje $G$ ser un bipartito gráfico con desdoblamiento $(A,B)$. Supongamos $G$ satisface Sala de la condición. Debemos mostrarles a $G$ tiene una coincidencia completa de$A$$B$.

Forma de grafo dirigido de $G$ mediante la adición de una fuente de vértice $s$, fregadero vértice $t$, uniéndose a $s$ a cada vértice en $A$ y se unen cada vértice en $B$$t$. Asignar a cada vértice en $A \cup B$ capacidad $1$. En este dígrafo, el caudal máximo de $s$ $t$es igual al máximo número de independientes de los bordes en la $G$ y por lo tanto es igual al tamaño máximo de una coincidencia en $G$. Necesitamos mostrar este valor es $|A|$. Un min de corte en el dígrafo es un conjunto de vértices de la forma $T_1 \cup T_2$ donde $T_1 \subseteq A, T_2 \subseteq B$. Para demostrar que el máximo flujo de valor es $|A|$, por el max min de flujo de corte teorema basta para mostrar que el min corte tiene el valor de $|A|$. Es claro que el min corte tiene el tamaño en la mayoría de las $|A|$ desde $A$ es un corte.

Deje $S_1 = A-T_1$$S_2 = B-T_2$. Desde $T_1 \cup T_2$ es un corte, no hay bordes en $G$$S_1$$S_2$. Por lo tanto, a todos los vecinos de $S_1$$T_2$. Si el min corte tiene un tamaño de menos de $|A|$,$|T_1|+|T_2| < |A|$, y desde $|T_1|+|S_1|=|A|$,$|T_2| < |S_1|$, lo que infringe la Sala de la condición. Por lo tanto, el min de corte tiene un tamaño igual a $|A|$. Esto demuestra que el máximo valor de flujo es igual a $|A|$. Esto implica que $G$ $|A|$ independiente de los bordes.

Answer 2

Le daré un toque. Como siempre todo el juego de pelota es escoger el gráfico del flujo apropiado. Como es el sabor típico, el gráfico de flujo será bipartito con un lado conectado a la fuente, y el otro conectado al fregadero. Ahora quieren poner pesos en los bordes para asegurar que:

1) el flujo de "ve" el tamaño de los conjuntos en un corte.

2) cualquier corte razonable debe respetar la estructura de grafo.

Espero que ayude.