Национальная академия наук Республики Армения
ՀԱՅ  ENG  РУС
Home academy [@] sci.am Facebook Page
Главная страница Об Академии Отделения Организации Члены Связь с нами
Армен Седракян
Д.ф.-м.н., профессор
Структура
Члены президиума
Документы
Инновационные предложения
Публикации
Фонды
Конференции
Конкурсы
Международное сотрудничество
Молодежные программы
Фотогалерея
Видеогалерея
Веб ресурсы
Другие академии
Газета "Гитутюн"
Журнал "В мире науки"
Публикации в прессе
Анонсы
Юбилеи
Университеты
Новости
Научные результаты
Отдел диаспоры представляет
Трибуна молодого ученого
Наши заслуженные деятели
Объявления
Карта сайта
COVID-19
Фонд развития науки НАН РА
Фонд развития науки НАН РА
Всеармянский фонд финансирования арменоведческих исследований
Всеармянский фонд финансирования арменоведческих исследований
Научно-аналитический фонд Гегард
Научно-аналитический фонд Гегард
Международный научно-образовательный центр НАН РА
Международный научно-образовательный центр НАН РА
Фундаментальная научная библиотека НАН РА
Фундаментальная научная библиотека НАН РА
Международная комиссия по присуждению международной премии имени Виктора Амбарцумяна
Международная комиссия по присуждению международной премии имени Виктора Амбарцумяна
Национальный информационный пункт Армении HORIZON 2020
Национальный информационный пункт Армении HORIZON 2020
EURAXESS-Armenia Portal
EURAXESS-Armenia Portal

Академическая научно-исследовательская компьютерная сеть Армении
Академическая научно-исследовательская компьютерная сеть Армении
Научные результаты
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թ․


Анонсы








С 7-11 октября этого года международная организация "ИКРАНЕТ-Центр" организует международную конференцию "High Energy Astrophysics and Cosmology in the era of all-sky surveys (HEACOSS 2024)"

С 11 по 13 октября 2024 года в Национальной академии наук РА состоится всеармянская научная конференция "Eстественные науки, математика, техника, информатика в XXI веке: проблемы популяризации и обучения и пути их решения"

С 15-19 октября этого года приглашаем принять участие на 12-ом международном симпозиуме "Оптика и ее применения", который пройдет в Ереване (Армения) (12th Symposium on "Optics & its Applications (OPTICS12)). Срок регистрации: 15-ое августа 2024г.

С 4-6 ноября 2024 г., Институт физиологии имени Л.А. Орбели НАН РА организует международную конференцию «Разгадка тайн природы с помощью передовых подходов биовизуализации» (Ереван, Армения)

С 6 по 7 ноября 2024 года Институт языка им. Г. Ачаряна НАН РА организует международную научную конференцию "Изучение диалектного языка в странах СНГ"

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

Публикации в прессе
30/09/2024

Գիտության շաբաթ
gituzh.am
29/09/2024

«Բարձրագույն կրթության և գիտության» մասին օրենքի նախագիծը՝ ԿԳՄՍ նախարարին կից հասարակական խորհրդի նիստի օրակարգում
escs.am
29/09/2024

Բարձրագույն կրթության և գիտության մասին նոր օրենք. Գիտուժի ու գիտական համայնքի արձագանքը
media-center.am
28/09/2024

ԳԱԱ կազմում չեն լինի գիտական կազմակերպություններ, այն կդառնա խորհրդատվական մարմին
1lurer.am
с 01.01.2005г. сайт посещался
7 113 682

раз
National Academy of Sciences of the Republic of Armenia
Логотип НАН РА (черный, синий)
наверх Сайт последний раз обновлялся:  17:00, 04/10/2024 наверх
Главная страница - Об Академии - Отделения - Организации - Члены - Связь с нами - Структура - Члены президиума
Документы - Инновационные предложения - Публикации - Фонды - Конференции - Конкурсы - Международное сотрудничество
Молодежные программы - Фотогалерея - Видеогалерея - Веб ресурсы - Другие академии - Газета "Гитутюн" - Журнал "В мире науки"
Публикации в прессе - Анонсы - Юбилеи - Университеты - Новости - Научные результаты - Отдел диаспоры представляет
Трибуна молодого ученого - Наши заслуженные деятели - Объявления - Карта сайта - COVID-19
© Copyright 1998-2024 Все права защищены.
Сайт создан и поддерживается Академической научно-исследовательской компьютерной сетью Армении (ASNET-AM)
Вопросы и предложения можете посылать на электронный адрес webmaster {[ at ]} sci.am