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

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

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

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

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

 →
 →

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

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

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

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

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

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

Մաթեմատիկական խնդիրներ
Մաթեմատիկական գլուխկոտրուկներ
Մաթեմատիկայի պատմություն
Գրաֆների տեսություն
Կալինինգրադի կամուրջներ
Գլուխկոտրուկներ