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
Megerdich Toomanian
Dr. of Math. Sciences, Prof.
Structure
Presidium Members
Documents
Innovation Proposals
Publications
Funds
Conferences
Competitions
International cooperation
Youth programs
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
Sitemap
COVID-19
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








Ս.թ. ապրիլի 23-ին ժ. 13:00-ից ԳԱԱ տարեկան ընդհանուր ժողովի շրջանակներում ՀՀ ԳԱԱ նախագահության նիստերի փոքր դահլիճում կկայանան գիտական զեկուցումներ,որի ընթացքում ելույթ կունենան ԳԱԱ արտասահմանյան անդամներ՝ Գերմանիայից, Մեծ Բրիտանիայից, Շվեդիայից, Ֆրանսիայից և Ռուսաստանի Դաշնությունից

Ս/թ. ապրիլի 26-ին, ժամը 12.00-ին, ՀՀ ԳԱԱ մոլեկուլային կենսաբանության ինստիտուտը և Հայկական տիեզերական ֆորումը անց են կացնում «Science in Space Analog Missions: AMADEE-24 Mars Simulation Results and the Future Prospects» աշխատաժողով (ՀՀ գիտությունների ազգային ակադեմիայի կլոր դահլիճ, Բաղրամյան պ., 24)

On 28–30 April, 2025 Institute of Mathematics of NAS RA and Regional Mathematical Center of Southern Federal University of Russia, RF organize Workshop OTHA Spring -2025 "On operator theory, harmonic analysis and their applications" (Yerevan, Armenia)

On April 29, 2025, the NAS RA, the Ministry of Education, Science, Culture and Sports of RA, the International Scientific and Educational Center of NAS RA, the Institute of Language after H. Acharian of NAS RA and the Institute of Literature after M. Abeghyan of NAS RA will organize a Pan-Armenian scientific conference on the topic "Armenian language and Armenian Literature: development trends, opportunities for popularization and their reflection in the educational process"

On May 5-8, 2025, the Scientific Center of Zoology and Hydroecology of the National Academy of Sciences of RA and the Yerevan State University are jointly organizing an International conference "Biodiversity, Conservation and Climate Change" (Yerevan, NAS RA main building)

On 5-9 May, 2025, Byurakan Astrophysical Observatory after V.Ambartsumian of NAS RA organizes 17th Armenian-Georgian Astronomical Colloquium in Byurakan

On May 6, 2025, at 15:00 PM, at the library of the Institute of Archaeology and Ethnography NAS RA will take place the presentation of the book by the department of Anthropology of Social Processes and Institutions titled "War and Memory: The Problem of Memorialization of the 44-Day War"

On 16-21 June, 2025, the Institute of Applied Problems of Physics of NAS RA organizes "IV International Scientific School for Radiation Physics and Related Applications named after Academician Alpic Mkrtchyan", in Yerevan

On 8-11 September, 2025, the Institute for Physical Research of NAS RA is holding the XIII International Conference on Magnetic and Superconducting Materials (MSM25) in Yerevan, Armenia

On September 26-27, 2025 the Shirak Center for Armenological Studies of NAS RA invites you to Gyumri to participate in the 12th International Conference entitled "Historical and Cultural Heritage of Shirak: Contemporary Issues of Armenian Studies"

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

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

Publications in Press
05/05/2025

Կյանքից հեռացել է ԳԱԱ նախկին նախագահ, ակադեմիկոս Ռադիկ Մարտիրոսյանը
armenpress.am
05/05/2025

Մահացել է ՀՀ ԳԱԱ ակադեմիկոս Ռադիկ Մարտիրոսյանը Ամբողջական հոդվածը կարող եք կարդալ այս հասցեով՝ https://factor.am/887469.html © factor.am
factor.am
05/05/2025

Կյանքից հեռացել է ՀՀ ԳԱԱ ակադեմիկոս Ռադիկ Մարտիրոսյանը
hesc.am
05/05/2025

Կյանքից հեռացել է ԳԱԱ նախկին նախագահ Ռադիկ Մարտիրոսյանը
livenews.am
This site has been visited
7 323 563

times since 01.01.2005
National Academy of Sciences of the Republic of Armenia
NAS RA Logo (black, blue)
Top Website last updated on:  00:02, 09/05/2025 Top
General Page - About Academy - Divisions - Organizations - Members - Contact us - Structure - Presidium Members
Documents - Innovation Proposals - Publications - Funds - Conferences - Competitions - International cooperation
Youth programs - 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 - Sitemap - COVID-19
© Copyright 1998-2025 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