Lema de l'encaixada de mans

De Viquipèdia
Salta a: navegació, cerca
En aquest graf, un nombre parell de vèrtexs (els quatre enumerats amb 2, 4, 5 i 6) tenen graus senars. La suma dels graus dels vèrtexs és 2 + 3 + 2 + 3 + 3 + 1 = 14, el doble del nombre d'arestes.

En teoria de grafs, el lema de l'encaixada de mans afirma que cada graf no dirigit té un nombre parell de vèrtexs de grau senar (el grau d'un vèrtex és el nombre d'arestes que el toquen). El nom prové d'una versió més col·loquial del lema: si algunes de les persones d'un encontre s'encaixen la mà, un nombre parell de persones l'haurà encaixat amb un nombre senar d'altres.

El lema de l'encaixada de mans és una conseqüència de la fórmula de la suma de graus,

per un graf amb un conjunt de vèrtexs V i un conjunt d'arestes E. Ambdós resultats els demostrà Leonhard Euler en el cèlebre problema dels set ponts de Königsberg, que inicià l'estudi de la teoria de grafs.

Els vèrtexs de grau senar d'un graf sovint s'anomenen nodes senars o vèrtexs senars; amb aquesta terminologia, el lema de l'encaixada de mans es pot formular com que cada graf té un nombre parell de vèrtexs senars.

Bibliografia[modifica]