Formalmente, dado un gráfico bipartito G = ( X + Y , E ) , un violador de Hall en X es un subconjunto W de X , para el cual | NG ( W ) | < | W | , donde N G ( W ) es el conjunto de vecinos de W en G .
Si W es un violador de Hall, entonces no hay coincidencia que sature todos los vértices de W. Por lo tanto, tampoco existe ninguna coincidencia que sature X . El teorema del matrimonio de Hall dice que lo contrario también es cierto: si no hay ningún infractor de Hall, entonces existe una coincidencia que satura X.
Algoritmos
Encontrar un infractor de Hall
Se puede encontrar un infractor de Hall mediante un algoritmo eficiente. El siguiente algoritmo utiliza los siguientes términos:
Un camino alternativo M , para algunos M coincidentes , es un camino en el que el primer borde no es un borde de M , el segundo borde es de M , el tercero no es de M , etc.
Un vértice z es M -alcanzable desde algún vértice x , si hay un camino M -alterno de xa z .
Como ejemplo, considere la figura de la derecha, donde los bordes verticales (azules) indican la M coincidente . Los conjuntos de vértices Y 1 , X 1 , Y 2 , X 2 , son alcanzables M desde x 0 (o cualquier otro vértice de X 0 ), pero Y 3 y X 3 no son alcanzables M desde x 0 .
El algoritmo para encontrar un infractor de Hall procede de la siguiente manera.
Si todos los vértices de X coinciden, devuelve "No hay ningún infractor de Hall".
De lo contrario, sea x 0 un vértice no coincidente.
Sea W el conjunto de todos los vértices de X a los que se puede llegar M desde x 0 (se puede encontrar usando la búsqueda en amplitud ; en la figura, W contiene x 0 , X 1 y X 2 ).
Volver W.
Esta W es de hecho un infractor de Hall debido a los siguientes hechos:
Todos los vértices de N G ( W ) coinciden con M . Supongamos por contradicción que algún vértice y en N G ( W ) no tiene correspondencia con M . Sea x su vecino en W . El camino de x 0 a x a y es un camino que aumenta M - es M -alterno y comienza y termina con vértices inigualables, por lo que al "invertirlo" podemos aumentar M , contradiciendo su maximalidad.
W contiene todas las coincidencias de N G ( W ) por M . Esto se debe a que todas estas coincidencias son M accesibles desde x 0 .
W contiene otro vértice, x 0 , quepor definición no coincide con M.
Por lo tanto, | W | = | NG ( W ) | + 1 > | NG ( W ) | , por lo que W de hecho satisface la definición de infractor de Hall.
Encontrar infractores mínimos y mínimos de Hall
Un infractor de Hall con inclusión mínima es un infractor de Hall tal que cada uno de sus subconjuntos no es un infractor de Hall.
El algoritmo anterior, de hecho, encuentra un infractor de Hall con inclusión mínima. Esto se debe a que, si se elimina algún vértice de W , entonces los vértices restantes pueden coincidir perfectamente con los vértices de N G ( W ) (ya sea por los bordes de M o por los bordes del camino alternativo M desde x 0 ). [2]
El algoritmo anterior no necesariamente encuentra un infractor de Hall con cardinalidad mínima . Por ejemplo, en la figura anterior, devuelve un infractor de Hall de tamaño 5, mientras que X 0 es un infractor de Hall de tamaño 3.
De hecho, encontrar un infractor de Hall con cardinalidad mínima es NP-difícil. Esto se puede demostrar mediante la reducción del problema de la camarilla . [3]
Encontrar un infractor de Hall o un camino de aumento
El siguiente algoritmo [4] [5] toma como entrada una coincidencia arbitraria M en un gráfico y un vértice x 0 en X que no está saturado por M.
Devuelve como salida, ya sea un infractor de Hall que contiene x 0 o una ruta que puede usarse para aumentar M.
Establecer k = 0 , W k : = { x 0 }, Z k : = {} .
Afirmar:
W k = { x 0 ,..., x k } donde los x i son vértices distintos de X ;
Z k = { y 1 ,..., y k } donde y i son vértices distintos de Y ;
Para todo i ≥ 1 , y i coincide con x i por M .
Para todo i ≥ 1 , y i está conectado a algún x j < i por una arista que no está en M .
Si N G ( W k ) ⊆ Z k , entonces W k es un violador de Hall, ya que | Semana k | = k +1 > k = | Z k | ≥ | NG ( Wk ) | . Devuelve el violador de Hall W k .
De lo contrario, sea y k +1 un vértice en N G ( W k ) \ Z k . Considere los dos casos siguientes:
Caso 1: y k +1 coincide con M .
Dado que x 0 no tiene correspondencia, y cada x i en W k coincide con y i en Z k , el compañero de este y k +1 debe ser algún vértice de X que no esté en W k . Denotalo por x k +1 .
Sea W k +1 := W k U { x k +1 } y Z k +1 := Z k U { y k +1 } y k := k + 1 .
Vuelva al paso 2 .
Caso 2: y k +1 no tiene comparación con M .
Dado que y k +1 está en NG ( W k ) , está conectado a algún x i (para i < k + 1 ) por una arista que no está en M. x i está conectado a y i por una arista en M . y i está conectado a algún x j (para j < i ) por una arista que no está en M , y así sucesivamente. Seguir estas conexiones debe conducir eventualmente a x 0 , que no tiene comparación. Por tanto tenemos un camino de aumento de M. Devuelve la ruta de aumento M.
En cada iteración, W k y Z k crecen en un vértice. Por lo tanto, el algoritmo debe finalizar como máximo después de | X | iteraciones.
El procedimiento se puede utilizar de forma iterativa: comience con M como una coincidencia vacía, llame al procedimiento una y otra vez, hasta que se encuentre un infractor de Hall o la coincidencia M sature todos los vértices de X. Esto proporciona una prueba constructiva del teorema de Hall.
"Encontrar un subconjunto en un gráfico bipartito que viole la condición de Hall". Intercambio de pilas de informática . 2014-09-15 . Consultado el 8 de septiembre de 2019 .
Referencias
^ Lenchner, Jonathan (19 de enero de 2020). "Sobre una generalización del problema del matrimonio". arXiv : 1907.05870v3 [math.CO].
^ Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (1 de septiembre de 2019). "Libre de envidia en los problemas de asignación de viviendas". Ciencias Sociales Matemáticas . 101 : 104-106. arXiv : 1905.00468 . doi : 10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.
^ Aditya Kabra. "Complejidad parametrizada del problema de unión mínima k". Tesis de maestría. Teorema 3.2.5. Este también es el ejercicio 13.28 en [4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk y Saket Saurabh, "Parameterized Algorithms", Springer, 2016. Véase también esta publicación de CS stackexchange .
^ Mardoqueo J. Golin (2006). "Emparejamiento bipartito y el método húngaro" (PDF) .
^ Segal-Halevi, Erel; Aigner-Horev, Elad (28 de enero de 2019). "Emparejamientos sin envidia en gráficos bipartitos y sus aplicaciones a la división justa". arXiv : 1901.09527v2 [cs.DS].
^ Elffers, enero; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (3 de abril de 2020). "Justificación de todas las diferencias mediante razonamiento pseudobooleano". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 1486-1494. doi : 10.1609/aaai.v34i02.5507 . ISSN 2374-3468. S2CID 208242680.
