Deficiencia (teoría de grafos)

La deficiencia es un concepto en la teoría de grafos que se utiliza para refinar varios teoremas relacionados con el emparejamiento perfecto en grafos, como el teorema del matrimonio de Hall . Esto fue estudiado por primera vez por Øystein Ore . ^{[ 1 ] [ 2 ] : 17} Una propiedad relacionada es el excedente .

Sea G = ( V , E ) un grafo 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. Sea N _G ( U ) el conjunto de vecinos de U , formado por todos los vértices de V que están conectados por una arista a uno o más vértices de U. La deficiencia del conjunto U se define por:

${\displaystyle \mathrm {def} _{G}(U):=|U|-|N_{G}(U)|}$

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 :

${\displaystyle \mathrm {def} (G;X):=\max _{U\subseteq X}\mathrm {def} _{G}(U)}$

A veces , esta cantidad se denomina diferencia crítica de G. ^{[ 3 ]}

Nótese que def _G del subconjunto vacío es 0 , por lo que def( G ; X ) ≥ 0 .

Si def( G; X) = 0, significa que para todos los subconjuntos U de X , |N _G ( U )| ≥ | U |. Por lo tanto, según el teorema del matrimonio de Hall , G admite un emparejamiento perfecto .

Por el contrario, si def( G; X) > 0, significa que para algunos subconjuntos U de X , |N _G ( U )| < | U |. Por lo tanto, según el mismo teorema, G no admite un emparejamiento perfecto . Además, utilizando la noción de deficiencia, es posible enunciar una versión cuantitativa del teorema de Hall:

Demostración . Sea d = def(G;X). Esto significa que, para cada subconjunto U de X , |N _G ( U )| ≥ | U |- d . Añadamos d vértices ficticios a Y y conectemos cada vértice ficticio con todos los vértices de X. Después de la adición, para cada subconjunto U de X , |N _G ( U )| ≥ | U |. Por el teorema de matrimonio de Hall, el nuevo grafo admite un emparejamiento en el que todos los vértices de X están emparejados. Ahora, restauremos el grafo original eliminando los d vértices ficticios; esto deja como máximo d vértices de X sin emparejar.

Este teorema puede enunciarse de forma equivalente como: ^{[ 2 ] : 17}

${\displaystyle \nu (G)=|X|-\operatorname {def} (G;X),}$

donde ν ( G ) es el tamaño de un emparejamiento máximo en G (llamado el número de emparejamiento de G ).

En un grafo bipartito G = ( X + Y , E ), la función de deficiencia es una función de conjunto supermodular : para cada dos subconjuntos X ₁ , X ₂ de X : ^{[ 2 ] : Lem.1.3.2}

${\displaystyle \operatorname {def} _{G}(X_{1}\cup X_{2})+\operatorname {def} _{G}(X_{1}\cap X_{2})\geq \operatorname {def} _{G}(X_{1})+\operatorname {def} _{G}(X_{2})}$

Un subconjunto ajustado es un subconjunto de X cuya deficiencia es igual a la deficiencia de todo el grafo (es decir, es igual al máximo). La intersección y la unión de conjuntos ajustados son ajustadas; esto se deduce de las propiedades de las funciones de conjuntos supermodulares acotadas superiormente. ^{[ 2 ] : Lem.1.3.3}

En un grafo no bipartito, la función de deficiencia, en general, no es supermodular.

Un grafo G posee la propiedad de Hall si se cumple el teorema de matrimonio de Hall para dicho grafo, es decir, si G tiene un emparejamiento perfecto o un conjunto de vértices con deficiencia positiva. Un grafo posee la propiedad de Hall fuerte si def(G) = |V| - 2 ν(G). Obviamente, la propiedad de Hall fuerte implica la propiedad de Hall. Los grafos bipartitos poseen ambas propiedades; sin embargo, existen clases de grafos no bipartitos que también las poseen.

En particular, un grafo tiene la propiedad de Hall fuerte si y solo si es estable : su tamaño máximo de emparejamiento es igual a su tamaño máximo de emparejamiento fraccional . ^{[ 3 ]}

El excedente de un subconjunto U de V se define por:

sur _G ( U )  := |N _G ( U )| − | U | = −def _GRAMO ( U )

El excedente de un grafo G con respecto a 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 )

Nótese la restricción a subconjuntos no vacíos: sin ella, el excedente de todos los grafos siempre sería 0. Nótese también que:

def(G;X) = max[0, −sur( G; X)]

En un grafo bipartito G = ( X + Y , E ), la función excedente es una función de conjunto submodular : para cada dos subconjuntos X ₁ , X ₂ de X :

${\displaystyle \operatorname {sur} _{G}(X_{1}\cup X_{2})+\operatorname {sur} _{G}(X_{1}\cap X_{2})\leq \operatorname {sur} _{G}(X_{1})+\operatorname {sur} _{G}(X_{2})}$

Un subconjunto ajustado con excedente es un subconjunto de X cuyo excedente es igual al excedente de todo el grafo (es decir, es igual al mínimo). La intersección y la unión de conjuntos ajustados con intersección no vacía son ajustados; esto se deduce de las propiedades de las funciones de conjuntos submodulares con límite inferior. ^{[ 2 ] : Lem.1.3.5}

Para un grafo bipartito G con def( G ; X ) = 0, el número sur( G ;X) es el mayor entero s que satisface la siguiente propiedad para cada vértice x en X : si añadimos s nuevos vértices a X y los conectamos a los vértices en N _G ( x ), el grafo resultante tiene un excedente no negativo. ^{[ 2 ] : Teorema 1.3.6}

Si G es un grafo bipartito con un superávit positivo, de modo que eliminar cualquier arista de G disminuye sur( G; X), entonces cada vértice en X tiene grado sur( G ;X)  +  1. ^{[ 4 ]}

Un grafo bipartito tiene un superávit positivo (con respecto a X ) si y solo si contiene un bosque F tal que cada vértice en X tiene grado 2 en F. [ ^{2 ] : Teorema 1.3.8}

Los grafos con superávit positivo desempeñan un papel importante en la teoría de las estructuras de grafos; véase la descomposición de Gallai-Edmonds .

En un grafo no bipartito, la función de excedente, en general, no es submodular.