Kézfogás Lemma

A gráfelméletben , a matematika egyik ágában a kézfogás lemma az a megállapítás, hogy minden véges irányítatlan gráfnak páros számú páratlan fokú csúcsa van . Triviálisabb, hogy több ember találkozásánál, akik közül néhányan kezet fognak, páros számú embernek páratlan számú alkalommal kell kezet ráznia más embereknek.

Leírás

A kézfogás lemma a fokok összegének következménye (néha kézfogás lemmának hívják ),

∑v∈Vdeg⁡(v)=2|E|{\ displaystyle \ sum _ {v \ in V} \ deg (v) = 2 | E |}

Egy gráf, amelynek csúcsok halmaza V és élhalmazok E . Ezt az eredményt Leonhard Euler bizonyította híres, 1736-ban megjelent cikkében a hét königsbergi híd problémájáról , amely a gráfelmélet tanulmányának alapszövege.

A grafikonon a páratlan fokú csúcsokat néha páratlan csomópontoknak vagy páratlan csúcsoknak nevezik  ; e terminológia szerint a kézfogás lemma a következőképpen fogalmazható meg: minden véges gráfnak páros a páratlan csomópontja.

Demonstráció

A fokok összegének képletének igazolása példaként szolgál a kettős számolással történő bizonyításra  : az emberek két különböző módon számolják az élek végeinek számát:

• ez duplája az élek számának, mindegyik élnek két vége van;
• ez az egyes csúcsok fokainak összege is.

Az élek végeinek száma az első pont szerint páros, arra következtetünk, hogy a páratlan hozzájárulások a második pont összegében páros számban vannak, ezért az eredmény.

Végtelen grafikonok

A kézfogás lemma nem vonatkozik a végtelen gráfokra, még akkor sem, ha véges számú páratlan fokú csúcsuk van. Például egy végtelen láncgráfnak, amelynek csak egy vége van (ábra) , pontosan egy páratlan fokú csúcsa van (a végén lévő), ahol 1 páratlan szám.

Rendszeres grafikonok esete

A képlet az összege fok azt jelenti, hogy minden reguláris gráf fokú a pontú élek. Ennek egyik következménye, hogy ha a fok páratlan, akkor az élek száma osztható . r{\ displaystyle r}nem{\ displaystyle n}rnem2{\ displaystyle {\ frac {rn} {2}}}r{\ displaystyle r}r{\ displaystyle r}

Megjegyzések

1. V csúcs esetén, ami angolul „csúcsot” jelent .
2. E élre, ami angolul "él" -t jelent.

Hivatkozások

• (fr) Ez a cikk részben vagy egészben az angol Wikipedia "  Handshaking lemma  " című cikkéből származik ( lásd a szerzők felsorolását ) .

1. (a) Joan M. Aldous és Robin J. Wilson , grafikonok és Alkalmazások: egy bevezető Approach , Springer-Verlag ,2000, 444  p. ( ISBN  978-1-85233-259-4 , online olvasás ) , „2.2 . Tétel” , 1. o.  44..

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">