Lema del apretón de manos

Cada gráfico tiene un número par 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 , 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 se dan la mano, el número de personas que estrechan un número impar de manos de otras personas es par. ^[1] El lema del apretón de manos es una consecuencia de la fórmula de la 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 del grafo. 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ó los tours eulerianos , otras aplicaciones de la fórmula de la suma de grados incluyen demostraciones de ciertas estructuras combinatorias. Por ejemplo, en las demostraciones del lema de Sperner y del problema de la escalada de montañas surgen comúnmente las propiedades geométricas de la fórmula. La clase de complejidad PPA encapsula la dificultad de encontrar un segundo vértice impar, dado un vértice de ese tipo en un grafo grande definido implícitamente .

Definiciones y declaraciones

Un grafo no dirigido consiste en un sistema de vértices y aristas que conectan pares de vértices no ordenados. En cualquier grafo, el grado de un vértice se define como el número de aristas que tiene como punto final. Para los grafos a los que se les permite contener bucles que conectan un vértice consigo mismo, un bucle debe contarse como contribuyente con dos unidades al grado de su punto final para los propósitos del lema del apretón de manos. ^[2] Entonces, el lema del apretón de manos establece que, en cada grafo 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 grafo a veces se denominan nodos impares (o vértices impares ); ^[4] en esta terminología, el lema del apretón de manos puede reformularse como la afirmación de que cada grafo tiene un número par de nodos impares. ^{[4] [5]} ${\displaystyle \deg(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \deg(v)}$

La fórmula de suma de grados establece que donde es el conjunto de nodos (o vértices) en el grafo y es el conjunto de aristas en el grafo. Es decir, la suma de los grados de los vértices es igual al doble del número de aristas. ^[6] En grafos dirigidos , otra forma de la fórmula de suma de grados establece que la suma de los grados de entrada de todos los vértices y la suma de los grados de salida son iguales al número de aristas. Aquí, el grado de entrada es el número de aristas entrantes y el grado de salida es el número de aristas salientes. ^[7] Una versión de la fórmula de suma de grados también se aplica a familias finitas de conjuntos o, equivalentemente, multigrafos : la suma de los grados de los elementos (donde el grado es igual al número de conjuntos que lo contienen) siempre es igual a la suma de las cardinalidades de los conjuntos. ^[8] $${\displaystyle \sum _{v\in V}\deg v=2|E|,}$$ ${\displaystyle V}$ ${\displaystyle E}$

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

Aplicaciones

Caminos 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 , pidiendo 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 de un grafo conexo que represente la ciudad y sus puentes: un paseo a través del grafo que recorra cada arista una vez, ya sea terminando en un vértice diferente del que comienza en el caso de un camino de Euler o regresando a su punto de partida en el caso de un recorrido de Euler. Euler enunció los resultados fundamentales para este problema en términos del número de vértices impares en el grafo, que el lema del apretón de manos restringe a 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 grafo que representa el problema tiene cuatro vértices impares y no tiene ni un camino de Euler ni un recorrido de Euler. ^[3] Por lo tanto, era imposible recorrer los siete puentes de Königsberg sin repetir uno.

En el algoritmo de Christofides-Serdyukov para aproximar el problema del viajante de comercio , las implicaciones geométricas de la fórmula de suma de grados juegan un papel vital, permitiendo que el algoritmo conecte 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 grafo 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 grafos en los que todos los vértices tienen grado impar. Thomason define un grafo de intercambio , cuyos vértices están en correspondencia biunívoca con los caminos hamiltonianos en que comienzan en y continúan a través de la arista . Dos de estos caminos y se definen como conectados por una arista en si uno puede obtener añadiendo una nueva arista al final de y quitando otra arista del medio de . Esta operación es reversible, formando una relación simétrica , por lo que es un grafo no dirigido. Si el camino termina en el vértice , entonces el vértice correspondiente a en tiene grado igual al número de formas en que puede extenderse por una arista 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 . Como tiene un número par de vértices impares, debe tener un número par de ciclos hamiltonianos a través de . ^[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 demostraciones de varios otros resultados en matemáticas. Entre ellos se incluyen los siguientes:

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 borde con borde, y los vértices se etiquetan con tres colores de modo que solo se usan 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 grafo de intercambio cuyos vértices son los triángulos (tanto pequeños como grandes) y cuyos bordes conectan pares de triángulos que comparten dos vértices de algunos dos colores particulares. El triángulo grande necesariamente tiene grado impar en este grafo de intercambio, al igual que un triángulo pequeño con los tres colores, pero no los otros triángulos pequeños. Por 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 montañismo

• El problema de la escalada de montaña establece que, para funciones con un comportamiento suficientemente bueno 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 encuentren en algún lugar en el medio mientras 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, parametrizando la posición de los dos puntos en movimiento mediante las coordenadas de un único punto en el cuadrado unitario , y mostrando que las posiciones disponibles para los dos puntos forman un grafo finito, incrustado en este cuadrado, con solo la posición inicial y su inversión como vértices impares. Por el lema del apretón de manos, estas dos posiciones pertenecen al mismo componente conectado del grafo, y un camino de una a la otra pasa necesariamente por el punto de encuentro deseado. ^[14]
• La conjetura de reconstrucción se refiere al problema de determinar de forma única la estructura de un grafo a partir del multiconjunto de subgrafos formados al eliminar un único vértice de él. Dada esta información, la fórmula de suma de grados se puede utilizar para recuperar el número de aristas en el grafo dado y los grados de cada vértice. A partir de esto, es posible determinar si el grafo dado es un grafo regular y, de ser así, determinarlo de forma única a partir de cualquier subgrafo al que se le haya eliminado un vértice agregando un nuevo vecino para todos los vértices del subgrafo de grado demasiado bajo. Por lo tanto, todos los grafos regulares se pueden reconstruir. ^[15]
• El juego de Hex se juega entre dos jugadores, que colocan piezas de su color en un mosaico de hexágonos de un tablero en forma de paralelogramo hasta que un jugador tenga un camino conectado de piezas adyacentes de un lado del tablero al otro. Nunca puede terminar en empate: cuando el tablero se haya llenado completamente de piezas, uno de los jugadores habrá formado un camino ganador. Una prueba de esto forma un grafo a partir de un tablero de juego lleno, con vértices en las esquinas de los hexágonos y con aristas en los lados de los hexágonos que separan los colores de los dos jugadores. Este grafo tiene cuatro vértices impares en las esquinas del tablero y vértices pares en el resto, por lo que debe contener un camino que conecte dos esquinas, que necesariamente tiene un camino ganador para un jugador en uno de sus lados. ^[16]

Prueba

La prueba de Euler de la fórmula de suma de grados utiliza la técnica del doble conteo : cuenta el número de pares incidentes donde es 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 incidentes a él. Por lo tanto, el número de pares incidentes es la suma de los grados. Sin embargo, cada arista en el grafo pertenece exactamente a dos pares incidentes, uno para cada uno de sus puntos finales; por lo tanto, el número de pares incidentes es . Dado que estas dos fórmulas cuentan el mismo conjunto de objetos, deben tener valores iguales. La misma prueba puede interpretarse como la suma de las entradas de la matriz de incidencia del grafo de dos maneras, por filas para obtener la suma de grados y por columnas para obtener el doble del número de aristas. ^[5] ${\displaystyle (v,e)}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \deg(v)}$ ${\displaystyle \deg(v)}$ ${\displaystyle v}$ ${\displaystyle 2|E|}$

En el caso de los grafos, el lema del apretón de manos se deduce como corolario de la fórmula de la 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 en 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 la 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|}$

Como alternativa, es posible utilizar la inducción matemática para demostrar la fórmula de suma de grados, ^[2] o demostrar directamente que el número de vértices de grado impar es par, eliminando un borde a la vez de un gráfico dado y utilizando 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 grado impar. ^[17]

En clases especiales de gráficos

Gráficas regulares

La fórmula de suma de grados implica que todo grafo regular con vértices tiene aristas. ^[18] Como el número de aristas debe ser un 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 birregulares

Un grafo bipartito tiene sus vértices divididos en dos subconjuntos, y cada arista tiene un punto final en cada subconjunto. Del mismo argumento de doble conteo se deduce que, en cada subconjunto, la suma de los grados es igual al número de aristas del grafo. En particular, ambos subconjuntos tienen sumas de grados iguales. ^[21] Para grafos biregulares , con una partición de los vértices en subconjuntos y con cada vértice en un subconjunto que tiene grado , debe ser el caso de que ; ambos sean 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}}$

Grafos infinitos

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

El lema del handshaking no se aplica en su forma habitual a los grafos infinitos, incluso cuando tienen solo un número finito de vértices de grado impar. Por ejemplo, un grafo de camino infinito con un punto final tiene solo un único vértice de grado impar en lugar de tener un número par de tales vértices. Sin embargo, es posible formular una versión del lema del handshaking usando el concepto de un extremo , una clase de equivalencia de caminos semi-infinitos ("rayos") considerando dos rayos como equivalentes cuando existe un tercer rayo que usa infinitos vértices de cada uno de ellos. El grado de un extremo es el número máximo de rayos disjuntos en sus aristas 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 impar o par, independientemente de si tiene grado infinito, en grafos para los cuales todos los vértices tienen grado finito. Entonces, en tales grafos, el número de vértices impares y extremos impares, sumados, es par o infinito. ^[23]

Subgrafos

Por un teorema de Gallai los vértices de cualquier grafo pueden ser particionados como donde en los dos subgrafos inducidos resultantes , tiene todos los grados pares y tiene todos los grados impares. Aquí, debe ser par por el lema de apretón de manos. También es posible encontrar subgrafos inducidos de grado par y de grado impar con muchos vértices. Un subgrafo inducido de grado par se puede encontrar con al menos la mitad de los vértices, y un subgrafo inducido de grado impar (en un grafo sin vértices aislados ) se puede encontrar con . ^{[24] [25]} ${\displaystyle V=V_{e}\cup V_{o}}$ ${\displaystyle G[V_{e}]}$ ${\displaystyle G[V_{o}]}$ ${\displaystyle |V_{o}|}$ ${\displaystyle |V_{o}|/|V|>1/10000}$

Complejidad computacional

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

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

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ág. 703, ISBN 9781284070408
2. Gunderson, David S. (2014), Manual de inducción matemática: teoría y aplicaciones, CRC Press, pág. 240, ISBN 9781420093650
3. Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128-140. Reimpreso y traducido en Biggs, NL ; Lloyd, EK; Wilson, RJ (1976), Graph Theory 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: Grado", 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ág. 26, ISBN 9780132278287
7. Loehr, Nicholas (2011), "3.31. Teorema: Fórmula de suma de grados para dígrafos", Combinatoria biyectiva , CRC Press, pág. 106, ISBN 9781439848869
8. Jukna, Stasys (2011), "Proposición 1.7", Combinatoria extrema , Textos en 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 aplicada y tecnología, Springer, pág. 16, ISBN 9788132207504
10. Christofides, Nicos (1976), Análisis del peor caso de una nueva heurística para el problema del viajante (PDF) , Informe 388, Graduate School of Industrial Administration, CMU, archivado (PDF) desde el original el 21 de julio de 2019El 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 con aristas coloreables de forma única", Advances in Graph Theory (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, ISBN 978-0-7204-0843-0, Sr.  0499124
13. Aigner, Martin ; Ziegler, Günter M. (2018), "Sección 28.6: Lema de Sperner", Pruebas del LIBRO (6.ª ed.), Berlín: Springer, pp. 203–205, doi :10.1007/978-3-662-57265-8, ISBN 978-3-662-57264-1, Sr.  3823190
14. Goodman, Jacob E. ; Pach, János ; Yap, 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, Josef; Scapellato, Raffaele (2016), Temas de automorfismos y reconstrucción de grafos, London Mathematical Society Lecture Note Series, vol. 432 (2.ª ed.), Cambridge University Press, págs. 105-106, doi :10.1017/CBO9781316669846, ISBN 978-1-316-61044-2, Sr.  3496604
16. Gale, David (1979), "El juego de Hex y el teorema de 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, pp. 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 los gráficos, Corolario 1", A Beginner's Guide to Discrete Mathematics (2.ª ed.), Springer, pág. 219, ISBN 9780817682866
20. Clark, John; Holton, Derek Allan (1995), "Problema 1.4.6", Una primera mirada a la teoría de grafos , Allied Publishers, pág. 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, Sr.  2978043
23. Bruhn, Henning; Stein, Maya (2007), "Sobre grados finales y ciclos infinitos en grafos localmente finitos", Combinatorica , 27 (3): 269–291, doi :10.1007/s00493-007-2149-0, MR  2345811, S2CID  8367713; véase la Proposición 15, pág. 284
24. Ferber, Asaf; Krivelevich, Michael (2022), "Cada gráfico contiene un subgráfico inducido de tamaño lineal con todos los grados impares", Advances in Mathematics , 406 108534, arXiv : 2009.05495 , doi : 10.1016/j.aim.2022.108534, MR  4448268
25. Honner, Patrick (24 de marzo de 2022), "Lo que nos dice un juego de matemáticas sobre la teoría de grafos", Quanta , consultado el 27 de marzo de 2022
26. Papadimitriou, Christos H. (1994), "Sobre la complejidad del argumento de paridad y otras pruebas ineficientes de existencia", Journal of Computer and System Sciences , 48 ​​(3): 498–532, doi : 10.1016/S0022-0000(05)80063-7 , MR  1279412
27. Chen, Xi; Deng, Xiaotie (2006), "Resolver la complejidad del equilibrio de Nash entre dos jugadores", Proc. 47th Symp. Foundations of Computer Science , págs. 261-271, doi :10.1109/FOCS.2006.69, ISBN 0-7695-2720-5, S2CID  14102058, Código de barras  TR05-140
28. Grigni, Michelangelo (2001), "Un lema de Sperner completo para PPA", Information Processing Letters , 77 (5–6): 255–259, doi :10.1016/S0020-0190(00)00152-6, MR  1818525
29. Filos-Ratsikas, Aris; Goldberg, Paul W. (2018), "La reducción a la mitad del consenso es PPA-completa", 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-29 de junio de 2018 , págs. 51–64, arXiv : 1711.04503 , doi : 10.1145/3188745.3188880, ISBN 978-1-4503-5559-9, S2CID8111195 ​