Archiu:6n-graf.svgEn este grafo, un número par de vèrtiços (els quatre vèrtiços numerats com 2, 4, 5 i 6) tenen graus impars. La suma dels graus dels sis vèrtiços és 2 + 3 + 2 + 3 + 3 + 1 = 14, el doble del número d'arestes.
En teoria de grafos, el lema de la premuda de mans és l'afirmació de que, en tot grafo finito no dirigit, el número de vèrtiços que toquen un número impar d'arestes és parell. Per eixemple, si hi ha un grup de persones que es donen la mà, el número de persones que donen la mà a un número impar d'atres persones és parell.[1] El lema de la premuda de mans és una conseqüència de la fòrmula de la suma de graus, també cridada a voltes lema de la premuda de mans,[2] segons la qual la suma dels graus (el número de voltes que es toca cada vèrtiç) és igual al doble del número d'arestes del grafo. Abdós resultats varen ser demostrats per Leonhard Euler (1736) en el seu famós artícul sobre els Sèt Ponts de Königsberg, que va iniciar l'estudi de la teoria de grafos.[3]
Més allà del problema dels sèt ponts de Königsberg, que va formalisar posteriorment els cicles eulerianos, atres aplicacions de la fòrmula de la suma de graus inclouen proves de certes estructures combinatòries. Per eixemple, en les proves del lema de Sperner i del problema de l'escalada de montanyes solen sorgir les propietats geomètriques de la fòrmula. La classe de complexitatPPA engloba la dificultat de trobar un segon vèrtiç impar, donat un de tals vèrtiços en un gran grafo implícitament definit.
Un grafo no dirigit està format per un sistema de vèrtiços i arestes que conecten parells desordenats de vèrtiços. En qualsevol grafo, el grau d'un vèrtiç es definix com el número d'arestes que tenen com a punt final. Per als grafos que poden contindre bucles que conecten un vèrtiç conseguixc mateixa, un bucle deu contar-se com una contribució de dos unitats al grau del seu punt final per als propòsits del lema de la premuda de mans.[2] Llavors, el lema de la premuda de mans establix que, en cada grafo finito, deu haver un número par de vèrtiços per als que és un número impar.[1] Els vèrtiços de grau impar d'un grafo es denominen a voltes nodos impars (o vèrtiços impars);[4] en esta terminologia, el lema de la premuda de mans pot reformular-se com l'afirmació de que tot grafo té un número par de nodos impars.[4][5]
La fòrmula de la suma de graus establix que:
A on és el conjunt de nodos (o vèrtiços) del grafo i és el conjunt d'arestes del grafo. És dir, la suma dels graus dels vèrtiços és igual al doble del número d'arestes.[6] En els grafos dirigits, una atra forma de la fòrmula de la suma de graus establix que la suma dels graus d'entrada de tots els vèrtiços i la suma dels graus d'eixida són iguals al número d'arestes. Ací, el grau d'entrada és el número d'arestes entrantes i el grau d'eixida és el número d'arestes eixints.[7] Una versió de la fòrmula de la suma de graus també s'aplica a famílies finitas de conjunts o, equivalentemente, a multigrafos: la suma dels graus dels elements (a on el grau és igual al número de conjunts que ho contenen) sempre és igual a la suma de les cardinalidades dels conjunts.[8]
Abdós resultats s'apliquen també a qualsevol subgrafo del grafo donat i, en particular, als seus components conectats. Una conseqüència és que, per a qualsevol vèrtiç impar, deu existir un camí que ho conecte en un atre vèrtiç impar.[9]
Leonhard Euler va demostrar per primera volta el lema de la premuda de mans en el seu treball sobre els Sèt Ponts de Königsberg, en el que demanava un
recorregut a peu per la ciutat de Königsberg (actual Kaliningrado) creuant cada u dels seus sèt ponts una volta. En la teoria de grafos, açò pot traduir-se com una ruta o recorregut de Euler per un grafo conexo que represente la ciutat i els seus ponts: un passejada pel grafo que travesse cada aresta una volta i que termine en un vèrtiç distint del de partida, en el cas d'una ruta de Euler, o que retorne al punt de partida, en el cas d'un recorregut de Euler. Euler va enunciar els resultats fonamentals d'este problema en térmens del número de vèrtiços impars del grafo, que el lema de la premuda de mans restringix a un número par. Si este número és zero, existix un recorregut de Euler, i si és dos, existix un camí de Euler. En cas contrari, el problema no pot resoldre's. En el cas dels Sèt Ponts de Königsberg, el grafo que representa el problema té quatre vèrtiços impars i no té ni camí ni recorregut de Euler,[3] per lo que era impossible recórrer els sèt ponts de Königsberg sense repetir cap.
En l'algoritme Christofides-Serdyukov per a aproximar el problema del viajante de comerç, les implicacions geomètriques de la fòrmula de la suma de graus eixerciten un paper vital, permetent a l'algoritme conectar vèrtiços de dos en dos per a construir un grafo en el que un recorregut de Euler forme un recorregut aproximat de el TSP.[10]
Es pot demostrar que vàries estructures combinatòries són parells en número relacionant-les en els vèrtiços impars d'un «grafo d'intercanvi» apropiat.[11]
Per eixemple, com va demostrar C. A. B. Smith, en qualsevol grafo cúbic deu haver un número par de cicles hamiltonianos a través de qualsevol aresta fixa ; es tracta de cicles que passen per cada vèrtiç exactament una volta. Thomason (1978) va utilisar una prova basada en el lema de la premuda de mans per a estendre este resultat a grafos en els que tots els vèrtiços tenen grau impar. Thomason definix un grafo d'intercanvi els vèrtiços del qual estan en correspondència un a un en les trayectòries hamiltonianas en començant en i continuant per la vora . Dos d'estes vies i es definixen com conectades per una aresta en si es pot obtindre afegint una nova aresta al final de i llevant una atra aresta del centre de . Esta operació és reversible, formant una relació simètrica, per lo que és un grafo no dirigit. Si el camí termina en el vèrtiç , llavors el vèrtiç corresponent a en té grau igual al número de formes en que pot ampliar-se en una aresta que no torne a conectar-se en ; és dir, el grau d'este vèrtiç en és (un número par) si no forma part d'un cicle hamiltoniano a través de o (un número impar) si forma partix d'un cicle hamiltoniano a través de . Ya que té un número par de vèrtiços impars, deu tindre un número par de cicles hamiltonianos a través de .[12]
El lema de la premuda de mans (o fòrmula de la suma de graus) també s'utilisa en la demostració d'atres resultats matemàtics. Entre ells s'inclouen els següents:
Archiu:Sperner2d.svgColoreado de Sperner d'un triàngul triangulado, sombreado per a resaltar els tres triànguls menuts que tenen els tres colors de vèrtiç.El lema de Sperner establix que, si un triàngul gran es subdivide en triànguls més menuts que es troben vora en vora, i els vèrtiços s'etiqueten en tres colors de modo que només dos dels colors s'utilisen a lo llarc de cada vora del triàngul gran, llavors a lo manco un dels triànguls més menuts té vèrtiços dels tres colors; té aplicacions en teoremes de punt fix, algoritmes de busca de raïls, i la divisió justa. Una prova d'este lema forma un grafo d'intercanvi els vèrtiços del qual són els triànguls (grans i menuts) i les arestes dels quals conecten parells de triànguls que compartixen dos vèrtiços de dos colors determinats. El triàngul gran té necessàriament grau impar en este grafo d'intercanvi, de la mateixa manera que un triàngul chicotet en els tres colors, pero no els atres triànguls menuts. Pel lema de la premuda de mans, deu haver un número impar de triànguls menuts en els tres colors i, per tant, deu existir a lo manco un d'estos triànguls.[13]
Archiu:Mountain climbing problem.gifEl problema de l'escalada de montanyaEl problema de l'escalada de montanyes establix que, per a funcions suficientment ben comportades en un interval unitari, en valors iguals en els extrems de l'interval, és possible coordinar el moviment de dos punts, que partixen d'extrems oposts de l'interval, de modo que es troben en algun punt intermig permaneixent en punts d'igual valor durant tot el moviment. Una prova d'això consistix en aproximar la funció per una funció llineal a trossos en els mateixos punts extrems, parametrizar la posició dels dos punts en moviment per les coordenades d'un únic punt del quadrat unitari i demostrar que les posicions disponibles per als dos punts formen un grafo finito, incrustat en este quadrat, en només la posició inicial i la seua inversió com a vèrtiços impars. Pel lema de la premuda de mans, estes dos posicions pertanyen a la mateixa component conexa del grafo, i un camí d'una a una atra passa necessàriament pel punt de trobada desijada.[14]
La conjectura de reconstrucció es referix al problema de determinar de forma única l'estructura d'un grafo a partir del conjunt de subgrafos formats en eliminar un únic vèrtiç del mateix. Donada esta informació, la fòrmula de la suma de graus pot utilisar-se per a recuperar el número d'arestes del grafo donat i els graus de cada vèrtiç. A partir d'ahí, és possible determinar si el grafo és regular i, en cas afirmatiu, determinar-ho de forma única a partir de qualsevol subgrafo en vèrtiços eliminats afegint un nou veí a tots els vèrtiços del subgrafo en un grau massa baix. Per lo tant, es poden reconstruir tots els grafos regulars.[15]
El joc de l'Hexàgon ho juguen dos jugadors, que coloquen peces del seu color en un tauler en forma de paralelogramo emmanisat per hexàgons fins que un dels jugadors tinga un camí conectat de peces adjacents d'un costat a l'atre del tauler. Mai pot acabar en empat: en el moment en que el tauler s'haja omplit completament de peces, un dels jugadors haurà format un camí guanyador. Una prova d'això és que es forma un gràfic a partir d'un tauler ple, en vèrtiços en els cantons dels hexàgons i en arestes en els costats dels hexàgons que separen els colors dels dos jugadors. Este grafo té quatre vèrtiços impars en els cantons del tauler, i vèrtiços pares en el restant, per lo que deu contindre un camí que conecte dos cantons, que necessàriament té un camí guanyador per a un jugador en un dels seus costats.[16]
