Պատրաստի նյութեր

Աշխատությունը նվիրված է գրաֆների տեսության շրջանակում համեմատելիության գրաֆների ներկման խնդիրների տեսական ուսումնասիրությանը և դրանց լուծման արդյունավետ ալգորիթմների մշակմանը։ Հետազոտության առանցքում գրաֆի գագաթներին գույների այնպիսի վերագրման խնդիրն է, որի դեպքում հարակից գագաթները ստանում են տարբեր գույներ, իսկ օգտագործվող գույների քանակը հնարավորության դեպքում հասցվում է նվազագույնի։ Հատուկ ուշադրություն է հատկացվում համեմատելիության գրաֆների կառուցվածքային առանձնահատկություններին, որոնք կապված են մասնակի կարգավորված բազմությունների և տրանզիտիվ կողմնորոշումների հետ։ Դիտարկվում են գրաֆի քրոմատիկ թվի որոշման, թույլատրելի ներկումների կառուցման և համապատասխան օպտիմալացման խնդիրները։ Ուսումնասիրվում է, թե գրաֆների տվյալ դասի կառուցվածքային հատկությունների օգտագործումը ինչպես կարող է պարզեցնել ընդհանուր դեպքում հաշվարկային առումով բարդ ներկման խնդիրները և հնարավորություն տալ կառուցելու մասնագիտացված ալգորիթմներ։ Կարևոր տեղ է զբաղեցնում մաթեմատիկական մոդելների և ալգորիթմական մոտեցումների համադրումը, որի միջոցով հնարավոր է սահմանել խնդրի մուտքային տվյալները, սահմանափակումները, նպատակային չափանիշները և լուծման ստացման հաջորդականությունը։ Քննվում են գագաթների ու կողերի ներկայացման տարբեր եղանակները, տրանզիտիվ հարաբերությունների հայտնաբերումը, կառուցվածքային բաղադրիչների առանձնացումը և դրանց օգտագործումը ներկման գործընթացում։ Ալգորիթմների մշակման ընթացքում կարևոր նշանակություն ունի դրանց կոռեկտության հիմնավորումը և հաշվարկային բարդության գնահատումը՝ ժամանակային ու հիշողության ծախսերի տեսանկյունից։ Համեմատական վերլուծությունը հնարավորություն է տալիս ուսումնասիրել տարբեր մոտեցումների արդյունավետությունը և պարզել, թե գրաֆի չափը, խտությունը և կառուցվածքային առանձնահատկությունները ինչպես են ազդում հաշվարկների վրա։ Աշխատանքի շրջանակում կարող են դիտարկվել նաև կատարյալ գրաֆների տեսության հետ առնչությունները, քանի որ համեմատելիության գրաֆները կարևոր տեղ են զբաղեցնում այն դասերի շարքում, որոնց կառուցվածքային հատկությունները թույլ են տալիս մի շարք օպտիմալացման խնդիրներ լուծել ավելի արդյունավետ մեթոդներով։ Նման խնդիրներն ունեն նաև կիրառական նշանակություն՝ ժամանակացույցերի կազմման, ռեսուրսների բաշխման, առաջադրանքների համաձայնեցման և փոխադարձ անհամատեղելիության հարաբերություններով համակարգերի մոդելավորման ոլորտներում։ Ընդհանուր առմամբ հետազոտությունը միավորում է դիսկրետ մաթեմատիկայի, գրաֆների տեսության, կոմբինատորային օպտիմալացման և ալգորիթմների տեսության մոտեցումները՝ նպատակ ունենալով զարգացնել համեմատելիության գրաֆների ներկման խնդիրների լուծման տեսական հիմքերն ու արդյունավետ հաշվարկային մեթոդները։