Քյոնիգսբերգի յոթ կամուրջները

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Քյոնիգսբերգ քաղաքը Էյլերի ապրած ժամանակաշրջանում

«Քյոնիգսբերգի յոթ կամուրջները» հին հռչակավոր մաթեմատիկական խնդիր է։ Լեոնարդ Էյլերի լուծումը 1735 թվականին հիմք դրեց գրաֆների տեսությանը:

Պրուսիայի Քյոնիգսբերգ քաղաքը (այժմ Կալինինգրադ, Ռուսաստան) գտնվում էր Պրեգոլյա գետի երկու ափերին։ Քաղաքը բաժանված էր չորս ցամաքների, որոնք կապված էին միմյանց մայրցամաքին յոթ կամուրջներով։ Խնդիրն էր՝ անցնել ողջ քաղաքը, օգտագործելով բոլոր յոթ կամուրջները։ Ընդ որում յուրաքանչյուր կամրջով կարելի էր անցնել միայն մեկ անգամ։ Չէր կարելի օգտագործել որևէ այլ ճանապարհ, բացի կամուրջներից։ Բացի այդ չէր թույլատրվում կամրջի կեսից ետ դառնալ։ Շրջագայությունը կարող էր ավարտվել սկզբնակետից բացի ցանկացած այլ կետում։

Էյլերն ապացուցեց, որ խնդիրը չունի լուծում։ Ամենադժվարը վերլուծության տեխնիկան զարգացնելն էր և մաթեմատիկական խստությամբ պնդումն ապացուցելը, որի արդյունքում ծնվեց ժամանակակից գրաֆների տեսությունը:

Էյլերի վերլուծությունը[խմբագրել | խմբագրել կոդը]

Էյլերը նկատեց, որ ճանապարհի ընտրությունը խնդրի լուծման համար կարևոր չէ։ Կարևորը կամուրջներով անցնելու հերթականությունն է։ Սա հնարավորություն տվեց նրան վերակազմել խնդիրը աբստրակտ պայմաններով։ Նա հեռացրեց ամեն ինչ, բացի ցամաքային տարածքներից և դրանք կապող կամուրջներից։ Էյլերը ցամաքային մասերը փոխարինեց կետերով, իսկ կամուրջները՝ գծերով։ Յուրաքանչյուր գիծ (կամուրջ) ցույց էր տալիս, թե որ գագաթը (ցամաք) որին էր միացված։ Այսպես նա ստացավ գրաֆ:

Konigsberg bridges.png7 bridges.svgKönigsberg graph.svg

Հաջորդիվ, Էյլերը նկատեց, որ բացի սկզբանական և վերջնական գագաթներից` բոլոր գագաթները որևէ կամրջով անցնելիս պետք է այնտեղից դուրս գալ որևէ այլ կամրջով։ Այլ խոսքերով, մուտքերի և ելքերի քանակները պետք է հավասար լինեին։ Հետևաբար բացի սկզբնական և վերջնական գագաթներից` յուրաքանչյուր գագաթին կից կամուրջների թիվը պետք է զույգ լիներ։ Այնուամենայնիվ, բոլոր գագաթների աստիճանները կենտ էին. մեկից դուրս էր գալիս հինգ կամուրջ, իսկ մյուսներից՝ երեքական։

Գրաֆների տեսության մեջ գրաֆի բոլոր կողերը մեկ անգամ այցելող ուղին կոչվում է Էյլերյան զբոսանք՝ ի պատիվ Էյլերի։ Պարզվում է, որ կապակցված գրաֆում Էլյերյան փակ զբոսանքի գոյության համար անհրաժեշտ է և բավարար, որ բոլոր գագաթներն ունենան զույգ աստիճաններ։

Էյլերի աշխատանքը ներկայացվեց Սանկտ Պետերբուրգի համալսարանին 1735 թվականի oգոստեսի 26-ին։ Եվ Commentarii academiae scientiarum Petropolitanae ամսագրում 1741 թվականին հրապարակվեց որպես Solutio problematis ad geometriam situs pertinentis:

Կարևորությունը մաթեմատիկայի պատմության մեջ[խմբագրել | խմբագրել կոդը]

«Քյոնիգսբերգի յոթ կամուրջները» խնդրի լուծումը Էյլերի կողմից համարվում է գրաֆների տեսության առաջին թեորեմը։ Գրաֆների տեսությունն այժմ դիտվում է որպես կոմբինատորիկայի մի ճյուղ։

Կամուրջների ներկայիս դրությունը[խմբագրել | խմբագրել կոդը]

Յոթ կամուրջներից երկուսը ոչնչացվել են Քյոնիգսբերգի ռմբակոծման ժամանակ՝ Երկրորդ համաշխարհային պատերազմի տարիներին։ Մյուս երկուսը հետագայում վերացվել են և փոխարինվել ժամանակակից մայրուղով։ Մնացած երեք կամուրջները դեռ կանգուն են, չնայած դրանցից միայն երկուսն են Էյլերի ժամանակներից (երրորդը վերակառուցվել է 1935 թվականին)։ Այսպիսով, այժմ Կալինինգրադում կա հինգ կամուրջ։

Գրաֆների տեսության լեզվով գագաթներից երկուսի աստիճանը 2 է, իսկ մյուս երկուսինը՝ 3: Ուստի Էյլերյան ուղին այժմ հնարավոր է, սակայն եղած ուղին տուրիստների համար հարմար չէ, քանի որ սկսվում է մի գետի ափին և ավարտվում՝ մյուսին։