4.5: Coincidencia en Gráficas Bipartitas

Última actualización
Guardar como PDF

Page ID: 115810

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Template:MathJaxLevin

¡Investiga!

Dada una gráfica bipartita, una coincidencia es un subconjunto de los bordes para los que cada vértice pertenece exactamente a uno de los bordes. Nuestro objetivo en esta actividad es descubrir algún criterio para cuando una gráfica bipartita tiene una coincidencia.

¿La gráfica de abajo contiene una coincidencia? Si es así, encuentra uno.

$image-145.svg$

No todas las gráficas bipartitas tienen emparejamientos. Dibuja tantos ejemplos fundamentalmente diferentes de gráficas bipartitas que NO tengan emparejamientos. Tu objetivo es encontrar todas las obstrucciones posibles para que una gráfica tenga una coincidencia perfecta. Anota las condiciones necesarias para que una gráfica tenga una coincidencia (es decir, rellena el espacio en blanco: Si una gráfica tiene una coincidencia, entonces). Entonces pregúntate si estas condiciones son suficientes (¿es cierto que si, entonces la gráfica tiene una coincidencia?).

Concluimos con un ejemplo más de un problema de teoría gráfica para ilustrar la variedad e inmensidad del sujeto.

Supongamos que tienes una gráfica bipartita$G\text{.}$ Esta consistirá en dos conjuntos de vértices$A$ y$B$ con algunos bordes conectando algunos vértices de$A$ a algunos vértices en$B$ (pero claro, no hay aristas entre dos vértices ambos en$A$ o ambos en$B$). Una coincidencia de$A$ es un subconjunto de los bordes para los cuales cada vértice de$A$ pertenece exactamente a un borde del subconjunto, y ningún vértice en$B$ pertenece a más de un borde en el subconjunto. En la práctica asumiremos que$|A| = |B|$ (los dos conjuntos tienen el mismo número de vértices) por lo que esto dice que cada vértice de la gráfica pertenece exactamente a un borde en la coincidencia. ⁵ Nota: lo que estamos llamando una coincidencia a veces se llama una coincidencia perfecta o una coincidencia completa. Esto se debe a que en ella es interesante mirar también los emparejamientos no perfectos. Llamaremos a esos emparejamientos parciales.

Algún contexto podría hacer que esto sea más fácil de entender. Piense en los vértices en$A$ como que representan a los estudiantes en una clase, y los vértices en$B$ como que representan temas de presentación. Ponemos un borde de un vértice$a \in A$ a un vértice$b \in B$ si estudiante$a$ quisiera presentar sobre tema Por$b\text{.}$ supuesto, algunos alumnos querrían presentar sobre más de un tema, por lo que su vértice tendría grado superior a 1. Como profesor, quieres asignarle a cada alumno su propio tema único. Por lo tanto, desea encontrar una coincidencia de$A\text{:}$ usted elige algún subconjunto de los bordes para que cada estudiante se empareja con exactamente un tema, y ningún tema se empareja con dos estudiantes. ⁶ El ejemplo estándar para los emparejamientos solía ser el problema del matrimonio en el que$A$ consisted of the men in the town, $B$ the women, and an edge represented a marriage that was agreeable to both parties. A matching then represented a way for the town elders to marry off everyone in the town, no polygamy allowed. We have chosen a more progressive context for the sake of political correctness.

La pregunta es: ¿cuándo contiene una gráfica bipartita una coincidencia de$A\text{?}$ Para comenzar a responder a esta pregunta, considere qué podría impedir que la gráfica contenga una coincidencia? Esto no necesariamente nos dirá una condición cuando la gráfica sí tiene una coincidencia, pero al menos es un inicio.

Una forma que no$G$ podría tener una coincidencia es si hay un vértice en$A$ no adyacente a ningún vértice en$B$ (por lo que tiene grado 0). ¿Qué más? ¿Y si a dos estudiantes les gusta el mismo tema y a ningún otro? Entonces después de asignar ese tema al primer alumno, no le queda nada que le guste al segundo alumno, por lo que es mucho como si el segundo alumno tuviera el título 0. O qué pasa si a tres alumnos les gustan sólo dos temas entre ellos. Nuevamente, después de asignar un tema a un alumno, reducimos esto al caso anterior de que a dos estudiantes les gusta solo un tema. Podemos continuar de esta manera con cada vez más estudiantes.

Debe quedar claro en este punto que si hay cada grupo de$n$ alumnos a los que como grupo les gustan$n-1$ o menos temas, entonces no es posible emparejar. Esto es cierto para cualquier valor de$n\text{,}$ y cualquier grupo de$n$ estudiantes.

Para hacer esto más teórico gráfico, digamos que tienes un conjunto$S \subseteq A$ de vértices. Definir$N(S)$ para ser el conjunto de todos los vecinos de vértices en Es$S\text{.}$ decir,$N(S)$ contiene todos los vértices (in$B$) los cuales son adyacentes a al menos uno de los vértices en$S\text{.}$ (En la gráfica estudiante/tema,$N(S)$ se encuentra el conjunto de temas que les gusta a los alumnos de $S\text{.}$) Nuestra discusión anterior se puede resumir de la siguiente manera:

Condición coincidente

Si una gráfica bipartita$G = \{A, B\}$ tiene una coincidencia de$A\text{,}$ entonces

\ start {ecuación*} |N (S) |\ ge |S|\ end {ecuación*}

para todos$S \subseteq A\text{.}$

¿Es cierto lo contrario? Supongamos que$G$ satisface la condición coincidente$|N(S)| \ge |S|$ para todos$S \subseteq A$ (cada conjunto de vértices tiene al menos tantos vecinos que vértices en el conjunto). ¿Significa eso que hay una coincidencia? Sorprendentemente, sí. La condición necesaria obvia también es suficiente. ⁷ Esto sucede a menudo en la teoría gráfica. Si puedes evitar los obvios contraejemplos, a menudo obtienes lo que quieres. Este es un teorema probado por primera vez por Philip Hall en 1935. ⁸ También hay una versión infinita del teorema que fue probada por Marshal Hall, Jr. El nombre es una coincidencia aunque ya que los dos Salones no están relacionados.

Teorema 4.5.1 Teorema del matrimonio de Hall

Dejar$G$ ser una gráfica bipartita con conjuntos$A$ y$B\text{.}$ luego$G$ tiene una coincidencia de$A$ si y solo si

\ start {ecuación*} |N (S) |\ ge |S|\ end {ecuación*}

para todos$S \subseteq A\text{.}$

Hay bastantes pruebas diferentes de este teorema: una búsqueda rápida en Internet te ayudará a comenzar.

Además de su aplicación a temas de matrimonio y presentación estudiantil, los emparejamientos tienen aplicaciones por todas partes. Concluimos con uno de esos ejemplos.

Ejemplo$\PageIndex{1}$

Supongamos que reparte 52 naipes regulares en 13 montones de 4 cartas cada uno. Demuestra que siempre puedes seleccionar una carta de cada pila para obtener uno de cada uno de los 13 valores de cartas As, 2, 3,..., 10, Jack, Reina y Rey.

Solución

Hacer esto directamente sería difícil, pero podemos usar la condición coincidente para ayudar. Construir una gráfica$G$ with 13 vertices in the set $A\text{,}$ each representing one of the 13 card values, and 13 vertices in the set $B\text{,}$ each representing one of the 13 piles. Draw an edge between a vertex $a \in A$ to a vertex $b \in B$ if a card with value $a$ is in the pile $b\text{.}$ Notice that we are just looking for a matching of $A\text{;}$ each value needs to be found in the piles exactly once.

Tendremos una coincidencia si la condición coincidente se mantiene. Dado cualquier conjunto de valores de tarjeta (un conjunto$S \subseteq A$) we must show that $|N(S)| \ge |S|\text{.}$ That is, the number of piles that contain those values is at least the number of different values. But what if it wasn't? Say $|S| = k\text{.}$ If $|N(S)| < k\text{,}$ then we would have fewer than $4k$ different cards in those piles (since each pile contains 4 cards). But there are $4k$ cards with the $k$ different values, so at least one of these cards must be in another pile, a contradiction. Thus the matching condition holds, so there is a matching, as required.