En matemáticas , el teorema del matrimonio de Hall , probado por Philip Hall ( 1935 ), es un teorema con dos formulaciones equivalentes:
- La formulación combinatoria se ocupa de una colección de conjuntos finitos . Da una condición necesaria y suficiente para poder seleccionar un elemento distinto de cada conjunto.
- La formulación de la teoría de grafos trata con un grafo bipartito . Proporciona una condición necesaria y suficiente para encontrar una coincidencia que cubra al menos un lado del gráfico.
Formulación combinatoria
Dejar ser una familia (posiblemente infinita) de subconjuntos finitos de, donde los miembros de se cuentan con multiplicidad (es decir,puede contener el mismo conjunto varias veces). [1]
Una transversal paraes la imagen de una función inyectiva de a tal que es un elemento del conjunto para cada en la familia . En otras palabras, selecciona un representante de cada conjunto en de tal manera que no haya dos de estos representantes iguales. Un término alternativo para transversal es sistema de representantes distintos .
La colección S satisface la condición de matrimonio cuando para cada subfamilia,
Reiterado en palabras, la condición del matrimonio afirma que cada subfamilia de contiene al menos tantos miembros distintos como el número de conjuntos de la subfamilia.
Si la condición del matrimonio falla, no puede haber una transversal de .
Prueba |
---|
Supongamos que la condición del matrimonio falla, es decir, que para alguna subcolección de , Supongamos, a modo de contradicción, que una transversal de también existe. La restricción de a la subcolección infractora sería una función inyectiva de dentro . Esto es imposible por el principio de casillero ya que. Por tanto, no puede existir ninguna transversal si falla la condición matrimonial. |
El teorema de Hall establece que lo contrario también es cierto:
Teorema del matrimonio de Hall : una familia S de conjuntos finitos tiene una transversal si y solo si S satisface la condición del matrimonio.
Ejemplos de
Ejemplo 1: considere S = { A 1 , A 2 , A 3 } con
- A 1 = {1, 2, 3}
- A 2 = {1, 4, 5}
- A 3 = {3, 5}.
Una transversal válida sería (1, 4, 5). (Tenga en cuenta que esto no es único: (2, 1, 3) funciona igualmente bien, por ejemplo.)
Ejemplo 2: Considere S = { A 1 , A 2 , A 3 , A 4 } con
- A 1 = {2, 3, 4, 5}
- A 2 = {4, 5}
- A 3 = {5}
- A 4 = {4}.
No existe ninguna transversal válida; la condición del matrimonio se viola como lo muestra la subfamilia W = { A 2 , A 3 , A 4 }. Aquí el número de conjuntos de la subfamilia es | W | = 3, mientras que la unión de los tres conjuntos A 2 U A 3 U A 4 contiene solamente 2 elementos de X .
Ejemplo 3: Considere S = { A 1 , A 2 , A 3 , A 4 } con
- A 1 = { a , b , c }
- A 2 = { b , d }
- A 3 = { a , b , d }
- A 4 = { b , d }.
Las únicas transversales válidas son ( c , b , a , d ) y ( c , d , a , b ).
Aplicación al matrimonio
El ejemplo estándar de una aplicación del teorema del matrimonio es imaginar dos grupos; uno de n hombres y una de n mujeres. Para cada mujer, hay un subconjunto de hombres, con cualquiera de los cuales se casaría felizmente; y cualquier hombre estaría feliz de casarse con una mujer que quiera casarse con él. Considere si es posible emparejar (en matrimonio ) a hombres y mujeres para que todos sean felices.
Si dejamos que A i sea el conjunto de hombres con los que la i -ésima mujer estaría feliz de casarse, entonces el teorema del matrimonio establece que cada mujer puede casarse felizmente con un hombre único si y solo si para cualquier subconjunto de las mujeres, el número de hombres con los que al menos una de estas mujeres estaría feliz de casarse, , es al menos tan grande como el número de mujeres en ese subconjunto, .
Es obvio que esta condición es necesaria , ya que si no se cumple, no hay suficientes hombres para compartir entre losmujeres. Lo interesante es que también es una condición suficiente .
Formulación de la teoría de grafos
Sea G un gráfico bipartito finito con conjuntos bipartitos X e Y (es decir, G : = ( X + Y , E )). Un juego X-perfecto (también llamado: X-saturar a juego ) es un juego que cubre cada vértice en X .
Para un subconjunto W de X , dejar N G ( W ) denotar el barrio de W en G , es decir, el conjunto de todos los vértices en Y adyacentes a algún elemento de W . El teorema del matrimonio en esta formulación establece que hay una coincidencia perfecta de X si y solo si para cada subconjunto W de X :
En otras palabras: cada subconjunto W de X tiene suficientemente muchos vértices adyacentes en Y .
Prueba de la versión teórica de grafos
Fácil dirección : suponemos que algunas coincidentes M satura cada vértice de X , y demostrar que la condición de Hall está satisfecho para todos W ⊆ X . Sea M ( W ) el conjunto de todos los vértices en Y emparejados por M a un W dado . Por definición de coincidencia, | M ( W ) | = | W |. Pero M ( W ) ⊆ N G ( W ), ya que todos los elementos de M ( W ) son vecinos de W . Entonces, | N G ( W ) | ≥ | M ( W ) | y por tanto, | N G ( W ) | ≥ | W |.
Dirección duro : se supone que no hay X coincidente -perfect y demostrar que la condición de Hall es violada por al menos un W ⊆ X . Deje que M sea un juego máximo, y dejar que u sea un vértice de X no saturado por M . Considere todas las trayectorias alternas (es decir, trayectorias en G que utilizan alternativamente aristas dentro y fuera de M ) a partir de u . Sea Z el conjunto de todos los puntos en Y conectados ay por estos caminos alternos , y W el conjunto de todos los puntos en X conectados ay por estos caminos alternos (incluido el propio u ) . Ninguna ruta alterna máxima puede terminar en un vértice en Y , no sea que sea una ruta de aumento , de modo que podamos aumentar M a una coincidencia estrictamente más grande al alternar el estado (pertenece a M o no) de todos los bordes de la ruta. Así, cada vértice en Z es emparejado por M con un vértice en W \ { u }. A la inversa, cada vértice v en W \ { u } es emparejado por M con un vértice en Z (es decir, el vértice que precede a v en una trayectoria alterna que termina en v ). Por tanto, M proporciona una biyección de W \ { u } y Z , lo que implica | W | = | Z | + 1. Por otro lado, N G ( W ) ⊆ Z : que v en Y estar conectado a un vértice w en W . El borde ( w , v ) debe estar en M , de lo contrario u llega a w a través de una ruta alterna que no contiene v , y podríamos tomar esta ruta alterna que termina en w y extenderla con v , obteniendo una ruta aumentada (que nuevamente contradeciría la maximalidad de M ). Por tanto, v debe estar en Z y, por tanto, | N G ( W ) | ≤ | Z | = | W | - 1 <| W |.
Prueba constructiva de la dirección dura
Defina un infractor de Hall como un subconjunto W de X para el cual | N G ( W ) | <| W |. Si W es un violador Hall, entonces no hay ninguna coincidencia que satura todos los vértices de W . Por lo tanto, no hay tampoco a juego que satura X . El teorema del matrimonio de Hall dice que una gráfica contiene una coincidencia perfecta de X si y solo si no contiene infractores de Hall. El siguiente algoritmo demuestra la dirección estricta del teorema: encuentra una coincidencia perfecta de X o un infractor de Hall. Utiliza, como subrutina, un algoritmo que, dado una M coincidente y un vértice no coincidente x 0 , encuentra una ruta de aumento M o un infractor de Hall que contiene x 0 .
Usa
- Inicializar M : = {}. // Coincidencia vacía.
- Assert: M es un coincidente en G .
- Si M se satura todos los vértices de X, a continuación, devuelven el X -perfect coincidente M .
- Sea x 0 un vértice no coincidente (un vértice en X \ V ( M )).
- Utilizando el algoritmo de infractor de Hall , busque un infractor de Hall o una ruta de aumento M.
- En el primer caso, devuelva el infractor de Hall .
- En el segundo caso, use la ruta de aumento M para aumentar el tamaño de M (en un borde) y vuelva al paso 2 .
En cada iteración, M crece en un borde. Por tanto, este algoritmo debe finalizar después de, como máximo, | E | iteraciones. Cada iteración toma como máximo | X | hora. La complejidad total del tiempo de ejecución es similar al método Ford-Fulkerson para encontrar una coincidencia máxima de cardinalidad .
Equivalencia de la formulación combinatoria y la formulación teórica de grafos
Sea S = ( A 1 , A 2 , ..., A n ) donde A i son conjuntos finitos que no necesitan ser distintos. Sea el conjunto X = { A 1 , A 2 , ..., A n } (es decir, el conjunto de nombres de los elementos de S ) y el conjunto Y sea la unión de todos los elementos en todo A i .
Formamos un gráfico bipartito finito G : = ( X + Y , E ), con conjuntos bipartitos X e Y uniendo cualquier elemento de Y a cada A i del que es miembro. A transversal de S es un X -perfect coincidente (un juego que cubre cada vértice en X ) del gráfico bipartito G . Así, un problema en la formulación combinatoria puede traducirse fácilmente a un problema en la formulación de la teoría de grafos.
Prueba topológica
El teorema de Hall se puede demostrar (de forma no constructiva) basándose en el lema de Sperner . [2] : Thm.4.1,4.2
Aplicaciones
El teorema tiene muchas otras aplicaciones interesantes "no maritales". Por ejemplo, tome una baraja de cartas estándar y distribúyalas en 13 pilas de 4 cartas cada una. Luego, usando el teorema del matrimonio, podemos demostrar que siempre es posible seleccionar exactamente 1 carta de cada pila, de modo que las 13 cartas seleccionadas contengan exactamente una carta de cada rango (As, 2, 3, ..., Reina, Rey).
Más abstractamente, deja que G sea un grupo , y H sea un finito subgrupo de G . Entonces el matrimonio teorema se puede utilizar para demostrar que hay un conjunto T de tal manera que T es una transversal tanto para el conjunto de la izquierda clases laterales y clases laterales derechas de H en G .
El teorema del matrimonio se utiliza en las demostraciones habituales del hecho de que un rectángulo latino ( r × n ) siempre puede extenderse a un rectángulo latino (( r +1) × n ) cuando r < n , y así, en última instancia, a un rectángulo latino cuadrado .
Equivalencias lógicas
Este teorema es parte de una colección de teoremas notablemente poderosos en combinatoria, todos los cuales están relacionados entre sí en un sentido informal, ya que es más sencillo probar uno de estos teoremas a partir de otro de ellos que a partir de los primeros principios. Éstas incluyen:
- El teorema de König-Egerváry (1931) ( Dénes Kőnig , Jenő Egerváry )
- Teorema de König [3]
- Teorema de Menger (1927)
- El teorema de flujo máximo y corte mínimo (algoritmo de Ford-Fulkerson)
- El teorema de Birkhoff-Von Neumann (1946)
- Teorema de Dilworth .
En particular, [4] [5] hay pruebas simples de las implicaciones teorema de Dilworth ⇔ teorema de Hall ⇔ teorema de König-Egerváry ⇔ teorema de König.
Familias infinitas
Variante de Marshall Hall Jr.
Al examinar cuidadosamente la prueba original de Philip Hall , Marshall Hall, Jr. (sin relación con Philip Hall) pudo modificar el resultado de una manera que permitió que la prueba funcionara para S infinito . [6] Esta variante refina el teorema del matrimonio y proporciona un límite inferior en el número de transversales que puede tener un S dado . Esta variante es: [7]
Suponga que ( A 1 , A 2 , ..., A n ), donde A i son conjuntos finitos que no necesitan ser distintos, es una familia de conjuntos que satisface la condición matrimonial, y suponga que | A i | ≥ r para i = 1, ..., n . ¡Entonces el número de transversales diferentes para la familia es al menos r ! si r ≤ n y r ( r - 1) ... ( r - n + 1) si r > n .
Recuerde que una transversal para una familia S es una secuencia ordenada, por lo que dos transversales diferentes podrían tener exactamente los mismos elementos. Por ejemplo, la familia A 1 = {1, 2, 3}, A 2 = {1, 2, 5} tiene tanto (1, 2) como (2, 1) como transversales distintas.
La condición matrimonial no se extiende
El siguiente ejemplo, debido a Marshall Hall, Jr., muestra que la condición del matrimonio no garantizará la existencia de una transversal en una familia infinita en la que se permiten conjuntos infinitos.
Sea S la familia, A 0 = {1, 2, 3, ...}, A 1 = {1}, A 2 = {2}, ..., A i = { i }, ...
La condición del matrimonio es válida para esta familia infinita, pero no se puede construir ninguna transversal. [8]
El problema más general de seleccionar un elemento (no necesariamente distinto) de cada uno de una colección de conjuntos no vacíos (sin restricción en cuanto al número de conjuntos o el tamaño de los conjuntos) se permite en general sólo si el axioma de elección es aceptado.
El teorema del matrimonio se extiende al caso infinito si se establece correctamente. Dado un gráfico bipartito con lados A y B , decimos que un subconjunto C de B es más pequeño o igual en tamaño que un subconjunto D de A en el gráfico si existe una inyección en el gráfico (es decir, usando solo los bordes del gráfico) de C a D , y que es estrictamente menor en el gráfico si además no hay inyección en el gráfico en la otra dirección. Tenga en cuenta que omitir en el gráfico produce la noción ordinaria de comparar cardinalidades. El teorema del matrimonio infinito establece que existe una inyección de A a B en el gráfico, si y solo si no hay un subconjunto C de A tal que N ( C ) sea estrictamente menor que C en el gráfico. [9]
Variante de coincidencia fraccional
Una coincidencia fraccional en un gráfico es una asignación de pesos no negativos a cada borde, de modo que la suma de pesos adyacentes a cada vértice sea como máximo 1. Una coincidencia fraccional es X perfecta si la suma de pesos adyacentes a cada vértice es exactamente 1. Los siguientes son equivalentes para un gráfico bipartito G = ( X + Y, E ): [10]
- G admite una combinación perfecta de X.
- G admite una coincidencia fraccionaria perfecta en X. La implicación es obvia ya que una coincidencia X -perfect es un caso especial de una coincidencia fraccional X -perfect, en la que cada peso es 1 (si el borde está en la coincidencia) o 0 (si no lo está).
- G satisface la condición de matrimonio de Hall. La implicación se cumple porque, para cada subconjunto W de X , la suma de pesos cerca de los vértices de W es | W |, por lo que los bordes adyacentes a ellos son necesariamente adyacentes al menos a | W | vértices de Y .
Variante cuantitativa
Cuando la condición de Hall no se cumple, el teorema original solo nos dice que no existe una coincidencia perfecta, pero no dice cuál es la coincidencia más grande que existe. Para aprender esta información, necesitamos la noción de deficiencia de un gráfico . Dado un gráfico bipartito G = ( X + Y , E ), la deficiencia de G wrt X es el máximo, sobre todos los subconjuntos W de X , de la diferencia | W | - | N G ( W ) |. Cuanto mayor es la deficiencia, más lejos está el gráfico de satisfacer la condición de Hall.
Usando el teorema del matrimonio de Hall, se puede demostrar que, si la deficiencia de un gráfico bipartito G es d , entonces G admite una coincidencia de tamaño al menos | X | - d .
Generalizaciones
- El teorema de Tutte proporciona una generalización del teorema de Hall a los gráficos generales (que no son necesariamente bipartitos) .
- Varios teoremas de tipo Hall para hipergráficos proporcionan una generalización del teorema de Hall a los hipergráficos bipartitos .
Notas
- ^ Hall, Jr. 1986 , pág. 51. También es posible tener infinitos conjuntos en la familia, pero el número de conjuntos en la familia debe ser finito, contado con multiplicidad. Solo no se permite la situación de tener un número infinito de conjuntos mientras se permiten conjuntos infinitos.
- ^ Haxell, P. (2011). "Sobre la formación de comités" . The American Mathematical Monthly . 118 (9): 777–788. doi : 10.4169 / amer.math.monthly.118.09.777 . ISSN 0002-9890 .
- ^ El nombre de este teorema es inconsistente en la literatura. Está el resultado sobre emparejamientos en gráficos bipartitos y su interpretación como una cobertura de (0,1) -matrices. Hall, Jr. (1986) y van Lint y Wilson (1992) se refieren a la forma matricial como teorema de König, mientras que Roberts y Tesman (2009) se refieren a esta versión como el teorema de Kőnig-Egerváry. Cameron (1994) y Roberts & Tesman (2009) denominan la versión gráfica bipartita teorema de Kőnig.
- ^ Equivalencia de siete teoremas principales en combinatoria
- ^ Reichmeider 1984
- ^ Hall, Jr. 1986 , pág. 51
- ↑ Cameron 1994 , pág. 90
- ^ Hall, Jr. 1986 , pág. 51
- ^ Aharoni, Ron (febrero de 1984). "Teorema de dualidad de König para gráficos bipartitos infinitos". Revista de la Sociedad Matemática de Londres . s2-29 (1): 1–12. doi : 10.1112 / jlms / s2-29.1.1 . ISSN 0024-6107 .
- ^ "co.combinatorics - versión de emparejamiento fraccional del teorema del matrimonio de Hall" . MathOverflow . Consultado el 29 de junio de 2020 .
Referencias
- Brualdi, Richard A. (2010), Introducción a la combinatoria , Upper Saddle River, Nueva Jersey: Prentice-Hall / Pearson, ISBN 978-0-13-602040-0
- Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos , Cambridge: Cambridge University Press, ISBN 978-0-521-45761-3
- Dongchen, Jiang; Nipkow, Tobias (2010), "Teorema del matrimonio de Hall" , El archivo de pruebas formales , ISSN 2150-914X . Prueba comprobada por computadora.CS1 maint: posdata ( enlace )
- Hall, Jr., Marshall (1986), Teoría combinatoria (2a ed.), Nueva York: John Wiley & Sons, ISBN 978-0-471-09138-7
- Hall, Philip (1935), "Sobre representantes de subconjuntos", J. London Math. Soc. , 10 (1): 26–30, doi : 10.1112 / jlms / s1-10.37.26
- Halmos, Paul R .; Vaughan, Herbert E. (1950), "El problema del matrimonio", American Journal of Mathematics , 72 (1): 214-215, doi : 10.2307 / 2372148 , JSTOR 2372148 , MR 0033330
- Reichmeider, PF (1984), The Equivalence of Some Combinatorial Matching Theorems , Polygonal Publishing House, ISBN 978-0-936428-09-3
- Roberts, Fred S .; Tesman, Barry (2009), Applied Combinatorics (2.a ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
- van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge: Cambridge University Press, ISBN 978-0-521-42260-4
enlaces externos
- Teorema del matrimonio al cortar el nudo
- Teorema y algoritmo matrimonial en el corte del nudo
- El teorema del matrimonio de Hall se explica intuitivamente en las notas de Lucky.
Este artículo incorpora material de la prueba del teorema del matrimonio de Hall en PlanetMath , que está bajo la licencia Creative Commons Attribution / Share-Alike License .