Ձեռքսեղմումների լեմմա

Ձեռքսեղմումների լեմմա՝ Գրաֆների տեսության մեջ (մաթեմատիկայի ճյուղ), պնդումն է, ըստ որի ցանկացած վերջավոր չուղղորդված գրաֆ ունի կենտ աստիճանների զույգ թվով գագաթներ։ Ավելի խոսակցական ձևով՝ որոշ քանակի մարդիկ հանդիպելիս, նրանցից ոմանք ձեռք են սեղմում, զույգ մարդիկ պետք է սեղմած լինեն կենտ թվով ձեռքեր։ Գրաֆի կենտ աստիճանի գագաթները երբեմն կոչվում են կենտ հանգույցներ կամ կենտ գագաթներ։ Այս տերմինաբանությամբ ձեռքսեղմումների լեմման կարող է վերաշարադրվել այսպես՝ յուրաքանչյուր գրաֆ ունի զույգ թվով կենտ հանգույցներ։

Ձեռքսեղմումների լեմման աստիճանի գումարի բանաձևի հետևանքն է (երբեմն կոչվում է նաև ձեռքսեղմման լեմմա)։

գրաֆի համար, որի գագաթները՝ V են, իսկ կողերի բազմությունը՝ E.

Երկու արդյունքն էլ ապացուցեց Էյլերը՝ Քյոնիգսբերգի յոթ կամուրջները մասին իր հայտնի ելույթում (1736)։ Այս աշխատանքը հիմք դրեց գրաֆների տեսության ոլորտում հետազոտությունների համար։

Ապացույց
Վերոնշյալ բանաձևն ապացուցելիս Էյլերը կիրառեց կրկնակի (կրկնվող) հաշվման տեխնիկան։ Նա հաշվեց միջադեպերի զույգերի թիվը (v, e), որտեղ e- ն կողն է, իսկ v- ն դրա ծայրերից մեկի գագաթն է երկու տարբեր եղանակներով։ Երբ կող է ավելացվում, գրաֆի գագաթների աստիճանների գումարը մեծանում է 2 -ով, այսինքն գագաթը v պատկանում է deg (v) զույգերին, որտեղ deg (v) գագաթի աստիճանն է (դրան հարևան կողերի թիվը)։ Հետևաբար, հանդիպող զույգերի թիվը համընկնում է բոլոր աստիճանների գումարի հետ։ Այնուամենայնիվ, յուրաքանչյուր կող պատկանում է երկու միջադեպերի զույգերի, քանի որ այն ունի երկու ծայրագագաթ։ Հետևաբար, միջադեպերի զույգերի թիվը  ։ Քանի որ այս երկու բանաձևերը նախատեսված են նույն հավաքածուի համար, դրանց արժեքները նույնն են։

Ամբողջ թվերի գումարի զույգ կամ կենտ լինելը կախված չէ զույգ քանակով բաղադիրչներից։ Գումարը զույգ է նույնիսկ այն դեպքում, եթե կենտ բաղադրիչների թիվը զույգ է (կենտ է հակառակ դեպքում)։ Քանի որ հավասարման մի կողմը միշտ զույգ է, մյուս կողմը պետք է պարունակի զույգ քանակով կենտ բաղադրիչներ, այսինքն ՝ կենտ աստիճանի գագաթներ։

Կանոնավոր գրաֆներ 
Աստիճանի գումարի բանաձևերը ենթադրում են, որ n գագաթներով k- կանոնավոր գրաֆը ունի kn / 2 կող։ Մասնավորապես, եթե k կենտ է, ապա կողերիի թիվը պետք է բաժանվի k- ի։

Անվերջ գրաֆներ 
Լեման չի տարածվում անվերջ գրաֆների վրա, նույնիսկ եթե դրանք ունեն վերջավոր թվով կենտ գագաթներ։ Օրինակ, մեկ ծայր գագաթ ունեցող անսահման ուղին ունի մեկ կենտ գագաթ (այսինքն ՝ կենտ թիվ)։

Հավելվածներ 
Ձեռքսեղմումների լեմման օգտագործվում է նաեւ Սփերների լեմմայի ապացույցներից մեկում, ինչպես նաև «սար բարձրանալու» խնդրում։

Ծանոթագրություններ

Աղբյուրներ
.
. Печать и перевод: .
.
.

Գրաֆների տեսություն