infractor de Hall

En teoría de grafos , un violador de Hall es un conjunto de vértices en un grafo que violan la condición del teorema de matrimonio de Hall . ^{[ 1 ]}

Formalmente, dado un grafo bipartito $G = (X + Y, E)$ , un violador de Hall en $X$ es un subconjunto $W$ de $X$ , para el cual $| N G (W)| < | W |$ , donde $N G (W)$ es el conjunto de vecinos de $W$ en $G$ .

Si $W$ es una violación de Hall, entonces no existe ningún emparejamiento que sature todos los vértices de $W.$ Por lo tanto, tampoco existe ningún emparejamiento que sature $X.$ El teorema del matrimonio de Hall afirma que lo contrario también es cierto: si no existe ninguna violación de Hall, entonces existe un emparejamiento que satura $X.$

Algoritmos

Encontrar a un infractor del Hall

Un violador de Hall puede detectarse mediante un algoritmo eficiente. El algoritmo que se muestra a continuación utiliza los siguientes términos:

Un camino $M$ -alternado , para algún $M$ coincidente , es un camino en el que la primera arista no es una arista de $M$ , la segunda arista es de $M$ , la tercera no es de $M$ , etc.
Un vértice $z$ es $M$ -alcanzable desde algún vértice $x$ , si existe un camino $M -alternativo de$ $x$ a $z$ .

Como ejemplo, considere la figura de la derecha, donde los bordes verticales (azules) denotan el $M$ correspondiente . Los conjuntos de vértices $Y 1, X 1, Y 2, X 2$ , son $M$ -alcanzables desde $x 0$ (o cualquier otro vértice de $X 0$ ), pero $Y 3$ y $X 3$ no son $M$ -alcanzables desde $x 0$ .

El algoritmo para encontrar una violación de Hall procede de la siguiente manera.

Encuentra el máximo emparejamiento $M$ (se puede encontrar con el algoritmo de Hopcroft-Karp ).
Si todos los vértices de $X$ coinciden, entonces devuelve "No hay ningún violador de Hall".
De lo contrario, sea $x 0$ un vértice no emparejado.
Sea $W$ el conjunto de todos los vértices de $X$ que son $M-$ alcanzables desde $x 0$ (se puede encontrar usando una búsqueda en anchura ; en la figura, $W$ contiene $x 0$ y $X 1$ y $X 2$ ).
Regresar $W.$

Esta $W$ es, de hecho, una violadora de Hall debido a los siguientes hechos:

Todos los vértices de $N G (W)$ están emparejados por $M$ . Supongamos por contradicción que algún vértice $y$ en $N G (W)$ no está emparejado por $M$ . Sea $x$ su vecino en $W$ . El camino de $x 0$ a $x$ a $y$ es un camino $M$ -aumentante - es $M$ -alternativo y comienza y termina con vértices no emparejados, 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 $alcanzables por M$ desde $x 0$ .
$W$ contiene otro vértice, $x 0$ , quepor definición $no tiene correspondencia con M.$
Por lo tanto, $| W | = | N G (W)| + 1 > | N G (W)|$ , así que $W$ efectivamente satisface la definición de un violador de Hall.

Encontrar infractores mínimos y mínimos de Hall

Un violador de Hall con mínima inclusión es un violador de Hall tal que cada uno de sus subconjuntos no es un violador de Hall.

El algoritmo anterior, de hecho, encuentra un violador de Hall con mínima inclusión. Esto se debe a que, si se elimina cualquier vértice de $W$ , los vértices restantes pueden emparejarse perfectamente con los vértices de $N G (W)$ (ya sea mediante aristas de $M$ o mediante aristas del camino alternante de M desde $x 0$ ). ^{[ 2 ]}

El algoritmo anterior no necesariamente encuentra un violador de Hall de cardinalidad mínima . Por ejemplo, en la figura anterior, devuelve un violador de Hall de tamaño 5, mientras que $X 0$ es un violador de Hall de tamaño 3.

De hecho, encontrar un violador de Hall de cardinalidad mínima es NP-difícil. Esto se puede demostrar mediante una reducción a partir del problema de la camarilla . ^{[ 3 ]}

Encontrar un violador de Hall o una ruta de aumento

El siguiente algoritmo ^{[ 4 ]}^{[ 5 ]} toma como entrada un emparejamiento arbitrario M $en$ un grafo y un vértice $x 0$ en $X$ que no está saturado por $M.$

Devuelve como resultado, o bien un violador de Hall que contiene x $0,$ o bien una ruta que se puede utilizar 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 los $y i$ son vértices distintos de $Y$ ;
- Para todo $i \geq 1$ , $y i$ se corresponde con $x i$ mediante $M.$
- Para todo $i \geq 1$ , $y i$ está conectado a algún $x j < i$ por una arista que no está en $M.$
Si $N G (W k) \subseteq Z k$ , entonces $W k$ es un violador de Hall, ya que $| W k | = k +1 > k = | Z k | \geq | N G (W k)|$ . Devuelve el violador de Hall $W k$ .
De lo contrario, sea $y k +1$ un vértice en $N G ( W k ) \ Z k .$ Consideremos los dos casos siguientes:
Caso 1: y _{k +1} coincide con M.
- Dado que $x 0$ no está emparejado, y cada $x i$ en $W k$ está emparejado 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$ . Denotemoslo 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$ .
- Vuelve al paso 2 .
Caso 2: y k _{+1 no} tiene correspondencia con M.
- Dado que $y k +1$ está en $N G (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. Siguiendo estas conexiones se debe llegar finalmente a $x 0$ , que no está emparejado. Por lo tanto, tenemos un camino de aumento de M. Devuelve el camino de aumento de M .

En cada iteración, $W k$ y $Z k$ aumentan en un vértice. Por lo tanto, el algoritmo debe terminar después de como máximo $| X |$ iteraciones.

El procedimiento puede utilizarse de forma iterativa: se comienza con $M$ como un emparejamiento vacío, se llama al procedimiento repetidamente hasta que se encuentre un violador del teorema de Hall o el emparejamiento $M$ sature todos los vértices de $X.$ Esto proporciona una demostración constructiva del teorema de Hall.

Enlaces externos

Una aplicación de violadores de Hall en programación con restricciones . ^{[ 6 ]}
"Encontrar un subconjunto en un grafo bipartito que viole la condición de Hall" . Computer science stack exchange . 15 de septiembre de 2014. Consultado el 8 de septiembre de 2019 .

Referencias

↑ Lenchner, Jonathan (2020-01-19). "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 k mínima ". Tesis de maestría. Teorema 3.2.5. Este es también el Ejercicio 13.28 en [4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk y Saket Saurabh, "Algoritmos parametrizados", Springer, 2016. Véase también esta publicación de CS stackexchange .
↑ Mordecai J. Golin (2006). "Emparejamiento bipartito y el método húngaro" (PDF) .
↑ Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Emparejamientos libres de envidia en grafos bipartitos y sus aplicaciones a la división justa". arXiv : 1901.09527v2 [ cs.DS ].
↑ Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03). "Justifying All Differences Using Pseudo-Boolean Reasoning" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 1486– 1494. doi : 10.1609/aaai.v34i02.5507 . ISSN 2374-3468 . S2CID 208242680 .

[1] Lenchner, Jonathan (2020-01-19). "Sobre una generalización del problema del matrimonio". arXiv : 1907.05870v3 [ math.CO ].

[2] 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 .

[3] Aditya Kabra. " Complejidad parametrizada del problema de unión k mínima ". Tesis de maestría. Teorema 3.2.5. Este es también el Ejercicio 13.28 en [4] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk y Saket Saurabh, "Algoritmos parametrizados", Springer, 2016. Véase también esta publicación de CS stackexchange .

[4] Mordecai J. Golin (2006). "Emparejamiento bipartito y el método húngaro" (PDF) .

[5] Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Emparejamientos libres de envidia en grafos bipartitos y sus aplicaciones a la división justa". arXiv : 1901.09527v2 [ cs.DS ].

[6] Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03). "Justifying All Differences Using Pseudo-Boolean Reasoning" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 34 (2): 1486– 1494. doi : 10.1609/aaai.v34i02.5507 . ISSN 2374-3468 . S2CID 208242680 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]