Lema de l'encaixada de mans: diferència entre les revisions

De la Viquipèdia, l'enciclopèdia lliure
Contingut suprimit Contingut afegit
Pàgina nova, amb el contingut: «File:6n-graf.svg|thumb|250px|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...».
 
Línia 9: Línia 9:


==Bibliografia==
==Bibliografia==
*{{citation | last1 = Cameron| first1 = Kathie | last2 = Edmonds| first2 = Jack| author2-link = Jack Edmonds
*{{Ref-publicació | cognom = Cameron| nom = Kathie | cognom2 = Edmonds| nom2 = Jack| enllaçautor2 = Jack Edmonds
| issue = 3
| exemplar = 3
| journal = [[Annales de l'Institut Fourier]]
| publicació = [[Annales de l'Institut Fourier]]
| pages = 815–827
| pàgines = 815–827
| title = Some graphic uses of an even number of odd nodes
| títol = Some graphic uses of an even number of odd nodes
| url = http://www.numdam.org/item?id=AIF_1999__49_3_815_0
| url = http://www.numdam.org/item?id=AIF_1999__49_3_815_0
| volume = 49
| volum = '''49'''
| year = 1999 | mr = 1703426 | doi=10.5802/aif.1694}}.
| any = 1999 | mr = 1703426 | doi=10.5802/aif.1694}}
*{{citation | last = Euler| first = L. | journal = Commentarii Academiae Scientiarum Imperialis Petropolitanae | pages = 128–140 | title = Solutio problematis ad geometriam situs pertinentis | url = http://math.dartmouth.edu/~euler/docs/originals/E053.pdf | volume = 8 | year = 1736}}. Reprinted and translated in {{citation | last1 = Biggs| first1 = N. L. | last2 = Lloyd| first2 = E. K. | last3 = Wilson| first3 = R. J. | publisher = Oxford University Press | title = Graph Theory 1736–1936 | year = 1976}}.
*{{Ref-llibre|cognom=Euler|nom=L|títol=Commentarii Academiae Scientiarum Imperialis Petropolitanae|pàgines=128–140|any=1736|url=https://math.dartmouth.edu/~euler/docs/originals/E053.pdf|consulta=30 abril 2015|enllaçautor=Leonhard Euler|capítol=Solutio problematis ad geometriam situs pertinentis|llengua=llatí|volum='''8'''}} Reimpressió i traducció: {{ref-llibre|cognom=Biggs|nom=Norman L.|cognom2=Lloyd|nom2=E. Keith|cognom3=Wilson|nom3=Robin J|títol=Graph Theory 1736-1936|editorial=Oxford University Press|isbn=978-0-19-853916-2}}
*{{citation | last = Papadimitriou| first = Christos H.| author-link = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
*{{cite journal | last = Papadimitriou| first = Christos H| authorlink = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
| issue = 3
| issue = 3
| journal = Journal of Computer and System Sciences
| journal = Journal of Computer and System Sciences

Revisió del 15:25, 30 abr 2015

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