National Academy of Sciences of the Republic of Armenia
ՀԱՅ  ENG  РУС
Home academy [@] sci.am Facebook Page
General Page About Academy Divisions Organizations Members Contact us
Yervant Zorian
Dr., Professor
COVID-19
Structure
Presidium Members
Documents
Innovation Proposals
Publications
Funds
Conferences
Competitions
Photogallery
Videogallery
Web Resources
Other Academies
"Gitutyun" newspaper
"In the World of Science" Journal
Publications in Press
Notices
Anniversaries
Universities
News
Scientific Results
Diaspora Department presents
Young Scientist Tribune
Our Honored Figures
Announcements
Lindau Nobel Laureate Meeting
Sitemap
Scientific Results
15/09/2023
ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտի գիտաշխատողներն ապացուցել են` կողմնորոշված գրաֆների համիլտոնյանության համար Նեշ-Վիլյամսի երկու վարկածները հնարավոր չէ լավացնել

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

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

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

Կողմնորոշված գրաֆների համիլտոնյանության համար ամենահայտնի վարկածները առաջարկել է  Նեշ-Վիլյամսը (1966թ. և 1975թ.), որոնք ձևակերպվում են գրաֆի գագաթներից դուրս եկող և գագաթները մտնող աղեղների քանակների չնվազող հաջորդականությունների միջոցով: Անցած մոտ 50 տարիներին գտնված չէ որևէ արդյունք, որը ինչ-որ չափով կապված է Նեշ-Վիլյամսի վերևում նշված վարկածների հետ, նույնիսկ որոշակի սահմանափակումների դեպքում: Բիրմինգհեմի համալսարանի պրոֆեսորներ Կուհնն, Օստհուսը և Թրեգլոունը (J. Combin. Theory, B 100, 2010թ.) ցույց են տվել Նեշ-Վիլյամսի վարկածի մոտարկող մի տարբերակի ճշտությունը, երբ գրաֆի գագաթների քանակը բավականին մեծ է: Նշված աշխատանքում հեղինակները կողմնորոշված գրաֆների համիլտոնության համար առաջարկել են ևս մի վարկած, որը ճիշտ է, եթե Նեշ-Վիլյամսի վարկածներից մեկն ու մեկը ճիշտ է: Այդ նույն աշխատանքում հեղինակները հարցնում են. գոյություն ունեն արդյոք այնպիսի կողմնորոշված գրաֆներ, որոնք բավարարում են Նեշ-Վիլյամսի նշված վարկածների բոլոր պայմաններին, բացի մեկից, բայց համիլտոնյան չեն: «Մեր աշխատանքում, մասնավորապես, տրվում է նշված հարցի պատասխանը՝ ցանկացած դրական ամբողջ k թվի համար կառուցելով անթիվ բազմությամբ ոչ համիլտոնյան k-կապակցված կողմնորոշված գրաֆներ, որոնք ցույց են տալիս, որ կողմնորոշված գրաֆների համիլտոնյանության համար Նեշ-Վիլյամսի առաջարկած երկու վարկածները, ինչպես նաև Կուհնի, Օստհուսի և Թրեգլոունի վարկածը լավացնելի չեն այն իմաստով, որ նշված վարկածներից ցանկացածի պայմաններից որևէ մեկի թուլացումից հետո պնդումը, ընդհանուր դեպքում, ճիշտ չէ։ Կառուցված կողմնորոշված գրաֆները նույնպես ցույց են տալիս, որ համիլտոնյանության բավարար պայմանները, որոնք ստացել են 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) և այժմ գտնվում է գրախոսման փուլում:

ՀՀ ԳԱԱ գիտության հանրայնացման և հասարակայնության հետ կապերի բաժին
15․09․2023թ․


Notices








On the 21st of February, 2024, The Institute of Language named after H. Acharyan of the National Academy of Sciences of the Republic of Armenia invites you to participate in the international conference "Current Problems of Studying and Teaching the Armenian Language". The conference will take place at the Institute of Language

Ս.թ. փետրվարի 23-ին ժ. 15:00-ին ՀՀ ԳԱԱ նիստերի դահլիճում (Բաղրամյան պող., 24) տեղի կունենա «Չընդհատված ծածկագիր. հայեր» գիտական ֆիլմի ցուցադրությունը և քննարկումը

The Shirak Center for Armenological Studies of NAS RA is starting to publish the 1 (27) volume of the "Scientific Works" journal for 2024. Priority is given to articles in English and Russian. The deadline for receiving articles is March 1, 2024

Международный инновационный центр нанотехнологий СНГ (МИЦНТ СНГ) при поддержке Межгосударственного фонда гуманитарного сотрудничества государств - участников СНГ (МФГС) и Объединенного института ядерных исследований объявляет о проведении конкурса на соискание грантов на разработку проектов в рамках деятельности МИЦНТ СНГ в 2024 году и очередной Стажировки молодых ученых и специалистов стран СНГ в Дубне в апреле - мае 2024года

The international conference "Armenia as a Civilizational Crossroad: Historical and Cultural Ties" is scheduled to take place from March 28 to 30, 2024, organized by the National Academy of Sciences of the Republic of Armenia and Yerevan State University

ՀՀ գիտության և տեխնիկայի զարգացման 2020-2024թթ. գերակայության ՀՀ կառավարության որոշման նախագիծ

Publications in Press
21/02/2024

Դա հետաքրքիր մեխանիզմ է. Օրինակ՝ կարող է սահմանագծման գործընթացում գիտական թեմա ի հայտ գալ. Փաշինյան
news.am
21/02/2024

Փաշինյանն առաջարկել է բուհերի ազատված շենքերը վարձակալության տալ և եկամուտն ուղղել «Ակադեմիական քաղաքի» ֆինանսավորմանը
news.am
21/02/2024

Գիտական կոչումների շնորհման գործընթացում ստաբիլ ցածր դինամիկա կա. պատճառը գրագողության դեմ պայքարն է. Սարգիս Հայոցյան
news.am
20/02/2024

Վարչապետին է ներկայացվել Բարձրագույն կրթության և գիտության կոմիտեի 2023թ. հաշվետվությունը
primeminister.am
This site has been visited
6 852 978

times since 01.01.2005
National Academy of Sciences of the Republic of Armenia
NAS RA Logo (black, blue)
Top Website last updated on:  17:41, 23/02/2024 Top
General Page - About Academy - Divisions - Organizations - Members - Contact us - Structure - COVID-19
Presidium Members - Documents - Innovation Proposals - Publications - Funds - Conferences - Competitions
Photogallery - Videogallery - Web Resources - Other Academies - "Gitutyun" newspaper - "In the World of Science" Journal - Publications in Press
Notices - Anniversaries - Universities - News - Scientific Results - Diaspora Department presents - Young Scientist Tribune
Our Honored Figures - Announcements - Lindau Nobel Laureate Meeting - Sitemap
© Copyright 1998-2024 All Rights Reserved.
Website is created and supported by Academical Scientific Research Computer Network of Armenia (ASNET-AM)
For any suggestions write to webmaster {[ at ]} sci.am