f

Անկախ

Հայ գիտաշխատողներն ապացուցել են` կողմնորոշված գրաֆների համիլտոնյանության համար Նեշ-Վիլյամսի երկու վարկածները հնարավոր չէ լավացնել


ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտի Դիսկրետ մաթեմատիկայի բաժնի գիտաշխատողները պարզել են, որ կողմնորոշված գրաֆների համիլտոնյանության համար անգլիացի հայտնի մաթեմատիկոս Նեշ-Վիլյամսի (1932-2001) առաջարկած երկու վարկածները (1966թ. և 1975թ.) հնարավոր չէ լավացնել, տեղեկացնում է ՀՀ ԳԱԱ գիտության հանրայնացման և հասարակայնության հետ կապերի բաժինը։

Գրաֆը (կողմնորոշված գրաֆը) կետերի/գագաթների բազմություն է, որտեղ գագաթների որոշ զույգեր միացված են կողերով (աղեղներով): Գրաֆը (կողմնորոշված գրաֆը), որը պարունակում է իր յուրաքանչյուր գագաթով ճիշտ մեկ անգամ անցնող ցիկլ (կողմնորոշված ցիկլ), կոչվում է համիլտոնյան: Պարզել, արդյոք տրված գրաֆը համիլտոնյան է, թե՝ ոչ, գրաֆների տեսության կենտրոնական խնդիրներից մեկն է և պատկանում է մաթեմատիկայի, այսպես ասած, NP-լրիվ (դժվար) խնդիրների դասին:

«Համիլտոնյանության և նրա հետ կապված բազմաթիվ խնդիրներ ունեն ինչպես տեսական, այնպես էլ գործնական բազմաթիվ կիրառություններ՝ շրջիկ վաճառականի խնդիրը, ցանցերի նախագծման և մեծ ինտեգրալ սխեմաների ուղեգծման փուլում առաջացած խնդիրները բերվում են համապատասխան գրաֆի համիլտոնյանության խնդրին, գրաֆի ցիկլերի և ճանապարհների հետ կապված խնդիրներ են առաջանում բազմաթիվ այլ բնագավառներում: Հետևաբար, անհրաժեշտություն է առաջանում գտնել այնպիսի պայմաններ, որոնց դեպքում գրաֆը համիլտոնյան է: Բազմաթիվ հետազոտողների կողմից ստացվել են մի շարք բավարար պայմաններ, որոնք ապահովում են գրաֆում համիլտոնյան ցիկլի գոյությունը»,- ասել է ֆիզիկամաթեմատիկական գիտությունների թեկնածու, դոցենտ, առաջատար գիտաշխատող Սամվել Դարբինյանը:

Կողմնորոշված գրաֆների համիլտոնյանության համար ամենահայտնի վարկածները առաջարկել է  Նեշ-Վիլյամսը (1966թ. և 1975թ.), որոնք ձևակերպվում են գրաֆի գագաթներից դուրս եկող և գագաթները մտնող աղեղների քանակների չնվազող հաջորդականությունների միջոցով: Անցած մոտ 50 տարիներին գտնված չէ որևէ արդյունք, որը ինչ-որ չափով կապված է Նեշ-Վիլյամսի վերևում նշված վարկածների հետ, նույնիսկ որոշակի սահմանափակումների դեպքում:

Բիրմինգհեմի համալսարանի պրոֆեսորներ Կուհնն, Օստհուսը և Թրեգլոունը (J. Combin. Theory, B 100, 2010թ.) ցույց են տվել Նեշ-Վիլյամսի վարկածի մոտարկող մի տարբերակի ճշտությունը, երբ գրաֆի գագաթների քանակը բավականին մեծ է: Նշված աշխատանքում հեղինակները կողմնորոշված գրաֆների համիլտոնության համար առաջարկել են ևս մի վարկած, որը ճիշտ է, եթե Նեշ-Վիլյամսի վարկածներից մեկն ու մեկը ճիշտ է: Այդ նույն աշխատանքում հեղինակները հարցնում են. գոյություն ունե՞ն արդյոք այնպիսի կողմնորոշված գրաֆներ, որոնք բավարարում են Նեշ-Վիլյամսի նշված վարկածների բոլոր պայմաններին, բացի մեկից, բայց համիլտոնյան չեն:

«Մեր աշխատանքում, մասնավորապես, տրվում է նշված հարցի պատասխանը՝ ցանկացած դրական ամբողջ թվի համար կառուցելով անթիվ բազմությամբ ոչ համիլտոնյան -կապակցված կողմնորոշված գրաֆներ, որոնք ցույց են տալիս, որ կողմնորոշված գրաֆների համիլտոնյանության համար Նեշ-Վիլյամսի առաջարկած երկու վարկածները, ինչպես նաև Կուհնի, Օստհուսի և Թրեգլոունի վարկածը լավացնելի չեն այն իմաստով, որ նշված վարկածներից ցանկացածի պայմաններից որևէ մեկի թուլացումից հետո պնդումը, ընդհանուր դեպքում, ճիշտ չէ։ Կառուցված կողմնորոշված գրաֆները նույնպես ցույց են տալիս, որ համիլտոնյանության բավարար պայմանները, որոնք ստացել են J. of Graph Theory ամսագրի գլխավոր խմբագիր, դանիացի հայտնի մաթեմատիկոս Թոմասենը (Proc. London Math. Soc. (3)42, 1981թ.) և Դարբինյանը (DAN Arm. SSR, 82(1), 1986թ.), նույնպես դառնում են սխալ, եթե նրանց կիսաաստիճանների վրա դրված պայմաններից մեկը թուլացվում է, նույնիսկ այն դեպքում երբ գրաֆի գագաթային-կապակցվածության թիվը մեծ է»,- ասել է Սամվել Դարբինյանը:

Աշխատանքը կատարվել է «Գրաֆների տեսության էքստրեմալ խնդիրներ» թեմայի շրջանակում՝ բազային ֆինանսավորմամբ: Աշխատանքը հետաքրքրություն է առաջացրել մի շարք մասնագետների շրջանում։ Սամվել Դարբինյանի «On three conjectures of Thomassen and the extremal digraphs for two conjectures of Nash-Williams» աշխատանքը ներկայացվել է գրաֆների տեսության ամենահեղինակավոր գիտական ամսագրին (J. of Graph Theory) և այժմ գտնվում է գրախոսման փուլում:

ՀՀ ԳԱԱ Հայաստան

Հոսանքազրկում Երևանում և մի շարք մարզերում
«Փաստ». Ոչ մի բովանդակային հայտարարություն կամ մեկնաբանություն
Տավուշը պայքարում է, համայնքապետն ԱՄՆ-ում է․ «Հրապարակ»
Ծիծեռնակաբերդ այցը պաշտոնական այցերի պրոտոկոլային մաս չէ․ ԱԳՆ-ն՝ Ղազախստանի նախագահի այցի մասին․ «Ժողովուրդ»
Համերգն առանց տեղական «իշխանիկների»․ «Հրապարակ»
Ժողովրդավարությունը թիվ մեկ «բրենդ» հռչակած կառավարության ղեկավարը չի մեկնաբանել Սամվել Վարդանյանի հանդեպ կատարվածը․ «Ժողովուրդ»
Սահմանազատման երեք տարբերակ է քննարկվել․ «Հրապարակ»
«Ժողովուրդ». Գնել Սանոսյանը «գովերգում» է, իսկ իր տեղակալը համարում է միջազգային մեքենայությունների հեղինակ
«Հրապարակ». Իշխանությունը փորձում է պառակտել շարժումը. Յուրիկների պակաս չի զգացվում
Ավարտվեց «Արցախի իրավունքների վերականգնման հրամայականը՝ ընդդեմ Ադրբեջանի ցեղասպանական քաղաքականության» համագումարը
«Փաստ». Ի՞նչ կապ ունեին Արայիկ Հարությունյանի հարցազրույցի անոնսն ու հետագա «զարգացումները»
Փաշինյանը բրիտանական ԶԼՄ-ներին տրված հարցազրույցում թույլ տվեց խայտառակ, ծայրահեղ վտանգավոր դիվանագիտական սխալ.Առաքելյան
Չարենցավանում անչափահասների միջև տեղի ունեցած վիճաբանությունը վերածվել է ծեծկռտուքի. կա վիրավոր
«Ժողովուրդ». Տավուշի համար ճակատագրական պահին դատախազը լքում է պաշտոնը
«Ժողովուրդ». 36 կգ ոսկու եւ 293 միլիոն ռուբլու անհետացման գործով վկայի կարգավիճակում դատավոր է հարցաքննվել
«Փաստ». Տա­վու­շը կա­րող է լի­նել նոր սկզբի... մեկ­նար­կը
Իրանի նախագահը պաշտոնական այցով ժամանել է Պակիստան
Իսրայելի իշխանությունները հրաժարվել են իրանական ռազմական օբյեկտներին ավելի մեծ հարվածից՝ ԱՄՆ-ի և այլ դաշնակիցների ճնշման ներքո․ NYT
Գերմանիայի նախագահը Թուրքիա այցի շրջանակում առաջինը հանդիպել է Ստամբուլի ընդդիմադիր քաղաքապետին
Իսրայելի ռազմական հետախուզության ղեկավարը հրաժարական է տվել
Ղարաբաղից դուրս բերված ռուսական զորքերը հավանաբար Ուկրաինա կուղարկվեն. Bild
Դաշնակիցները Հունաստանից և Իսպանիայից պահանջում են ՀՕՊ համակարգեր տրամադրել Կիևին. FT
Կիևը հայտարարել է, որ մոտ ապագայում Ուկրաինան կհայտնվի բավականին բարդ իրավիճակում
ԱՄՆ պետքարտուղարը Չինաստան կայցելի
Արևմուտքը միջուկային տերությունների միջև ուղիղ ռազմական բախման եզրին լարախաղացություն է անում. Լավրով
Ավելին
Ավելին