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

Տրված գրաֆի զույգ գագաթները (չորսն են ՝ 2, 4, 5 և 6) ունեն կենտ աստիճան: Բոլոր գագաթների աստիճանների գումարը 14 է, այսինքն `գրաֆի կողերի կրկնապատիկը:

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

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

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

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

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

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

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

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

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

Copyright