Մասնակից:SirunyanL/Ավազարկղ3
Ձեռքսեղմումների լեմմա՝ գրաֆների տեսության մեջ (մաթեմատիկայի ճյուղ), պնդումն է, ըստ որի ցանկացած վերջավոր չուղղորդված գրաֆ ունի կենտ աստիճանների զույգ թվով գագաթներ։ Ավելի խոսակցական ձևով՝ որոշ քանակի մարդիկ հանդիպելիս, նրանցից ոմանք ձեռք են սեղմում, զույգ մարդիկ պետք է սեղմած լինեն կենտ թվով ձեռքեր: Գրաֆի կենտ աստիճանի գագաթները երբեմն կոչվում են կենտ հանգույցներ կամ կենտ գագաթներ։ Այս տերմինաբանությամբ ձեռքսեղմումների լեմման կարող է վերաշարադրվել այսպես՝ յուրաքանչյուր գրաֆ ունի զույգ թվով կենտ հանգույցներ:
Ձեռքսեղմումների լեմման աստիճանի գումարի բանաձևի հետևանքն է (երբեմն կոչվում է նաև ձեռքսեղմման լեմմա)։
գրաֆի համար, որի գագաթները՝ V են, իսկ կողերի բազմությունը՝ E.
Երկու արդյունքն էլ ապացուցեց Էյլերը ՝ Կոենիգսբերգի յոթ կամուրջների մասին իր հայտնի ելույթում (1736): Այս աշխատանքը հիմք դրեց գրաֆների տեսության ոլորտում հետազոտությունների համար:
Ապացույց[խմբագրել | խմբագրել կոդը]
Վերոնշյալ բանաձևն ապացուցելիս Էյլերը կիրառեց կրկնակի (կրկնվող) հաշվման տեխնիկան: Նա հաշվեց միջադեպերի զույգերի թիվը (v, e), որտեղ e- ն կողն է, իսկ v- ն դրա ծայրերից մեկի գագաթն է երկու տարբեր եղանակներով։ Երբ կող է ավելացվում, գրաֆի գագաթների աստիճանների գումարը մեծանում է 2 -ով, այսինքն գագաթը v պատկանում է deg (v) զույգերին, որտեղ deg (v) գագաթի աստիճանն է (դրան հարևան կողերի թիվը): Հետևաբար, հանդիպող զույգերի թիվը համընկնում է բոլոր աստիճանների գումարի հետ: Այնուամենայնիվ, յուրաքանչյուր կող պատկանում է երկու միջադեպերի զույգերի, քանի որ այն ունի երկու ծայրագագաթ: Հետևաբար, միջադեպերի զույգերի թիվը ։ Քանի որ այս երկու բանաձևերը նախատեսված են նույն հավաքածուի համար, դրանց արժեքները նույնն են:
Ամբողջ թվերի գումարի զույգ կամ կենտ լինելը կախված չէ զույգ քանակով բաղադիրչներից։ Գումարը զույգ է նույնիսկ այն դեպքում, եթե կենտ բաղադրիչների թիվը զույգ է (կենտ է հակառակ դեպքում): Քանի որ հավասարման մի կողմը միշտ զույգ է, մյուս կողմը պետք է պարունակի զույգ քանակով կենտ բաղադրիչներ, այսինքն ՝ կենտ աստիճանի գագաթներ:
Կանոնավոր գրաֆներ[խմբագրել | խմբագրել կոդը]
Աստիճանի գումարի բանաձևերը ենթադրում են, որ n գագաթներով k- կանոնավոր գրաֆը ունի kn / 2 կող[1] ։ Մասնավորապես, եթե k կենտ է, ապա կողերիի թիվը պետք է բաժանվի k- ի:
Անվերջ գրաֆներ[խմբագրել | խմբագրել կոդը]
Լեման չի տարածվում անվերջ գրաֆների վրա, նույնիսկ եթե դրանք ունեն վերջավոր թվով կենտ գագաթներ: Օրինակ, մեկ ծայր գագաթ ունեցող անսահման ուղին ունի մեկ կենտ գագաթ (այսինքն ՝ կենտ թիվ):
Հավելվածներ[խմբագրել | խմբագրել կոդը]
Ձեռքսեղմումների լեման օգտագործվում է նաեւ Սփերների լեմայի ապացույցներից մեկում, ինչպես նաեւ «սար բարձրանալու» խնդրում:
Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]
- ↑ Олдес, Джоан M.; Уилсон, Робин Дж. (2000), «Theorem 2.2», Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, էջ 44, ISBN 978-1-85233-259-4
Աղբյուրներ[խմբագրել | խմբագրել կոդը]
- Кэмерон, Кэти; Эдмондс, Джек (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.