Fórmula de Tatta-Berge

La fórmula de Tutt-Berge es una fórmula teórica de gráficos que determina el tamaño de la coincidencia más grande en un gráfico . Es una generalización del teorema de coincidencia de Tutt ; establecido y probado por Claude Berg .

El teorema establece que el tamaño de la coincidencia más grande en un gráfico es: $G=(V,E)$

{\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {impar} (GU)+|V|\right)

donde es el número de componentes conectados del gráfico que tiene un número impar de vértices. $\operatorname {impar} (H)$ $H$

Explicación

Es intuitivamente claro que para cualquier subconjunto de vértices , la única forma de cubrir completamente un componente con un número impar de vértices es seleccionar una arista en el emparejamiento que conecte uno de los vértices con . Si un componente con un número impar de vértices no tiene esa arista en el emparejamiento, parte del emparejamiento cubrirá los vértices del componente, pero dado que el número de vértices es impar, al menos un vértice quedará sin cubrir. Por lo tanto, si algún subconjunto de vértices tiene un tamaño pequeño, pero cuando se elimina, se crea una gran cantidad de componentes impares, entonces habrá muchos vértices no cubiertos por la coincidencia, lo que implica que la coincidencia será pequeña. Este razonamiento se puede hacer riguroso si tenemos en cuenta que el tamaño de la coincidencia más grande no supera el valor dado por la fórmula de Tutt-Berge. $tu$ ${\ estilo de visualización GU}$ ${\ estilo de visualización GU}$ $tu$ $tu$

La fórmula muestra que esta restricción es el único obstáculo para obtener una coincidencia mayor: el tamaño de la coincidencia óptima está determinado por el subconjunto que tiene la mayor diferencia entre el número de componentes impares en el exterior y los vértices en el interior . Es decir, siempre hay un subconjunto exacto cuya eliminación produce el número correcto de componentes impares que satisfacen la fórmula. Una forma de obtener un conjunto de este tipo es elegir cualquier coincidencia más grande e incluirla en vértices que no estén cubiertos por la coincidencia o que se puedan alcanzar desde un vértice descubierto mediante un camino alterno [1] que termina con una arista de la coincidencia. Habiendo definido como el conjunto de vértices que se conectan por emparejamiento con vértices de , resulta que dos vértices de no pueden ser adyacentes, de lo contrario es posible conectar dos vértices descubiertos de forma alterna, lo que contradice la maximalidad [2] . Cualquier vecino de un vértice de debe pertenecer a , de lo contrario, podemos extender la ruta alterna a por un par de aristas a los vecinos, lo que hace que los vecinos se conviertan en parte de . Así, en , cualquier vértice forma parte de un vértice, es decir, tiene un número impar de vértices. No puede haber otros componentes impares ya que todos los demás vértices permanecen emparejados después de la eliminación de . $tu$ $tu$ $tu$ $tu$ $tu$ $METRO$ $X$ $METRO$ $tu$ $METRO$ $X$ $X$ $METRO$ $X$ $X$ $tu$ $X$ $tu$ ${\ estilo de visualización GU}$ $X$ $tu$

Conexión con el teorema de Tutt

El teorema de coincidencia de Tutt describe los gráficos con coincidencias perfectas como gráficos para los que la eliminación de cualquier subconjunto de vértices produce un máximo de componentes impares. (Un subconjunto que contiene al menos componentes impares siempre se puede encontrar como el conjunto vacío ). En este caso, según la fórmula de Tatta-Berge, el tamaño del emparejamiento es /2. Es decir, la mayor coincidencia es perfecta y el teorema de Tutt se puede obtener como consecuencia de la fórmula de Tutt-Berge, y la fórmula en sí se puede considerar como una generalización del teorema de Tutt. $tu$ ${\ estilo de visualización | U |}$ $tu$ ${\ estilo de visualización | U |}$ $|V|$

Notas

↑ Un camino alterno es un camino en el que los bordes de un emparejamiento se alternan y no están incluidos en el emparejamiento ( Berge 1962 , p. 186 Teoría de las cadenas alternas)
↑ Teorema: una coincidencia de gráficos es mayor si y solo si no hay una ruta alternativa que conecte dos vértices diferentes no coincidentes. ( Berge 1962 , p. 195)

Literatura

C. Berge La Teoría de Grafos. — Methuen, 1962.Reimpresión de Publicaciones de Dover, 2001.
C. Bergé. Teoría de grafos y su aplicación. - Moscú: Editorial de literatura extranjera, 1962.
JA Bondy, USR Murty. Teoría de grafos: un curso avanzado. - Springer-Verlag , 2007. - Pág. 428. - (Textos de Grado en Matemáticas). — ISBN 1-84628-969-6 .
JA Bondy, USR Murty. Ejercicio 5.3.4, pág. 80 // Teoría de grafos con aplicaciones . - Nueva York: Holanda Septentrional, 1976. - ISBN 0-444-19451-7 . Archivado el 13 de abril de 2010 en Wayback Machine .
Richard A. Brualdi. Clases de matrices combinatorias. - Cambridge: Cambridge University Press , 2006. - V. 108. - P. 360. - (Enciclopedia de las Matemáticas y sus Aplicaciones). — ISBN 0-521-86565-4 .
László Lovász , MD Plummer. Teoría del emparejamiento. - Ámsterdam: Holanda Septentrional, 1986. - S. 90-91. - ISBN 0-444-87916-1 .
Alejandro Schrijver . Optimización combinatoria: poliedros y eficiencia. - Springer-Verlag , 2003. - Pág. 413. - ISBN 3-540-44389-4 .

Enlaces

C. Berge Sur le couplage maximum d'un graphe //Comptes rendus hebdomadaires des séances de l'Académie des sciences. - 1958. -T. 247. -S. 258-259.
WT Tutte . La factorización de gráficos lineales // The Journal of the London Mathematical Society, Ser. 1. - 1947. - T. 22 . - S. 107-111 . -doi :/ jlms/s1-22.2.107 .