En la teoría de grafos , una rama de las matemáticas, el lema del apretón de manos es la afirmación de que cada grafo no dirigido finito tiene un número par de vértices con un grado impar (el número de aristas que tocan el vértice). En términos más coloquiales, en un grupo de personas algunas de las cuales se dan la mano, un número par de personas debe haber estrechado la mano a un número impar de otras personas. Los vértices de grado impar en un gráfico a veces se denominan nodos impares o vértices impares ; 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.
El lema de apretón de manos es una consecuencia de la fórmula de suma de grados (también llamado a veces lema de apretón de manos ),
para un gráfico con conjunto de vértices V y conjunto de aristas E . Ambos resultados fueron probados 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. [1]
Otras aplicaciones incluyen probar que para ciertas estructuras combinatorias, el número de estructuras es siempre uniforme y ayudar con las pruebas del lema de Sperner y el problema del montañismo . La clase de complejidad PPA encapsula la dificultad de encontrar un segundo vértice impar, dado uno de esos vértices en un gran gráfico definido implícitamente .
Prueba
La prueba de Euler de la fórmula de la suma de grados utiliza la técnica del conteo doble : cuenta el número de pares incidentes ( v , e ) donde e es un borde y el vértice v es uno de sus puntos finales, de dos maneras diferentes. El vértice v pertenece a los pares deg ( v ), donde deg ( v ) (el grado de v ) es el número de aristas incidentes a él. Por tanto, el número de pares de incidentes es la suma de los grados. Sin embargo, cada borde del gráfico pertenece exactamente a dos pares de incidentes, uno para cada uno de sus extremos; por lo tanto, el número de pares de incidentes es 2 | E |. Dado que estas dos fórmulas cuentan el mismo conjunto de objetos, deben tener valores iguales.
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 la suma de grados es el número par 2 | E |, 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 grados impares.
Alternativamente, es posible usar la inducción matemática para demostrar que el número de vértices de grados impares es par, quitando un borde a la vez de un gráfico dado y usando un análisis de caso en los grados de sus puntos finales para determinar el efecto de este eliminación de la paridad del número de vértices de grado impar.
En clases especiales de gráficos
Gráficos regulares
La fórmula de la suma de grados implica que cada r - grafo regular con n vértices tiene nr / 2 aristas. [2] En particular, si r es impar, entonces el número de aristas debe ser divisible por r , y el número de vértices debe ser par.
Gráficos infinitos
El lema de apretón de manos no se aplica a gráficos infinitos, incluso cuando solo tienen un número finito de vértices de grado impar. Por ejemplo, un gráfico de trayectoria 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.
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 teóricos de gráficos como pedir un camino de Euler o un recorrido de Euler de un gráfico conectado que represente la ciudad y sus puentes: un recorrido por el gráfico que atraviesa cada borde una vez, o termina en un vértice diferente al que comienza en el caso de un camino de Euler o volver a su punto de partida en el caso de un recorrido de Euler. Euler expresó 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 un número par. Si este número es cero, existe un recorrido de Euler, y si es dos, existe un recorrido 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 un camino de Euler ni un recorrido de Euler. [1]
En el algoritmo de Christofides-Serdyukov para aproximar el problema del vendedor ambulante , el hecho de que el número de vértices impares sea par juega un papel clave, permitiendo que el algoritmo conecte esos vértices en pares para construir un gráfico en el que un recorrido de Euler forma un recorrido aproximado de TSP. [3]
En enumeración combinatoria
Se puede demostrar que varias estructuras combinatorias son pares relacionándolas con los vértices impares en un "gráfico de intercambio" apropiado. [4]
Por ejemplo, como demostró CAB Smith , en cualquier grafo cúbico G debe haber un número par de ciclos hamiltonianos a través de cualquier borde fijo uv ; Thomason (1978) utilizó una demostración basada en el lema del apretón de manos para extender este resultado a los gráficos G en los que todos los vértices tienen un grado impar. Thomason define un gráfico de intercambio H , cuyos vértices están en correspondencia uno a uno con las trayectorias hamiltonianas que comienzan en u y continúan a través de v . Dos de estos caminos p 1 y p 2 están conectados por una arista en H si se puede obtener p 2 agregando una nueva arista al final de p 1 y quitando otra arista del medio de p 1 ; esta es una relación simétrica , por lo que H es una gráfica no dirigida. Si la trayectoria p termina en el vértice w , entonces el vértice correspondiente ap en H tiene un grado igual al número de formas en que p puede extenderse por una arista que no se conecta con u ; es decir, el grado de este vértice en H es deg ( w ) - 1 (un número par) si p no forma parte de un ciclo hamiltoniano a través de uv , o deg ( w ) - 2 (un número impar) si p es parte de un ciclo hamiltoniano a través de uv . Dado que H tiene un número par de vértices impares, G debe tener un número par de ciclos hamiltonianos a través de uv . [5]
Otras aplicaciones
El lema del apretón de manos también se utiliza en las pruebas del lema de Sperner y del caso lineal por partes del problema del montañismo .
Complejidad computacional
En relación con el método del gráfico de intercambio para probar la existencia de estructuras combinatorias, es interesante preguntarse con qué eficiencia se pueden encontrar estas estructuras. Por ejemplo, suponga que se da como entrada un ciclo hamiltoniano en un gráfico cúbico; del teorema de Smith se sigue que existe un segundo ciclo. ¿Qué tan rápido se puede encontrar este segundo ciclo? Papadimitriou (1994) investigó la complejidad computacional de preguntas como ésta, o más en general, de encontrar un segundo vértice de grado impar cuando a uno se le da un único vértice impar en un gran gráfico definido implícitamente . Definió la clase de complejidad PPA para encapsular problemas como éste; [6] 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. [7]
Notas
- ^ a b Euler, L. (1736), "Solutio problematis ad geometriam situs pertinente" (PDF) , 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
- ^ 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. 44 , ISBN 978-1-85233-259-4
- ^ Christofides, Nicos (1976), Análisis del peor caso de una nueva heurística para el problema del viajante de comercio (PDF) , Informe 388, Graduate School of Industrial Administration, CMU. El lema del apretón de manos se cita en la parte superior de la página 2.
- ^ 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
- ^ Thomason, AG (1978), "Ciclos hamiltonianos y gráficos con colores de borde único", Advances in Graph Theory (Conf. Combinatoria de Cambridge, Trinity College, Cambridge, 1977) , Annals of Discrete Mathematics, 3 , págs. 259-268, doi : 10.1016 / S0167-5060 (08) 70511-9 , MR 0499124
- ^ Papadimitriou, Christos H. (1994), "Sobre la complejidad del argumento de la 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 , Sr. 1279412
- ^ Chen, Xi; Deng, Xiaotie (2006), "Resolver la complejidad del equilibrio de Nash de dos jugadores", Proc. 47th Symp. Fundamentos de la informática , págs. 261–271, doi : 10.1109 / FOCS.2006.69 , ECCC TR05-140