Lemma o podání ruky

Lemma handshake je pozice teorie grafů , podle které má každý konečný neorientovaný graf sudý počet vrcholů lichých stupňů . Název pochází ze známého matematického problému: je třeba dokázat, že v jakékoli skupině je počet lidí, kteří si potřásli rukou s lichým počtem jiných lidí, sudý.

Lema je důsledkem vzorce mocninného součtu , někdy také nazývaného lemma pro podání ruky :

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

pro graf s mnoha vrcholy a mnoha hranami . Oba výsledky dokázal Euler ve své zprávě o sedmi mostech v Königsbergu (1736), která znamenala začátek výzkumu v oblasti teorie grafů. $PROTI$ $E$

Vrcholy lichých stupňů v grafu se někdy nazývají liché vrcholy nebo liché uzly ; pomocí této terminologie lze lemma přeformulovat takto: každý graf má sudý počet lichých vrcholů.

Ze vzorce mocninného součtu vyplývá, že - pravidelný graf s počtem vrcholů má hrany [1] ; zejména pokud je lichý, počet hran musí být dělitelný . $k$ $n$ $kn/2$ $k$ $k$

Lema neplatí pro nekonečné grafy , i když mají konečný počet lichých vrcholů. Například nekonečná cesta s jedním koncovým vrcholem má jeden lichý vrchol (tj. liché číslo).

Lemma je použito v jednom z důkazů Spernerova lemmatu , stejně jako " problém horolezectví ".

Důkaz

Při formulaci mocnin použil Euler techniku dvojitého (opakovaného) počítání: dvěma různými způsoby počítal počet dopadajících dvojic , kde je hrana a jeden z jejích koncových vrcholů. Při přidávání hrany se součet stupňů vrcholů grafu zvětší o 2, to znamená, že vrchol patří do dvojic, kde je stupeň vrcholu (počet hran, které k němu dopadají). Počet dopadajících dvojic je tedy stejný jako součet všech mocnin. Každá hrana však patří ke dvěma incidentním párům, protože má dva koncové vrcholy. Počet párů incidentů je tedy roven . Protože tyto dva vzorce jsou pro stejnou množinu, jejich význam je stejný. $(v,e)$ $E$ $proti$ $proti$ $\deg(v)$ $\deg(v)$ $2|E|$

Zda je součet celých čísel sudý nebo lichý , nezávisí na počtu sudých členů. Součet je sudý, pokud je počet lichých členů sudý (a jinak lichý). Protože jedna část rovnice je vždy sudá , druhá část musí obsahovat sudý počet lichých členů, tedy vrcholů lichého stupně. $(2|E|)$

Poznámky

↑ Oldes, Joan M. & Wilson, Robin J. (2000), Věta 2.2, Grafy a aplikace: Úvodní přístup , Řada vysokoškolské matematiky, The Open University, Springer-Verlag, str. 44, ISBN 978-1-85233-259-4

Literatura

Cameron, Cathy & Edmonds, Jack (1999), Některé grafické využití sudého počtu lichých uzlů , Annales de l'Institut Fourier vol. 49 (3): 815–827 , < http://www.numdam.org/ item?id=AIF_1999__49_3_815_0 > .
Euler, L. (1736), Solutio problematis ad geometriam situs pertinentis , Commentarii Academiae Scientiarum Imperialis Petropolitanae T. 8 : 128–140 , < http://math.dartmouth.edu/~euler/docs/originals/E053.pdf . Tisk a překlad: Biggs, N. L.; Loyd, I. K. & Wilson, R. J. (1976), Teorie grafů 1736–1936 , Oxford University Press .
Papadimitriou, Christos H. (1994), O složitosti argumentu parity a dalších neefektivních důkazech existence , Journal of Computer and System Sciences vol. 48 (3): 498–532 , DOI 10.1016/S0022-0000(05)80063 -7 .
Thomason, A. J. (1978), Hamiltonian cycles and uniquely edge colored graphs , Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , sv. 3, Annals of Discrete Mathematics, str. 259–268 , DOI 10.1016/S0167-5060(08)70511-9 .