Emparejamiento fraccional

En teoría de grafos , una coincidencia fraccionaria es una generalización de una coincidencia en la que, intuitivamente, cada vértice se puede dividir en fracciones que coinciden con diferentes vértices vecinos.

Definición

Dado un gráfico G = ( V , E ), una coincidencia fraccionaria en G es una función que asigna, a cada arista e en E , una fracción f ( e ) en [0, 1], tal que para cada vértice v en V , la suma de fracciones de aristas adyacentes a v es como máximo 1: ^[1] Una coincidencia en el sentido tradicional es un caso especial de coincidencia fraccionaria, en el que la fracción de cada arista es 0 o 1: f ( e ) = 1 si e está en la coincidencia, y f ( e ) = 0 si no lo está. Por esta razón, en el contexto de los emparejamientos fraccionarios, los emparejamientos habituales a veces se denominan emparejamientos integrales . $${\displaystyle \forall v\in V:\sum _{e\ni v}f(e)\leq 1}$$

El tamaño de una coincidencia integral es el número de aristas en la coincidencia, y el número de coincidencia de un gráfico G es el tamaño más grande de una coincidencia en G. De manera análoga, el tamaño de una coincidencia fraccionaria es la suma de las fracciones de todos los bordes. El número de coincidencia fraccionaria de un gráfico G es el tamaño más grande de una coincidencia fraccionaria en G. A menudo se denota por . ^[2] Dado que una coincidencia es un caso especial de una coincidencia fraccionaria, para cada gráfico G se tiene que el número integral de coincidencia de G es menor o igual al número fraccionario de coincidencia de G ; en símbolos: Un gráfico en el que se llama gráfico estable . ^[3] Todo gráfico bipartito es estable; esto significa que en cada gráfico bipartito, el número coincidente fraccionario es un número entero y es igual al número coincidente integral. ${\displaystyle \nu (G)}$ ${\displaystyle \nu ^{*}(G)}$ $${\displaystyle \nu (G)\leq \nu ^{*}(G).}$$ ${\displaystyle \nu (G)=\nu ^{*}(G)}$

En un gráfico general, el número coincidente fraccionario es un número entero o un medio entero. ^[4] ${\displaystyle \nu (G)>{\frac {2}{3}}\nu ^{*}(G).}$

Presentación matricial

Para un gráfico bipartito G = ( X + Y , E ), una coincidencia fraccionaria se puede presentar como una matriz con | X | filas y | Y | columnas. El valor de la entrada en la fila x y la columna y es la fracción del borde ( x , y ).

Coincidencia fraccionaria perfecta

Una coincidencia fraccionaria se llama perfecta si la suma de los pesos adyacentes a cada vértice es exactamente 1. El tamaño de una coincidencia perfecta es exactamente | V |/2.

En un gráfico bipartito G = ( X + Y , E ), una coincidencia fraccionaria se llama X-perfecta si la suma de los pesos adyacentes a cada vértice de X es exactamente 1. El tamaño de una coincidencia fraccionaria X -perfecta es exactamente | X |.

Para un gráfico bipartito G = ( X + Y , E ), lo siguiente es equivalente:

• G admite una X -integral perfecta,
• G admite una coincidencia fraccionaria perfecta X , y
• G satisface la condición del teorema del matrimonio de Hall .

La primera condición implica la segunda porque una coincidencia integral es una coincidencia fraccionaria. El segundo implica el tercero 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 a al menos | W | vértices de Y . Según el teorema del matrimonio de Hall , la última condición implica la primera. ^{[5] [ se necesita una mejor fuente ]}

En un gráfico general, las condiciones anteriores no son equivalentes: la coincidencia fraccionaria más grande puede ser mayor que la coincidencia integral más grande. Por ejemplo, un ciclo de 3 admite una coincidencia fraccionaria perfecta de tamaño 3/2 (la fracción de cada arista es 1/2), pero no admite una coincidencia integral perfecta: la coincidencia integral más grande es de tamaño 1.

Aspectos algorítmicos

La coincidencia fraccionaria más grande en un gráfico se puede encontrar fácilmente mediante programación lineal o, alternativamente, mediante un algoritmo de flujo máximo . En un gráfico bipartito, es posible convertir una coincidencia fraccionaria máxima en una coincidencia integral máxima del mismo tamaño. Esto conduce a un algoritmo simple de tiempo polinomial para encontrar una coincidencia máxima en un gráfico bipartito. ^[6]

Si G es un gráfico bipartito con | X | = | Y | = n y M es una coincidencia fraccionaria perfecta, entonces la representación matricial de M es una matriz doblemente estocástica : la suma de elementos en cada fila y cada columna es 1. El algoritmo de Birkhoff se puede usar para descomponer la matriz en una suma convexa de como máximo n ² -2 n +2 matrices de permutación. Esto corresponde a descomponer M en una suma convexa de como máximo n ² -2 n +2 coincidencias perfectas.

Coincidencia fraccionaria de máxima cardinalidad

Se puede encontrar una coincidencia fraccionaria de cardinalidad máxima (es decir, suma máxima de fracciones) mediante programación lineal . También existe un algoritmo de tiempo fuertemente polinomial, ^[7] que utiliza rutas de aumento , que se ejecuta en el tiempo . ${\displaystyle O(|V||E|)}$

Coincidencia fraccionaria de peso máximo

Supongamos que cada borde del gráfico tiene un peso. Se puede encontrar una coincidencia fraccionaria del peso máximo en un gráfico mediante programación lineal . En un gráfico bipartito, es posible convertir una coincidencia fraccionaria de peso máximo en una coincidencia integral de peso máximo del mismo tamaño, de la siguiente manera: ^[8]

• Sea f el emparejamiento fraccionario.
• Sea H un subgrafo de G que contiene solo los bordes e con fracción no integral, 0< f ( e )<1.
• Si H está vacío, entonces hemos terminado.
• si H tiene un ciclo, entonces debe ser de longitud par (ya que la gráfica es bipartita), por lo que podemos construir una nueva coincidencia fraccionaria f ₁ transfiriendo una pequeña fracción ε de aristas pares a aristas impares, y una nueva coincidencia fraccionaria f ₂ transfiriendo ε de aristas impares a aristas pares. Como f es el promedio de f ₁ y f ₂ , el peso de f es el promedio entre el peso de f ₁ y f ₂ . Dado que f tiene un peso máximo, las tres coincidencias deben tener el mismo peso. Existe una opción de ε para la cual al menos una de f ₁ o f ₂ tiene menos fracciones no integrales. Continuando de la misma manera se llega a una coincidencia integral del mismo peso.
• Supongamos que H no tiene ciclo y sea P el camino más largo en H. La fracción de cada arista adyacente al primer o último vértice en P debe ser 0 (si es 1, la primera/última arista en P viola la condición de coincidencia fraccionaria; si está en (0,1), entonces P no es el mas largo). Por lo tanto, podemos construir nuevas coincidencias fraccionarias f ₁ y f ₂ transfiriendo ε de aristas impares a aristas pares o viceversa. Nuevamente, f ₁ y f ₂ deben tener el peso máximo y al menos uno de ellos tiene menos fracciones no integrales.

Politopo de coincidencia fraccional

Dado un gráfico G = ( V , E ), el politopo de coincidencia fraccional de G es un politopo convexo que representa todas las coincidencias fraccionarias posibles de G. Es un politopo en R ^{| mi |} - el | E | Espacio euclidiano dimensional. Cada punto ( x ₁ ,..., x _|E| ) en el politopo representa una coincidencia en la que la fracción de cada arista e es x _e . El politopo está definido por | mi | restricciones de no negatividad ( x _e ≥ 0 para todo e en E ) y | V | restricciones de vértice (la suma de x _e , para todos los bordes e que son adyacentes a un vértice v , es como máximo 1). En un gráfico bipartito, los vértices del politopo coincidente fraccionario son todos integrales.

Referencias

1. Aharoni, Ron; Kessler, Ofra (15 de octubre de 1990). "Sobre una posible extensión del teorema de Hall a hipergrafías bipartitas". Matemáticas discretas . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN  0012-365X.
2. Liu, Yan; Liu, Guizhen (2002). "Los números fraccionarios coincidentes de gráficos". Redes . 40 (4): 228–231. doi :10.1002/net.10047. ISSN  1097-0037. S2CID  43698695.
3. Beckenbach, Isabel; Borndörfer, Ralf (1 de octubre de 2018). "Teorema de Hall y Kőnig en gráficas e hipergrafías". Matemáticas discretas . 341 (10): 2753–2761. doi : 10.1016/j.disc.2018.06.013 . ISSN  0012-365X. S2CID  52067804.
4. Füredi, Zoltán (1 de junio de 1981). "Coincidencias fraccionarias y de grado máximo en hipergrafías uniformes". Combinatoria . 1 (2): 155–162. doi :10.1007/BF02579271. ISSN  1439-6912. S2CID  10530732.
5. "co.combinatorics - Versión de correspondencia fraccionada del teorema del matrimonio de Hall". Desbordamiento matemático . Consultado el 29 de junio de 2020 .
6. Gartner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.
7. Bourjolly, Jean-Marie; Pulleyblank, William R. (1 de enero de 1989). "Gráficos de König-Egerváry, gráficos 2 bicríticos y emparejamientos fraccionarios". Matemática Aplicada Discreta . 24 (1): 63–82. doi : 10.1016/0166-218X(92)90273-D . ISSN  0166-218X.
8. Vazirani, Umesh (2012). "Coincidencias ponderadas máximas" (PDF) . UC Berkeley .

Ver también

• Coloración fraccionada