Håndtrykslemma

I grafteori , en gren af matematik , er håndtryk-lemmaet udsagnet om, at hver endelig, ikke-rettet graf har et lige antal hjørner af ulige grad . Mere trivielt vil et lige antal mennesker på et møde med flere mennesker, hvoraf nogle ryster hænder, være nødt til at ryste andre menneskers hænder et ulige antal gange.

Beskrivelse

Håndtrykslemmaet er en konsekvens af summen af graders formel (undertiden kaldet håndtryk lemma ),

\ sum _ {{v \ in V}} \ deg (v) = 2 | E |

for en graf med et sæt af knudepunkter V og en kant sæt E . Dette resultat blev bevist af Leonhard Euler i sin berømte artikel fra 1736 om problemet med de syv Königsberg-broer , grundlæggende tekst til studiet af grafteori.

I en graf kaldes hjørner af ulige grad undertiden ulige knudepunkter eller ulige hjørner ; under denne terminologi kan håndtryk-lemmaet omformuleres som følger: hver endelig graf har et lige antal ulige noder.

Demonstration

Beviset for formlen for summen af grader udgør et eksempel på bevis ved dobbelt optælling : man tæller på to forskellige måder antallet af enderne af kanterne:

dette er dobbelt så mange kanter, hver kant har to ender;
det er også summen af graderne for hvert toppunkt.

Antallet af enderne af kanterne er lige efter det første punkt, vi udleder, at de ulige bidrag i summen af det andet punkt er i lige antal, deraf resultatet.

Uendelige grafer

Håndtrykslemmet gælder ikke for uendelige grafer, selv når de har et endeligt antal hjørner af ulige grad. For eksempel har en uendelig kædegraf med kun den ene ende (figur) nøjagtigt et toppunkt af ulige grad (det ene i slutningen), hvor 1 er et ulige tal.

Tilfælde af regelmæssige grafer

Formlen på summen af graderne indebærer, at enhver regelmæssig grad af graf med hjørner har kanter. En konsekvens er, at hvis graden er ulige, så kan antallet af kanter deles med . $r$ $ikke$ ${\ frac {rn} {2}}$ $r$ $r$

Bemærkninger

V for vertex, hvilket betyder "vertex" på engelsk .
E for kant, hvilket betyder "kant" på engelsk.

Referencer

(fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen " Handshaking lemma " ( se listen over forfattere ) .

(i) Joan M. Aldous og Robin J. Wilson , Grafer og Applications: en indledende Approach , Springer-Verlag ,2000, 444 s. ( ISBN 978-1-85233-259-4 , læs online ) , "sætning 2.2" , s. 44.