La deficiencia es un concepto en la teoría de grafos que se utiliza para refinar varios teoremas relacionados con la correspondencia perfecta en gráficos, como el teorema del matrimonio de Hall . Fue estudiado por primera vez por Øystein Ore . [1] [2] : 17 Una propiedad relacionada es excedente .
Definición de deficiencia
Sea G = ( V , E ) un gráfico y sea U un conjunto independiente de vértices, es decir, U es un subconjunto de V en el que no hay dos vértices conectados por una arista. Let N G ( U ) denota el conjunto de vecinos de U , que está formado por todos los vértices de 'V' que están conectados por un borde a una o más vértices de U . La deficiencia del conjunto U se define por:
Supongamos que G es un grafo bipartito , con bipartición V = X ∪ Y . La deficiencia de G con respecto a una de sus partes (digamos X ), es la deficiencia máxima de un subconjunto de X :
A veces esta cantidad se llama la diferencia crítica de G . [3]
Tenga en cuenta que def G del subconjunto vacío es 0, por lo que def ( G; X) ≥ 0.
Deficiencia y emparejamientos
Si def ( G; X) = 0, significa que para todos los subconjuntos U de X , | N G ( U ) | ≥ | U |. Por tanto, según el teorema del matrimonio de Hall , G admite una coincidencia perfecta .
Por el contrario, si def ( G; X)> 0, significa que para algunos subconjuntos U de X , | N G ( U ) | <| U |. Por tanto, según el mismo teorema, G no admite una correspondencia perfecta . Además, utilizando la noción de deficiencia, es posible enunciar una versión cuantitativa del teorema de Hall:
Teorema : todo gráfico bipartito G = ( X + Y , E ) admite una coincidencia en la que, como máximo , los vértices def ( G ; X ) de X no coinciden .
Prueba . Sea d = def (G; X). Esto significa que, para cada subconjunto U de X , | N G ( U ) | ≥ | U | - d . Añadir d vértices ficticias para Y , y conectar cada vértice ficticia para todos los vértices de X . Después de la adición, para cada subconjunto U de X , | N G ( U ) | ≥ | U |. Según el teorema del matrimonio de Hall, el nuevo gráfico admite una coincidencia en la que todos los vértices de X coinciden. Ahora, restaurar el gráfico original mediante la eliminación de la d maniquí vértices; esto deja como máximo d vértices de X sin emparejar.
Este teorema puede expresarse de manera equivalente como: [2] : 17
donde ν ( G ) es el tamaño de una coincidencia máxima en G (llamado número de coincidencia de G ).
Propiedades de la función de deficiencia
En un gráfico bipartito G = ( X + Y , E ), la función de deficiencia es una función de conjunto supermodular : para cada dos subconjuntos X 1 , X 2 de X : [2] : Lem.1.3.2
Un subconjunto ajustado es un subconjunto de X cuya deficiencia es igual a la deficiencia de todo el gráfico (es decir, es igual al máximo). La intersección y unión de conjuntos apretados son estrechos; esto se sigue de las propiedades de las funciones de conjuntos supermodulares de límite superior. [2] : Lem.1.3.3
En un gráfico no bipartito, la función de deficiencia, en general, no es supermodular.
Propiedad de Strong Hall
Un gráfico G tiene la propiedad de Hall si el teorema del matrimonio de Hall se cumple para ese gráfico, es decir, si G tiene una coincidencia perfecta o un conjunto de vértices con una deficiencia positiva. Un gráfico tiene la propiedad Hall fuerte si def (G) = | V | - 2 ν (G). Obviamente, la propiedad Hall fuerte implica la propiedad Hall. Los gráficos bipartitos tienen estas dos propiedades, sin embargo, hay clases de gráficos no bipartitos que tienen estas propiedades.
En particular, un gráfico tiene la propiedad Hall fuerte si, y solo si es estable , su tamaño de coincidencia máximo es igual a su tamaño de coincidencia fraccional máximo . [3]
Superávit
El excedente de un subconjunto U de V se define por:
sur G ( U ): = | N G ( U ) | - | U | = - def G ( U )
El excedente de un gráfico G wrt un subconjunto X se define por el excedente mínimo de subconjuntos no vacíos de X : [2] : 19
sur ( G; X): = min [ U un subconjunto no vacío de X ] sur G ( U )
Tenga en cuenta la restricción a los subconjuntos no vacíos: sin ella, el excedente de todos los gráficos siempre sería 0. Tenga en cuenta también que:
def (G; X) = max [0, - sur ( G; X)]
En un gráfico bipartito G = ( X + Y , E ), la función excedente es una función de conjunto submodular : para cada dos subconjuntos X 1 , X 2 de X :
Un subconjunto ajustado al excedente es un subconjunto de X cuyo excedente es igual al excedente de todo el gráfico (es decir, es igual al mínimo). La intersección y unión de conjuntos estrechos con intersección no vacía son estrechas; esto se sigue de las propiedades de las funciones de conjuntos submodulares de límite inferior. [2] : Lem.1.3.5
Para un gráfico bipartito G con def ( G ; X ) = 0, el número sur ( G; X) es el entero más grande s que satisface la siguiente propiedad para cada vértice x en X : si sumamos s nuevos vértices a X y los conectamos a los vértices en N G ( x ), el gráfico resultante tiene un superávit no negativo. [2] : Thm.1.3.6
Si G es un gráfico bipartito con un superávit positivo, tal que eliminar cualquier borde de G disminuye sur ( G; X), entonces cada vértice en X tiene grado sur ( G; X) +1. [4]
Un grafo bipartito tiene un excedente positivo (wrt X ) si-y de sólo-si contiene un bosque F de tal manera que cada vértice en X tiene grado 2 en F . [2] : Thm.1.3.8
Los gráficos con un superávit positivo juegan un papel importante en la teoría de las estructuras de los gráficos; vea la descomposición de Gallai-Edmonds .
En un gráfico no bipartito, la función de superávit, en general, no es submodular.
Referencias
- ↑ Ore, Oystein (1 de diciembre de 1955). "Gráficos y teoremas de emparejamiento" . Diario de matemáticas de Duke . 22 (4): 625–639. doi : 10.1215 / S0012-7094-55-02268-7 . ISSN 0012-7094 .
- ^ a b c d e f g h Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ a b Beckenbach, Isabel; Borndörfer, Ralf (1 de octubre de 2018). "Teorema de Hall y Kőnig en gráficos e hipergráficos" . Matemáticas discretas . 341 (10): 2753–2761. doi : 10.1016 / j.disc.2018.06.013 . ISSN 0012-365X .
- ^ Lovász, L. (1 de septiembre de 1970). "Una generalización del teorema de Kónig". Acta Mathematica Academiae Scientiarum Hungaricae . 21 (3): 443–446. doi : 10.1007 / BF01894789 . ISSN 1588-2632 . S2CID 121333106 .