Lemma kädenpuristuksista

Kättelylemma on graafiteorian asema , jonka mukaan missä tahansa äärellisessä suuntaamattomassa graafissa on parillinen määrä parittoman asteen pisteitä . Nimi tulee tunnetusta matemaattisesta ongelmasta: on tarpeen todistaa, että missä tahansa ryhmässä parittoman määrän muita ihmisiä kätteleneiden määrä on parillinen.

Lemma on seuraus potenssisummakaavasta , jota joskus kutsutaan myös kättelylemmaksi :

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

graafille, jossa on monta kärkeä ja monta reunaa . Molemmat tulokset osoitti Euler raportissaan Königsbergin seitsemästä sillasta (1736), mikä merkitsi graafiteorian tutkimuksen alkua. $V$ $E$

Parittomat pisteet graafissa kutsutaan joskus parittomiksi pisteiksi tai parittomiksi solmuiksi ; tätä terminologiaa käyttäen lemma voidaan muotoilla uudelleen seuraavasti: jokaisessa graafissa on parillinen määrä parittomia pisteitä.

Potenssisummakaava tarkoittaa, että - säännöllisellä graafilla , jossa on useita pisteitä, on reunat [1] ; erityisesti, jos pariton, reunojen lukumäärän on oltava jaollinen . $k$ $n$ $kn/2$ $k$ $k$

Lemma ei päde äärettömiin graafeihin , vaikka niillä olisi äärellinen määrä parittomia pisteitä. Esimerkiksi äärettömällä polulla , jossa on yksi päätepiste, on yksi pariton kärkipiste (eli pariton luku).

Lemmaa käytetään yhdessä Spernerin lemman todistuksessa sekä " vuorikiipeilyongelmassa ".

Todiste

Potensseja muotoillessaan Euler käytti kaksinkertaisen (toistuvan) laskennan tekniikkaa: hän laski sattuvien parien lukumäärän , jossa on reuna ja yksi sen päätypisteistä kahdella eri tavalla. Kun lisäät reunan, graafin kärkien asteiden summa kasvaa 2:lla, eli kärki kuuluu pareihin, missä on kärjen aste (sille osuvien reunojen lukumäärä). Siksi tapausparien lukumäärä on sama kuin kaikkien potenssien summa. Jokainen reuna kuuluu kuitenkin kahteen tapahtumapariin, koska sillä on kaksi päätepistettä. Siksi tapausparien lukumäärä on yhtä suuri kuin . Koska nämä kaksi kaavaa ovat samalle joukolle, niiden merkitykset ovat samat. ${\näyttötyyli (v,e)}$ $e$ $v$ $v$ $\deg(v)$ $\deg(v)$ $2|E|$

Se, onko kokonaislukujen summa parillinen vai pariton , ei riipu parillisten termien määrästä. Summa on parillinen, jos parittomien termien määrä on parillinen (ja muuten pariton). Koska yhtälön yksi osa on aina parillinen , toisen osan tulee sisältää parillinen määrä parittomia termejä eli parittoman asteen kärkipisteitä. $(2|E|)$

Muistiinpanot

↑ Oldes, Joan M. & Wilson, Robin J. (2000), Lause 2.2, Grafit ja sovellukset: johdannon lähestymistapa , matematiikan perustutkintosarja, avoin yliopisto, Springer-Verlag, s. 44, ISBN 978-1-85233-259-4

Kirjallisuus

Cameron, Cathy & Edmonds, Jack (1999), Joitakin parillisten solmujen graafisia käyttötapoja , Annales de l'Institut Fourier , osa 49 (3): 815–827 , < http://www.numdam.org/ item?id=AIF_1999__49_3_815_0 > .
Euler, L. (1736), Solutio problematis ad geometriam situs pertintis , Commentarii Academiae Scientiarum Imperialis Petropolitanae T. 8: 128–140 , < http://math.dartmouth.edu/~euler/docs/originals/E053.pdf > . Painatus ja käännös: Biggs, N. L.; Loyd, I. K. & Wilson, R. J. (1976), Graph Theory 1736–1936 , Oxford University Press .
Papadimitriou, Christos H. (1994), Pariteettiargumentin monimutkaisuudesta ja muista tehottomista olemassaolon todisteista , Journal of Computer and System Sciences , osa 48 (3): 498–532 , DOI 10.1016/S0022-0000(05)80063 -7 .
Thomason, A. J. (1978), Hamiltonin syklit ja ainutlaatuisen reunan värikkäät graafit , Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , voi. 3, Annals of Discrete Mathematics, s. 259–268 , DOI 10.1016/S0167-5060(08)70511-9 .