Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Համեմատությունների գրաֆների ներկման խնդիրների հետազոտում և ալգորիթմների մշակում

Ադամյան, Ռուբեն Օհանի (2008) Համեմատությունների գրաֆների ներկման խնդիրների հետազոտում և ալգորիթմների մշակում. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (271Kb) | Preview

    Abstract

    Գրաֆների ներկման և գրաֆում ամենամեծ անկախ բազմություն գտնելու խնդիրները դիսկրետ մաթեմատիկայի ամենաշատ ուսումնասիրված խնդիրներից են: Սա պայմանավորված է նրանց սերտ կապով բազմաթիվ կիրառական խնդիրների հետ: Մասնավորապես կարգավորումների տեսության մեջ տրված աշխատանքները նվազագույն քանակի աշխատողներով կատարելու կամ տրված քանակի աշխատողներով տրված աշխատանքներից առավելագույն քանակով աշխատանքները կատարելու խնդիրները, գերմեծ ինտեգրալային սխեմաների ֆիզիկական նախագծման մեջ տրված շղթաներն ուղեգծելու համար անհրաժեշտ ամենափոքր տարածքը գտնելու կամ տրված տարածքում տրված շղթաներից հնարավորինս ամենաշատն ուղեգծելու խնդիրները, ծրագրի արդյունավետ աշխատանքի համար պրոցեսորի ռեգիստրների անհրաժեշտ նվազագույն քանակը գտնելու կամ ռեգիստրների տրված քանակր հնարավորինս արդյունավետ օգտագործելու խնդիրները բերվում հն ներկման խնդիրներին: Գրաֆի մինիմալ ներկում և գրաֆում ամենամեծ անկախ բազմություն գտնելու խնդիրները հայտնի և բավականաչափ լավ ուսումնասիրված NP-դժվար խնդիրներ են: Այս խնդիրների համար նաև ուսումնասիրված է նրանց համար լավ մոտավոր ալգորիթմների գոյության հարցը և ապացուցված է, որ նրանց համար կամայական ֆիքսված շեղման գնահատական ունեցող մոտավոր ալգորիթմներ գտնելը նույնպես NP-դժվար է: Գրաֆի ամենամեծ q-ներկելի ենթագրաֆ գտնելու խնդրում պահանջվում է այդ գրաֆում գտնել առավելագույն քանակով գագաթներ պարունակող ենթագրաֆ, որը q-ներկելի է: Այս խնդիրը հանդիսանում է գրաֆի ամենամեծ անկախ բազմություն (q = 1) և մինիմալ ներկում (q = x(G), որտեղ x(G)-h G գրաֆի ներկման թիվն է) գտնելու խնդիրների րնդհանրացումր: ՈՒստի այն q = 1 և q = x(G) դեպքերում NP-դժվար է: Լևիսի և Յանակակիսի կողմից ապացուցված է, որ այն NP-դժվար է նաև q-ի բոլոր q = 1, 2,... , x(G) արժեքների համար: Հայտնի է, որ ամենամեծ q-ներկելի ենթագրաֆ գտնելու խնդիրը հեշտությամբ բերվում է ամենամեծ անկախ բազմություն գտնելու խնդրին և հակառակր: Диссертационная работа посвящена изучению задач q-раскраски графов сравнения и построению точных и приближенных алгоритмов для нахождения максимального q-хроматического подграфа. Задачи раскраски графов одни из самых изученных задач дискретной математики. В задаче нахождения максимального q-хроматического подграфа требуется найти q-раскрашиваемый подграф, содержащий наибольшее возможное количество вершин. Эта задача является обобщением задач нахождения наибольшего независимого множества и минимальной раскраски графа. В диссертации также изучена проблема мощности минимального трансверсаля множества наибольших независимых множеств графа сравнения. Построен более эффективный алгоритм для нахождения максимального q-хроматического подграфа в графе сравнения при q = ш — 2, где ш - число вершин наибольшего полного подграфа. Построен обобщенный жадный алгоритм для нахождения максимального q-хроматического подграфа и найдено его отклонение от оптимального алгоритма. Улучшена оценка отклонения обычного жадного алгоритма для той же задачи q-раскраски. Доказано равенство чисел трансверсальности и независимости множества наибольших независимых множеств графа сравнения. Предложен алгоритм для нахождения минимального трансверсаля множества наибольших независимых множеств графа сравнения.

    Item Type: Thesis (PhD)
    Additional Information: Исследование задач и разработка алгоритмов расскраски графов сравнения. Study and construction of coloring algorithms for comparability graphs.
    Uncontrolled Keywords: Адамян Рубен Оганович, Adamyan Ruben
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 10 Mar 2017 10:34
    Last Modified: 13 Mar 2017 09:33
    URI: http://etd.asj-oa.am/id/eprint/4258

    Actions (login required)

    View Item