Teorema de König (combinatoria)

En la teoría de grafos, el teorema de König (el teorema de König-Egerváry, el teorema húngaro [1] ) , demostrado por Denes König en 1931 [2] , afirma la equivalencia de los problemas de encontrar la coincidencia más grande y la cobertura de vértice más pequeña en bipartito gráficos _ Fue descubierto de forma independiente, en el mismo 1931 [3] , por Jeno Egervari en una forma algo más general para el caso de los gráficos ponderados .

Definiciones

Un grafo se llama bipartito si sus vértices se pueden dividir en dos conjuntos de modo que cada arista tenga sus vértices finales en conjuntos diferentes.

La cubierta de vértices de un gráfico es un conjunto de vértices tales que cualquier borde del gráfico tiene al menos un vértice final de este conjunto. Una cubierta de vértices se llama la más pequeña si ninguna otra cubierta de vértices tiene menos vértices.

Una coincidencia en un gráfico es un conjunto de aristas que no tienen vértices finales comunes. Una coincidencia se llama la más grande si ninguna otra coincidencia tiene más aristas.

Enunciado del teorema

En cualquier gráfico bipartito , el número de aristas en la coincidencia más grande es igual al número de vértices en la cubierta de vértice más pequeña.

Ejemplo

El grafo bipartito de la figura anterior tiene 7 vértices en cada una de las partes. Una coincidencia con 6 aristas se resalta en azul y una cubierta de vértice se resalta en rojo. Esta cubierta es la más pequeña en tamaño, ya que cualquier vértice de la cubierta debe incluir al menos un vértice final de un borde coincidente. De la misma manera, no existe coincidencia mayor, ya que cualquier arista coincidente debe contener al menos un vértice final de la cubierta de vértice, por lo que esta coincidencia es la mayor. El teorema de Koenig simplemente afirma la igualdad de los tamaños de la coincidencia y la cubierta (en este ejemplo, ambos números son iguales a seis). ${\ estilo de visualización \{x_{2},x_{4},x_{5},y_{2},y_{4},y_{6}\))$

Prueba

Sea un grafo bipartito dado , y sea la coincidencia más grande en . ${\ estilo de visualización G = (X, Y, E)}$ $METRO$ $GRAMO$

Primero, considere el caso cuando la coincidencia satura todos los vértices de la fracción , es decir, el tamaño de la coincidencia es igual a . Obviamente, toda la parte es una cubierta de vértice en el gráfico , por lo tanto, también es la cubierta de vértice más pequeña, y en este caso la afirmación del teorema es verdadera. $METRO$ $X$ $METRO$ $|X|$ $X$ $GRAMO$

De lo contrario, tomamos todos los vértices de la parte que no están saturados con matching y ejecutamos un recorrido transversal desde ellos de acuerdo con la siguiente regla: $X$ $METRO$

De izquierda a derecha, pasamos solo por los bordes que no están incluidos ( los llamaremos negros). $METRO$
De derecha a izquierda, pasamos solo por los bordes incluidos en (los llamaremos azules). $METRO$

Sean y los subconjuntos de los vértices de las partes izquierda y derecha visitadas durante el recorrido, y y los subconjuntos de los vértices no visitados, respectivamente (ver la figura de la derecha). ${\ estilo de visualización X^{+))$ $Y^{+}$ ${\ estilo de visualización X^{-}}$ $Y^{-}$

No hay aristas negras entre los conjuntos y , porque de lo contrario durante el recorrido visitaríamos vértices del conjunto . Por una razón similar, no hay bordes azules entre los conjuntos y . ${\ estilo de visualización X^{+))$ $Y^{-}$ $Y^{-}$ ${\ estilo de visualización X^{-}}$ $Y^{+}$

Probemos que no hay bordes azules entre los conjuntos y tampoco. Por el contrario , que haya tal ventaja . El vértice no puede ser el punto de partida de un paseo en anchura, ya que está saturado de coincidencias . Por lo tanto, la caminata de amplitud primero vino de algún vértice a lo largo del borde azul, lo que significa que dos bordes azules y son incidentes al vértice . Pero esto es imposible, ya que los bordes azules forman una coincidencia. ${\ estilo de visualización X^{+))$ $Y^{-}$ ${\ estilo de visualización \ {x^{+},y^{-}\}}$ ${\ estilo de visualización x^{+))$ $METRO$ ${\ estilo de visualización x^{+))$ ${\ estilo de visualización y^{+))$ ${\ estilo de visualización x^{+))$ ${\ estilo de visualización \ {x^{+},y^{-}\}}$ ${\ estilo de visualización \ {x^{+},y^{+}\}}$

Por lo tanto, cualquier arista del grafo G incide en un vértice desde o en un vértice desde , es decir, es una cubierta de vértice. Demostremos que todos los vértices en están saturados con coincidencias . Para los vértices de , esto es obvio, ya que por construcción todos los vértices no saturados de la parte izquierda se encuentran en . Si hay un vértice no saturado en , entonces hay un camino alterno que termina en él, lo que contradice el hecho de que la coincidencia es la más grande. Ahora queda recordar que entre los conjuntos y no hay aristas desde , es decir, cada arista del emparejamiento es incidente con exactamente un vértice desde la cubierta de vértice . Por lo tanto, , y la cobertura de vértices es la más pequeña [4] . ${\ estilo de visualización X^{-}}$ $Y^{+}$ ${\displaystyle X^{-}\taza Y^{+))$ ${\displaystyle X^{-}\taza Y^{+))$ $METRO$ ${\ estilo de visualización X^{-}}$ ${\ estilo de visualización X^{+))$ $Y^{+}$ $METRO$ $METRO$ ${\ estilo de visualización X^{-}}$ $Y^{+}$ $METRO$ ${\displaystyle X^{-}\taza Y^{+))$ $|M|=|X^{-}\cup Y^{+}|$ ${\displaystyle X^{-}\taza Y^{+))$

Demostración a través del teorema de Ford-Fulkerson

La tarea de encontrar la coincidencia más grande en un gráfico se puede reducir a encontrar el flujo más grande en la red de transporte , de modo que desde la fuente hasta la primera parte y desde la segunda parte hasta el drenaje hay bordes de capacidad , y para cualquier borde del gráfico original, de a hay un borde de capacidad . ${\ estilo de visualización G = (A, B, E)}$ ${\displaystyle G'_{\infty ))$ $s$ $A$ $B$ $t$ $una$ ${\ estilo de visualización (a, b) \ en E}$ $a$ $b$ $+\infty$

De acuerdo con el teorema de Ford-Fulkerson , el valor de dicho flujo es igual al valor del corte mínimo . Deje que tal corte esté dado por conjuntos de vértices y . Los vértices del grafo original se pueden dividir en cuatro grupos tales que y , mientras y . Con tal clasificación, el gráfico original no puede tener bordes de a , ya que dichos bordes harían infinito el tamaño del corte. ${\displaystyle G'_{\infty ))$ $S$ $T$ ${\ estilo de visualización A_{S},A_{T},B_{S},B_{T})$ $A=A_{S}\taza A_{T}$ ${\displaystyle B=B_{S}\taza B_{T))$ $A_{S},B_{S}\subconjunto S$ $A_{T},B_{T}\subconjunto T$ ${\ estilo de visualización A_ {S}}$ ${\ estilo de visualización B_ {T}}$

Esto, a su vez, implica que cualquier borde del grafo incide en un vértice de , o un vértice de . Al mismo tiempo, el corte en sí se compone de aristas de hasta y de hasta . Así, por un lado, es la cobertura de vértice del gráfico original, por otro lado, el valor del corte mínimo en el gráfico es , lo que implica que el conjunto es la cobertura de vértice mínimo del gráfico [5] . ${\ estilo de visualización A_ {T}}$ ${\ estilo de visualización B_ {S}}$ $s$ ${\ estilo de visualización A_ {T}}$ ${\ estilo de visualización B_ {S}}$ $t$ $A_{T}\taza B_{S}$ $|A_{T}|+|B_{S}|$ $A_{T}\taza B_{S}$ $GRAMO$

Corolario del teorema de König

Sean y , respectivamente, la coincidencia más grande y la cobertura de vértice más pequeña en un gráfico bipartito . Entonces cualquier arista desde es incidente a exactamente un vértice desde . Por el contrario, a cualquier vértice en exactamente un borde de es incidente . En otras palabras, la relación de incidencia define una biyección entre los conjuntos y . $METRO$ $C$ $GRAMO$ $METRO$ $C$ $C$ $METRO$ $METRO$ $C$

Tenga en cuenta que si el gráfico no fuera bipartito, entonces dos vértices de , y algunos vértices de , podrían no tener aristas incidentes de . $GRAMO$ $METRO$ $C$ $C$ $METRO$

Un algoritmo para construir la cubierta de vértice más pequeña en un gráfico bipartito

La caminata primero en anchura descrita anteriormente a partir de la prueba del teorema construye la cubierta de vértice más pequeña dada la coincidencia más grande. [4] Este algoritmo tiene complejidad . La coincidencia más grande en un gráfico bipartito se puede encontrar mediante el algoritmo de Hopcroft-Karp en el tiempo . $O(|E|)$ ${\textstyle O(|E|{\sqrt {|V|)))}$

Conexión con gráficos perfectos

Se dice que un grafo es perfecto si, para cualquier subgrafo generado , su número cromático es igual al tamaño de la camarilla máxima . Cualquier gráfico bipartito es perfecto ya que cualquiera de sus subgráficos es bipartito o independiente. En un grafo bipartito que no es independiente, el número cromático y el tamaño de la camarilla máxima son dos, mientras que para un conjunto independiente ambos números son iguales a uno.

Un grafo es perfecto si y solo si su complemento es perfecto [6] , y el teorema de König puede considerarse equivalente a la afirmación de que el complemento de un grafo bipartito es perfecto. Cualquier coloración complementaria de un gráfico bipartito tiene un tamaño máximo de 2, y las clases de tamaño 2 forman coincidencias. Las camarillas en el complemento de un grafo G son un conjunto independiente en G , y, como escribimos anteriormente, un conjunto independiente en un grafo bipartito G es el complemento de una cubierta de vértice G . Así, cualquier coincidencia de M en un grafo bipartito G con n vértices corresponde a una coloración del complemento de G con n -| m | colores, que, en vista de la perfección del complemento de grafos bipartitos, corresponde a un conjunto independiente en G con n -| m | vértices, que corresponde a la cubierta de vértice G | m | picos Por tanto, el teorema de Koenig demuestra la perfección de los complementos de grafos bipartitos, es decir, resultado expresado de forma más explícita por Gallai [7] .

También se puede relacionar el teorema de coloración de líneas de König con otra clase de gráficos perfectos, los gráficos lineales de gráficos bipartitos. Para un gráfico G , el gráfico lineal L ( G ) tiene vértices correspondientes a las aristas de G , y una arista para cada par de aristas adyacentes en G . Así, el número cromático L ( G ) es igual al índice cromático G. Si G es bipartito, las camarillas en L ( G ) son exactamente los conjuntos de aristas en G que tienen un vértice final común. Ahora, el teorema de coloración de líneas de König, que establece que el índice cromático es igual al grado máximo de vértices en un gráfico bipartito, puede interpretarse como que el gráfico lineal de un gráfico bipartito es perfecto.

Dado que las gráficas lineales de las gráficas bipartitas son perfectas, los complementos de las gráficas lineales de las gráficas bipartitas también lo son. Una camarilla en el complemento de un gráfico lineal para G es simplemente una coincidencia de G . Y la coloración del complemento de un gráfico lineal para G , si G es bipartito, es una partición de los bordes del gráfico G en subconjuntos de bordes que tienen vértices comunes. Los vértices finales que son comunes en estos subconjuntos forman una cubierta de vértice del grafo G. Por lo tanto, el propio teorema de König también puede interpretarse como que el complemento de los gráficos lineales de los gráficos bipartitos es perfecto.

Adiciones

Para los gráficos que no son bipartitos, la situación con los problemas de mayor coincidencia y menor cobertura de vértices es bastante diferente: la mayor coincidencia se puede encontrar en tiempo polinomial para cualquier gráfico, mientras que encontrar la menor cobertura de vértices es un problema NP-completo . Completar una cubierta de vértices para cualquier gráfico es un conjunto independiente , y encontrar el conjunto independiente más grande es otro problema NP-completo.
El teorema de König es equivalente a una serie de otros teoremas minimax en teoría de grafos y combinatoria , como el teorema de la boda de Hall y el teorema de Dilworth . Dado que la coincidencia en gráficos bipartitos es un caso especial de flujo de red, el teorema de König también se deriva del teorema de Ford-Fulkerson . [ocho]
En Internet y en la literatura científica rusa, es común la siguiente formulación del teorema: si una matriz rectangular está compuesta de ceros y unos, entonces el número mínimo de líneas que contienen todos los unos es igual al número máximo de unos que pueden ser elegido de modo que no haya dos de ellos en una misma línea (el término "línea" significa una fila o una columna en una matriz). [9]

A pesar de la equivalencia de los dos problemas en términos de solución exacta, no son en absoluto equivalentes para los algoritmos de aproximación . El problema de coincidencia más grande para gráficos bipartitos se puede aproximar a una precisión arbitraria en tiempo constante usando algoritmos distribuidos , en contraste con el problema de cobertura de vértice mínimo, que requiere al menos un tiempo logarítmico. [diez]

Notas

↑ Evnin, 2005 .
↑ Konig, 1931 .
↑ Egerváry, 1931 .
↑ 12 Bondy , 1976 , págs. 74-75.
↑ Cesa-Bianchi, Nicolò Matchings and the max-flow min-cut theorem (11 de abril de 2020). Archivado desde el original el 9 de mayo de 2021. (indefinido)
↑ Lovas, Plummer, 1998 , pág. 567.
↑ Gallai, 1958 .
↑ Lovas, Plummer, 1998 , pág. 89.
↑ Rybnikov, 1972 , pág. 100.
↑ Goös, 2012 .

Enlaces

Lovas L., Plummer M. Problemas aplicados de teoría de grafos. Teoría de emparejamientos en matemáticas, física, química. — M.: Mir, 1998. — 653 p. — ISBN 5-03-002517-0 .
Rybnikov K. A. Introducción al análisis combinatorio. - Universidad Estatal de Moscú, 1972.

Evnin A. Yu. Alrededor del teorema de Hall // Matemáticas. arr.. - 2005. - T. 3 (34) . - S. 2-23 . (Ruso)

Bondy, JA, Murty, USR Teoría de grafos con aplicaciones. - Holanda Septentrional, 1976. - ISBN 0-444-19451-7 .

Egervary, Jenő. Matrixok kombinatorius tulajdonságairól [Sobre las propiedades combinatorias de las matrices] (Hung.) // Matematikai és Fizikai Lapok. - 1931. - Vol. 38. - Pág. 16-28.

Gallai, Tibor. Máximo-mínimo Sätze über Graphen // Acta Math. Academia ciencia Hungría.. - 1958. - vol. 9.- Emisión. 3-4 . - Pág. 395-434. -doi : 10.1007/ BF02020271 .

Vaya, Mika. Jukka Suomela. 26º Simposio Internacional de Computación Distribuida (DISC), Salvador, Brasil, octubre de 2012. - 2012.

König, Denes. Gráfok és mátrixok (húngaro) // Matematikai és Fizikai Lapok. - 1931. - Vol. 38. - Pág. 116-119.