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

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

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

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

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

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

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

Ապացույց

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

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

Կանոնավոր գրաֆներ

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

Անվերջ գրաֆներ

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

Հավելվածներ

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

Աղբյուրներ

• Кэмерон, Кэти; Эдмондс, Джек (1999), «Some graphic uses of an even number of odd nodes», Annales de l'Institut Fourier, 49 (3): 815–827, MR 1703426.
• Эйлер, Л. (1736), «Solutio problematis ad geometriam situs pertinentis» (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Печать и перевод: Биггз, Н. Л.; Лойд, И. K.; Уилсон, Р. Дж. (1976), Graph Theory 1736–1936, Oxford University Press.
• Пападимитриу, Христос Х. (1994), «On the complexity of the parity argument and other inefficient proofs of existence», Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.
• Томасон, A. Дж. (1978), «Hamiltonian cycles and uniquely edge colourable graphs», Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, էջեր 259–268, doi:10.1016/S0167-5060(08)70511-9, MR 0499124.