El Teorema de Hall es una aplicación que creo que es realmente hermosa.
Un gráfico bipartito es aquel en el que puede dividir los nodos en dos partes, de modo que todos los bordes del gráfico se encuentren entre nodos en diferentes partes. Una coincidencia perfecta en un gráfico bipartito es un conjunto de aristas de modo que cada nodo se incluya exactamente en una arista. Si imagina un conjunto de nodos como hombres y un conjunto como mujeres, entonces un gráfico bipartito representa pares de personas dispuestas a casarse entre sí y una combinación perfecta es un conjunto de matrimonios que hace que todos se casen en un matrimonio aceptable.
El teorema de Hall afirma intuitivamente que, a menos que algo realmente obvio se interponga en tu camino, siempre puedes resolver el problema del matrimonio. ¿Qué podría interponerse en tu camino? Por un lado, podría haber más hombres que mujeres o viceversa. Entonces suponemos que los números son iguales. Otras cosas pueden salir mal. ¿Qué pasaría si seis hombres pudieran ser emparejados con un total de solo cinco mujeres? Entonces estarías atrapado en una combinación perfecta porque no habría suficientes mujeres para ese conjunto de hombres. Resulta que esto es todo lo que puede salir mal. Declaramos esto más precisamente.
- ¿Cuál es el significado del Lema Hardcore de Impagliazzo?
- ¿Qué significa cuando una función es seguida por la notación big-O?
- Cómo implementar esto en Python: dada una matriz, encuentre tres números a, byc de modo que a ^ 2 + b ^ 2 = c ^ 2
- ¿Cuál es la complejidad computacional de un problema de clasificación? ¿Es P o NP?
- ¿Hay algún método para generar números factoriales grandes usando C ++?
Teorema de Hall
Supongamos que G es un gráfico bipartito, con conjuntos partitos A y B de igual tamaño. Entonces G tiene una coincidencia perfecta si y solo si cada subconjunto de k nodos en A se conecta a al menos k nodos en B, y cada subconjunto de k nodos en B se conecta a al menos k nodos en A.
