Lema del apretón de manos

Todo gráfico tiene el mismo número de vértices impares.

En este gráfico, un número par de vértices (los cuatro vértices numerados 2, 4, 5 y 6) tienen grados impares. La suma de los grados de los seis vértices es 2 + 3 + 2 + 3 + 3 + 1 = 14 , el doble del número de aristas.

En teoría de grafos , una rama de las matemáticas, el lema del apretón de manos es la afirmación de que, en todo grafo finito no dirigido , el número de vértices que tocan un número impar de aristas es par. Por ejemplo, si hay un grupo de personas que dan la mano, el número de personas que dan la mano a un número impar de otras personas es par. ^[1] El lema del apretón de manos es una consecuencia de la fórmula de suma de grados , también llamada a veces lema del apretón de manos, ^[2] según la cual la suma de los grados (el número de veces que se toca cada vértice) es igual al doble del número de aristas en la gráfica. Ambos resultados fueron demostrados por Leonhard Euler  (1736) en su famoso artículo sobre los Siete Puentes de Königsberg que inició el estudio de la teoría de grafos. ^[3]

Más allá del problema de los siete puentes de Königsberg, que posteriormente formalizó Eulerian Tours , otras aplicaciones de la fórmula de suma de grados incluyen pruebas de ciertas estructuras combinatorias. Por ejemplo, en las pruebas del lema de Sperner y en el problema del montañismo suelen surgir las propiedades geométricas de la fórmula. La clase de complejidad PPA resume la dificultad de encontrar un segundo vértice impar, dado uno de esos vértices en un gráfico grande definido implícitamente .

Definiciones y declaración

Un gráfico no dirigido consta de un sistema de vértices y aristas que conectan pares desordenados de vértices. En cualquier gráfico, el grado de un vértice se define como el número de aristas que tiene como punto final. Para los gráficos que pueden contener bucles que conectan un vértice consigo mismo, se debe contar que un bucle contribuye con dos unidades al grado de su punto final a los efectos del lema del protocolo de enlace. ^[2] Entonces, el lema del apretón de manos establece que, en todo gráfico finito, debe haber un número par de vértices para los cuales es un número impar. ^[1] Los vértices de grado impar en un gráfico a veces se denominan nodos impares (o vértices impares ); ^[4] en esta terminología, el lema del protocolo de enlace se puede reformular como la afirmación de que cada gráfico tiene un número par de nodos impares. ^{[4] [5]} ${\displaystyle \deg(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \deg(v)}$

La fórmula de la suma de grados establece que

$${\displaystyle \sum _{v\in V}\deg v=2|E|,}$$

^[6]gráficos dirigidos^[7]familias finitas de conjuntosmultigrafoscardinalidades.^[8] ${\displaystyle V}$ ${\displaystyle E}$

Ambos resultados también se aplican a cualquier subgrafo del gráfico dado y en particular a sus componentes conectados . Una consecuencia es que, para cualquier vértice impar, debe existir un camino que lo conecte con otro vértice impar. ^[9]

Aplicaciones

Rutas y recorridos de Euler

Leonhard Euler demostró por primera vez el lema del apretón de manos en su trabajo sobre los Siete Puentes de Königsberg , solicitando un recorrido a pie por la ciudad de Königsberg (ahora Kaliningrado ) cruzando cada uno de sus siete puentes una vez. Esto se puede traducir en términos de teoría de grafos como pedir un camino de Euler o un recorrido de Euler por un grafo conectado que represente la ciudad y sus puentes: un recorrido a través del grafo que atraviesa cada borde una vez y termina en un vértice diferente al que comienza. en el caso de un camino de Euler o regresar a su punto de partida en el caso de un recorrido de Euler. Euler expuso los resultados fundamentales de este problema en términos del número de vértices impares en el gráfico, que el lema del apretón de manos restringe a ser un número par. Si este número es cero, existe un recorrido de Euler y si es dos, existe un camino de Euler. De lo contrario, el problema no se puede resolver. En el caso de los Siete Puentes de Königsberg, el gráfico que representa el problema tiene cuatro vértices impares y no tiene ni camino de Euler ni recorrido de Euler. ^[3] Por lo tanto, era imposible recorrer los siete puentes de Königsberg sin repetir un puente.

En el algoritmo de Christofides-Serdyukov para aproximar el problema del vendedor ambulante , las implicaciones geométricas de la fórmula de suma de grados desempeñan un papel vital, permitiendo al algoritmo conectar vértices en pares para construir un gráfico en el que un recorrido de Euler forma un recorrido TSP aproximado. . ^[10]

enumeración combinatoria

Se puede demostrar que varias estructuras combinatorias son pares en número relacionándolas con los vértices impares en un "gráfico de intercambio" apropiado. ^[11]

Por ejemplo, como demostró CAB Smith , en cualquier gráfico cúbico debe haber un número par de ciclos hamiltonianos a través de cualquier arista fija ; estos son ciclos que pasan por cada vértice exactamente una vez. Thomason (1978) utilizó una prueba basada en el lema del apretón de manos para extender este resultado a gráficos en los que todos los vértices tienen grados impares. Thomason define un gráfico de intercambio , cuyos vértices están en correspondencia uno a uno con las trayectorias hamiltonianas al comenzar en el borde y continuar a través del mismo . Dos de estos caminos se definen como conectados por un borde en si se puede obtener agregando un nuevo borde al final de y eliminando otro borde en el medio de . Esta operación es reversible, formando una relación simétrica , al igual que un gráfico no dirigido. Si el camino termina en un vértice , entonces el vértice correspondiente a in tiene un grado igual al número de caminos que puede extenderse por un borde que no se conecta de nuevo a ; es decir, el grado de este vértice en es (un número par) si no forma parte de un ciclo hamiltoniano a través de , o (un número impar) si es parte de un ciclo hamiltoniano a través de . Dado que tiene un número par de vértices impares, debe tener un número par de ciclos hamiltonianos . ^[12] ${\displaystyle G}$ ${\displaystyle uv}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle uv}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle H}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{1}}$ ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle w}$ ${\displaystyle p}$ ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle u}$ ${\displaystyle H}$ ${\displaystyle \deg(w)-1}$ ${\displaystyle p}$ ${\displaystyle uv}$ ${\displaystyle \deg(w)-2}$ ${\displaystyle p}$ ${\displaystyle uv}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle uv}$

Otras aplicaciones

El lema del apretón de manos (o fórmula de suma de grados) también se utiliza en pruebas de varios otros resultados en matemáticas. Estos incluyen lo siguiente:

Una coloración de Sperner de un triángulo triangulado, sombreada para resaltar los tres triángulos pequeños que tienen los tres colores de vértice.

• El lema de Sperner establece que, si un triángulo grande se subdivide en triángulos más pequeños que se encuentran de borde a borde, y los vértices están etiquetados con tres colores de modo que sólo se usen dos de los colores a lo largo de cada borde del triángulo grande, entonces al menos uno de los triángulos más pequeños tiene vértices de los tres colores; tiene aplicaciones en teoremas de punto fijo , algoritmos de búsqueda de raíces y división justa . Una prueba de este lema forma un gráfico de intercambio cuyos vértices son los triángulos (tanto pequeños como grandes) y cuyas aristas conectan pares de triángulos que comparten dos vértices de algunos dos colores en particular. El triángulo grande necesariamente tiene un grado impar en este gráfico de intercambio, al igual que un triángulo pequeño con los tres colores, pero no los otros triángulos pequeños. Según el lema del apretón de manos, debe haber un número impar de triángulos pequeños con los tres colores y, por lo tanto, debe existir al menos uno de esos triángulos. ^[13]

El problema del alpinismo

• El problema del montañismo establece que, para funciones que se comportan suficientemente bien en un intervalo unitario , con valores iguales en los extremos del intervalo, es posible coordinar el movimiento de dos puntos, comenzando desde extremos opuestos del intervalo, de modo que se encuentran en algún punto intermedio y permanecen en puntos de igual valor durante todo el movimiento. Una prueba de esto implica aproximar la función mediante una función lineal por partes con los mismos puntos extremos, parametrizar la posición de los dos puntos en movimiento mediante las coordenadas de un solo punto en el cuadrado unitario y demostrar que las posiciones disponibles para los dos puntos forman un gráfico finito, incrustado en este cuadrado, con solo la posición inicial y su inversión como vértices impares. Según el lema del apretón de manos, estas dos posiciones pertenecen al mismo componente conectado del gráfico, y un camino de una a la otra necesariamente pasa por el punto de encuentro deseado. ^[14]
• La conjetura de la reconstrucción se refiere al problema de determinar de forma única la estructura de un gráfico a partir del conjunto múltiple de subgrafos formados eliminando un solo vértice del mismo. Dada esta información, la fórmula de suma de grados se puede utilizar para recuperar el número de aristas en el gráfico dado y los grados de cada vértice. A partir de esto, es posible determinar si el gráfico dado es un gráfico regular y, de ser así, determinarlo únicamente a partir de cualquier subgrafo con vértices eliminados agregando un nuevo vecino para todos los vértices del subgrafo de grado demasiado bajo. Por tanto, se pueden reconstruir todas las gráficas regulares. ^[15]
• El juego de Hex lo juegan dos jugadores, que colocan piezas de su color en un mosaico de un tablero en forma de paralelogramo por hexágonos hasta que un jugador tiene un camino conectado de piezas adyacentes de un lado del tablero al otro. Nunca puede terminar en empate: cuando el tablero esté completamente lleno de piezas, uno de los jugadores habrá trazado un camino ganador. Una prueba de esto es un gráfico de un tablero de juego lleno, con vértices en las esquinas de los hexágonos y con bordes en los lados de los hexágonos que separan los colores de los dos jugadores. Este gráfico tiene cuatro vértices impares en las esquinas del tablero, y vértices pares en otras partes, por lo que debe contener un camino que conecte dos esquinas, que necesariamente tenga un camino ganador para un jugador en uno de sus lados. ^[dieciséis]

Prueba

La prueba de Euler de la fórmula de la suma de grados utiliza la técnica del doble conteo : cuenta el número de pares incidentes donde hay una arista y el vértice es uno de sus puntos finales, de dos maneras diferentes. El vértice pertenece a pares, donde (el grado de ) es el número de aristas que le inciden. Por tanto, el número de pares de incidentes es la suma de los grados. Sin embargo, cada arista del gráfico pertenece exactamente a dos pares de incidentes, uno para cada uno de sus puntos finales; por lo tanto, el número de pares de incidentes es . Dado que estas dos fórmulas cuentan el mismo conjunto de objetos, deben tener valores iguales. La misma prueba se puede interpretar como la suma de las entradas de la matriz de incidencia del gráfico de dos maneras, por filas para obtener la suma de grados y por columnas para obtener el doble de aristas. ^[5] ${\displaystyle (v,e)}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \deg(v)}$ ${\displaystyle \deg(v)}$ ${\displaystyle v}$ ${\displaystyle 2|E|}$

Para gráficos, el lema del protocolo de enlace sigue como corolario de la fórmula de suma de grados. ^[8] En una suma de números enteros, la paridad de la suma no se ve afectada por los términos pares de la suma; la suma total es par cuando hay un número par de términos impares e impar cuando hay un número impar de términos impares. Dado que un lado de la fórmula de suma de grados es el número par , la suma del otro lado debe tener un número par de términos impares; es decir, debe haber un número par de vértices de grado impar. ^[5] ${\displaystyle 2|E|}$

Alternativamente, es posible usar la inducción matemática para probar la fórmula de la suma de grados, ^{[2] o probar directamente que el número de vértices de grados impares es par, eliminando un borde a la vez de un gráfico dado y usando un} análisis de caso . sobre los grados de sus puntos finales para determinar el efecto de esta eliminación sobre la paridad del número de vértices de grados impares. ^[17]

En clases especiales de gráficos.

Gráficos regulares

La fórmula de suma de grados implica que todo gráfico regular con vértices tiene aristas. ^[18] Debido a que el número de aristas debe ser un número entero, se deduce que cuando es impar el número de vértices debe ser par. ^[19] Además, para valores impares de , el número de aristas debe ser divisible por . ^[20] ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle nr/2}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r}$

Grafos bipartitos y biregulares

Un gráfico bipartito tiene sus vértices divididos en dos subconjuntos, y cada arista tiene un punto final en cada subconjunto. Del mismo argumento del doble conteo se deduce que, en cada subconjunto, la suma de grados es igual al número de aristas del gráfico. En particular, ambos subconjuntos tienen sumas de grados iguales. ^[21] Para gráficos biregulares , con una partición de los vértices en subconjuntos y con cada vértice en un subconjunto teniendo grado , debe darse el caso de que ; ambos son iguales al número de aristas. ^[22] ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{i}}$ ${\displaystyle r_{i}}$ ${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$

graficos infinitos

Un gráfico infinito con un solo vértice impar.

El lema del apretón de manos no se aplica en su forma habitual a gráficos infinitos, incluso cuando solo tienen un número finito de vértices de grado impar. Por ejemplo, un gráfico de ruta infinita con un punto final tiene solo un vértice de grado impar en lugar de tener un número par de dichos vértices. Sin embargo, es posible formular una versión del lema del protocolo de enlace utilizando el concepto de extremo , una clase de equivalencia de caminos semiinfinitos ("rayos") que considera dos rayos como equivalentes cuando existe un tercer rayo que utiliza infinitos vértices desde cada uno de ellos. El grado de un extremo es el número máximo de rayos de aristas disjuntas que contiene, y un extremo es impar si su grado es finito e impar. De manera más general, es posible definir un extremo como par o impar, independientemente de si tiene grado infinito, en gráficos en los que todos los vértices tienen grado finito. Entonces, en tales gráficos, el número de vértices impares y extremos impares, sumados, es par o infinito. ^[23]

Subgrafos

Según un teorema de Gallai, los vértices de cualquier gráfico se pueden descomponer en donde todos los grados son pares y todos los grados son pares e impares según el lema del apretón de manos. En 1994, Yair Caro ^[24] lo demostró y en 2021, una preimpresión de Ferber Asaf y Michael Krivelevich lo demostró . ^{[25] [26]} ${\displaystyle V=V_{e}\cup V_{o}}$ ${\displaystyle G(V_{e})}$ ${\displaystyle G(V_{o})}$ ${\displaystyle |V_{o}|}$ ${\displaystyle |V_{o}|/|V|>1/{\sqrt {n}}}$ ${\displaystyle |V_{o}|/|V|>1/10000}$

Complejidad computacional

En relación con el método del gráfico de intercambio para demostrar la existencia de estructuras combinatorias, es interesante preguntarse con qué eficiencia se pueden encontrar estas estructuras. Por ejemplo, supongamos que a uno se le da como entrada un ciclo hamiltoniano en un gráfico cúbico; Del teorema de Smith se deduce que existe un segundo ciclo. ¿Qué tan rápido se puede encontrar este segundo ciclo? Papadimitriou (1994) investigó la complejidad computacional de preguntas como esta, o más generalmente, de encontrar un segundo vértice de grado impar cuando a uno se le da un único vértice impar en un gráfico grande definido implícitamente . Definió la clase de complejidad PPA para encapsular problemas como este; ^[27] una clase estrechamente relacionada definida en gráficos dirigidos, PPAD , ha atraído una atención significativa en la teoría algorítmica de juegos porque calcular un equilibrio de Nash es computacionalmente equivalente a los problemas más difíciles de esta clase. ^[28]

Los problemas computacionales que han demostrado ser completos para la clase de complejidad PPA incluyen tareas computacionales relacionadas con el lema de Sperner ^[29] y con la subdivisión justa de recursos según el teorema de Hobby-Rice . ^[30]

Notas

1. Hein, James L. (2015), "Ejemplo 3: El problema del apretón de manos", Estructuras discretas, lógica y computabilidad , Jones & Bartlett Publishers, p. 703, ISBN 9781284070408
2. Gunderson, David S. (2014), Manual de inducción matemática: teoría y aplicaciones, CRC Press, p. 240, ISBN 9781420093650
3. Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128-140. Reimpreso y traducido en Biggs, NL ; Lloyd, EK; Wilson, RJ (1976), Teoría de grafos 1736-1936 , Oxford University Press
4. Higgins, Peter M. (1998), Matemáticas para curiosos, Oxford University Press, pág. 201, ISBN 9780192880727
5. Biggs, Norman L. (2002), "15.3: Licenciatura", Matemáticas discretas , Oxford University Press, págs. 181-182, ISBN 9780198507178
6. West, Douglas B. (1996), "1.3.3. Teorema. (Fórmula de suma de grados)", Introducción a la teoría de grafos (2ª ed.), Prentice Hall, p. 26, ISBN 9780132278287
7. Loehr, Nicholas (2011), "3.31. Teorema: fórmula de suma de grados para dígrafos", Combinatoria biyectiva , CRC Press, p. 106, ISBN 9781439848869
8. Jukna, Stasys (2011), "Proposición 1.7", Combinatoria extrema , Textos de informática teórica. Una serie EATCS, Springer, pág. 9, doi :10.1007/978-3-642-17364-6, ISBN 978-3-642-17363-9
9. Ray, Santanu Saha (2012), "Teorema 2.2", Teoría de grafos con algoritmos y sus aplicaciones en ciencia y tecnología aplicadas, Springer, p. 16, ISBN 9788132207504
10. Christofides, Nicos (1976), Análisis del peor de los casos de una nueva heurística para el problema del viajante (PDF) , Informe 388, Escuela de Graduados en Administración Industrial, CMU, archivado (PDF) del original el 21 de julio de 2019. El lema del apretón de manos se cita en la parte superior de la página 2.
11. Cameron, Kathie; Edmonds, Jack (1999), "Algunos usos gráficos de un número par de nodos impares", Annales de l'Institut Fourier , 49 (3): 815–827, doi : 10.5802/aif.1694 , MR  1703426
12. Thomason, AG (1978), "Ciclos hamiltonianos y gráficos coloreables de bordes únicos", Avances en teoría de grafos (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , Annals of Discrete Mathematics, vol. 3, págs. 259–268, doi :10.1016/S0167-5060(08)70511-9, SEÑOR  0499124
13. Aigner, Martín ; Ziegler, Günter M. (2018), "Sección 28.6: Lema de Sperner", Pruebas del LIBRO (6.a ed.), Berlín: Springer, págs. 203–205, doi :10.1007/978-3-662-57265-8 , ISBN 978-3-662-57264-1, señor  3823190
14. Goodman, Jacob E .; Pach, János ; Sí, Chee-K. (1989), "Escalada de montañas, movimiento de escaleras y el ancho de anillo de un polígono" (PDF) , The American Mathematical Monthly , 96 (6): 494–510, doi :10.2307/2323971, JSTOR  2323971, MR  0999412
15. Lauri, José; Scapellato, Raffaele (2016), Temas sobre automorfismos y reconstrucción de gráficos, Serie de notas de conferencias de la London Mathematical Society, vol. 432 (2ª ed.), Cambridge University Press, págs. 105-106, doi :10.1017/CBO9781316669846, ISBN 978-1-316-61044-2, señor  3496604
16. Gale, David (1979), "El juego de Hex y el teorema del punto fijo de Brouwer", The American Mathematical Monthly , 86 (10): 818–827, doi :10.1080/00029890.1979.11994922, JSTOR  2320146, MR  0551501
17. Neto, Antonio Caminha Muniz (2018), Una excursión a través de las matemáticas elementales, Volumen III: Matemáticas discretas y álgebra polinomial , Libros de problemas de matemáticas, Springer, págs.132, 562, ISBN 9783319779775
18. Aldous, Joan M.; Wilson, Robin J. (2000), "Teorema 2.2", Gráficos y aplicaciones: un enfoque introductorio , Serie de Matemáticas de pregrado, The Open University, Springer-Verlag, pág. 44, ISBN 978-1-85233-259-4
19. Wallis, WD (2011), "Sección 7.1, Introducción a las gráficas, Corolario 1", Guía para principiantes de matemáticas discretas (2ª ed.), Springer, p. 219, ISBN 9780817682866
20. Clark, Juan; Holton, Derek Allan (1995), "Problema 1.4.6", Un primer vistazo a la teoría de grafos , Allied Publishers, p. 16, ISBN 9788170234630
21. Lovász, László (2014), Problemas y ejercicios combinatorios (2ª ed.), Elsevier, p. 281, ISBN 9780080933092
22. Pisanski, Tomaž ; Servatius, Brigitte (2013), "2.3.4: Semiregular Bipartite Graphs", Configuraciones desde un punto de vista gráfico , Birkhäuser Advanced Texts: Basler Lehrbücher, Nueva York: Birkhäuser/Springer, p. 35, doi :10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4, señor  2978043
23. Bruhn, Henning; Stein, Maya (2007), "Sobre grados finales y ciclos infinitos en gráficos localmente finitos", Combinatorica , 27 (3): 269–291, doi :10.1007/s00493-007-2149-0, MR  2345811, S2CID  8367713; ver la Proposición 15, pág. 284
24. Caro, Yair (15 de septiembre de 1994). "Sobre subgrafos inducidos con grados impares". Matemáticas discretas . 132 (1–3): 23–28. doi : 10.1016/0012-365X(92)00563-7 .
25. Ferber, Asaf; Krivelevich, Michael (2020). "Cada gráfico contiene un subgrafo inducido de tamaño lineal con todos los grados impares". arXiv : 2009.05495 ​​[math.CO].
26. Honner, Patrick (24 de marzo de 2022). "Lo que nos dice un juego de matemáticas sobre la teoría de grafos". Revista Quanta . Consultado el 27 de marzo de 2022 .
27. Papadimitriou, Christos H. (1994), "Sobre la complejidad del argumento de la paridad y otras pruebas de existencia ineficientes", Journal of Computer and System Sciences , 48 ​​(3): 498–532, doi : 10.1016/S0022-0000( 05)80063-7 , SEÑOR  1279412
28. Chen, Xi; Deng, Xiaotie (2006), "Resolver la complejidad del equilibrio de Nash de dos jugadores", Proc. 47º Simposio. Fundamentos de la informática , págs. 261–271, doi :10.1109/FOCS.2006.69, S2CID  14102058, ECCC  TR05-140
29. Grigni, Michelangelo (2001), "Un lema de Sperner completo para PPA", Cartas de procesamiento de información , 77 (5–6): 255–259, doi :10.1016/S0020-0190(00)00152-6, MR  1818525
30. Filos-Ratsikas, Aris; Goldberg, Paul W. (2018), "La reducción a la mitad del consenso es PPA completo", en Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Actas del 50.º Simposio anual ACM SIGACT sobre teoría de la computación, STOC 2018, Los Ángeles, CA, EE. UU., 25 al 29 de junio de 2018, págs. 51 a 64, arXiv : 1711.04503 , doi : 10.1145/3188745.3188880, S2CID  8111195