Unión de dos conjuntos coincidentes siendo una coincidencia

Question

Sea $G$ sea un grafo bipartito con partes $A$ y $B$ . Sea $U\subseteq A$ y $V\subseteq B$ y supongamos que existe coincidencia en $G$ que abarca todos los vértices de $U$ y otra coincidencia que cubra todos los vértices de $V$ . Demuestre que existe un emparejamiento que cubre todos los vértices de $U \cup V$ . (Pista: considera la unión de estas dos coincidencias, ¿qué aspecto tiene?)

Aquí está mi intento:

Sea $M_1$ es el emparejamiento que cubre todos los vértices de $U$ y análogamente $M_2$ sea la correspondencia para $V$ . Sea $M=M_1 \cup M_2$ . Tenemos que demostrar que es posible que $M$ sea una correspondencia que cubra la unión de $U$ y $V$ . Ahora $M$ cubriría claramente todos los vértices de $U$ y $V$ (debería explicar esto más) pero podría no ser una coincidencia porque podría tener aristas que tienen vértices en común. Si $M$ no tiene aristas que contengan vértices en común, entonces hemos terminado así que $M$ coincidiría con lo que tenemos que demostrar y que se describe en la pregunta. Supongamos que no es el caso. Obsérvese que para todas las aristas digamos $uv$ contenía $G$ vértice $u \in A$ y vértice $v \in B$ de lo contrario no sería un grafo bipartito. Consideremos tres vértices arbitrarios en $G$ , digamos $u\in U$ y $v,p \in V$ . Sea $uv, up \in M$ . Tener estas dos aristas significaría que $M$ no es coincidente porque hay un vértice en común que es $u$ . Debemos tener en cuenta que estas dos aristas no pueden estar ambas en $M_1$ o ambos en $M_2$ de lo contrario $M_1$ y $M_2$ no serían conjuntos coincidentes. Así que digamos sin pérdida de generalidad que $uv \in M_1$ y $up \in M_2$ . Podemos eliminar la arista $uv$ porque el vértice $v$ ya estará cubierto en $M$ porque el vértice $v$ estará en $M_2$ - de lo contrario $M_2$ no abarcaría todos los vértices de $V$ desde $v \in V$ . Como nuestros vértices eran arbitrarios, después de las eliminaciones necesarias, $M$ será una correspondencia que abarque todos los vértices de $U \cup V$ .

Por favor, dígame cualquier cosa que esté mal o que necesite más justificación. Puede que me haya precipitado un poco en la última parte. Me gustaría ver cuál es la mejor respuesta.

Answer 1

Aquí tienes una solución que aprovecha la pista. Piensa en $M=M_1\cup M_2$ (donde $M_1$ es la coincidencia que cubre $U$ y $M_2$ es la coincidencia que cubre $V$ ) como dirigido gráfico; aristas en $M_1$ se dirigen desde $A$ hacia $B$ ("rojo"), y bordes en $M_2$ se dirigen en sentido contrario ("azul"). Todos los vértices de $M$ tiene grado $1$ o $2$ por lo que los componentes de $M$ son caminos simples o ciclos. Además, el grado $2$ Los vértices tienen una arista de entrada y otra de salida, por lo que los caminos y ciclos son caminos dirigidos y ciclos dirigidos cuyas aristas alternan el rojo y el azul. Obsérvese que, como los vértices de $U\cup V$ tienen un borde saliente, un componente de $M$ que es un camino no puede terminar ni en $U$ o $V$ .

Ahora seleccionamos aristas de $M$ para obtener una coincidencia. Para cada camino, seleccione aristas alternas empezando por la primera. Si el camino tiene un número impar de aristas (por lo tanto cubre un número par de puntos) se trata de un emparejamiento entre el $A$ puntos del recorrido y el $B$ puntos. Si hay una arista extra, no cubrimos el último vértice - pero ese vértice no está ni en $U$ ni $V$ así que está bien. Para cada ciclo, selecciona aristas alternas que empiecen donde quieras (es decir, toma las aristas rojas o las aristas azules). En ambos casos, se obtiene una correspondencia que cubre todos los vértices del ciclo. La correspondencia resultante cubre todos los vértices de $M$ excepto algunos puntos finales de la ruta, que no estaban en $U$ o $V$ por lo que la coincidencia cubre $U\cup V$ . $\ \square$

Observamos que en el caso especial de que empecemos con una coincidencia $M_1$ de $U$ en $B$ y un $M_2$ de $V$ en $A$ este argumento demuestra que $M$ contiene exactamente $2^k$ emparejamientos que cubren $U\cup V$ donde $k$ es el número de ciclos en $M$ .

Answer 2

Como el siguiente algoritmo termina y produce una coincidencia hemos terminado.

Comience con $M=M_1$ y que $V'$ sea el conjunto de vértices de $V $ no cubiertos por $M$ .

Seleccione $v'$ en $V'$ considere la arista en $M_2$ de la forma $av$ . Si $a$ forma parte de una arista $av''$ en $M$ eliminar ese borde de $M$ y añada $av'$ a $M$ . Elimine $v'$ de $V'$ y añada $v''$ . Si $a$ no forma parte de una arista $av''$ sólo tiene que añadir $av'$ a $M$ y eliminar $v'$ de $V'$ .

La razón por la que este algoritmo produce una cobertura coincidente $U$ y $V$ es que después de cada paso $M$ es una coincidencia que cubre $M$ . además, una vez $v'$ se elimina de $V$ nunca se vuelve a añadir, porque $M_2$ es coincidente y sólo una arista de $M_2$ contiene $v_1'$ . Por lo tanto, obtenemos un recubrimiento coincidente $U$ y $V$ en un número finito de pasos (como máximo $|V|$ pasos).