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

Գրաֆների լոկալ-հավասարակշռված 2-տրոհումների մասին

Բալիկյան, Սուրեն Վարուժանի (2008) Գրաֆների լոկալ-հավասարակշռված 2-տրոհումների մասին. PhD thesis, ԵՊՀ.

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

Download (291Kb) | Preview

    Abstract

    Интерес к задачам о вершинных раскрасках графов возник в XIX веке, когда была сформулирована "гипотеза четырех красок" [1], согласно которой любая карта может быть раскрашена не более чем четырьмя цветами таким образом, чтобы никакие два государства с общей границей не получили бы одинаковый цвет. В переформулировке на языке теории графов "гипотеза четырех красок" утверждает, что хроматическое число [2] любого плоского графа не превосходит 4. До своего полного решения [3,4] задача прошла длительный путь, богатый интересными исследованиями, имеющими методологическое значение, ошибочными доказательствами и важными результатами [5, 6], существенно содействовав систематическому и всестороннему изучению вершинных раскрасок графов. Различные оценки хроматического числа графа получены в [7,8]. Асимптотическое значение хроматического числа для почти всех п-вершинных графов найдено в [9]. МР-полнота некоторых задач о вершинных раскрасках графов установлена в [10, 11]. Для некоторых частных классов графов найдены полиномиальные алгоритмы, позволяющие по данному графу О и натуральному числу к определять, существует ли правильная раскраска вершин О в к цветов [7, 12, 13]. Задачи о правильных вершинных раскрасках графов, кроме своего теоретического значения, имеют еще и большую практическую ценность, поскольку они связаны с задачами составления оптимальных расписаний, минимизации памяти программ, минимизации числа процессоров в распределенных параллельных вычислениях и т.д. [14,15]. По мере развития исследований правильных вершинных раскрасок графов и выявления их взаимосвязей с прикладными задачами из различных областей значительного внимания удостоились также и задачи о существовании и построении вершинных раскрасок специальных видов [16]. Как правило, характеристики условий таких раскрасок бывают связаны со специфическими особенностями соответствующих прикладных задач и могут быть обусловлены природой ресурсов, технологическими требованиями, особыми условиями труда, необходимостью обеспечения информационной или военной безопасности и т.д. Գրաֆների գագաթային ներկումները ունեն ինչպես մեծ տեսական արժեք, այնպես էլ կարևոր կիրառական նշանակություն, քանի որ դրանք սերտորեն կապված են այնպիսի խնդիրների հետ, ինչպիսիք են օպտիմալ կարգացուցակների կառուցումը, ծրագրերի աշխատանքի համար անհրաժեշտ հիշողության մինիմիզացումը, զուգահեռ հաշվարկներում օգտագործվող պրոցեսորների քանակի մինիմիզացումը և այլն: Ճիշտ գագաթային ներկումների ուսումնասիրությունների զարգացման ընթացքում ուշադրության արժանացան նաև հատուկ տեսակների գագաթային ներկումների գոյության և կառուցման խնդիրրները: Ատենախոսությունում դիտարկվող խնդիրները, մշակված մեթոդները, ալգորիթմները և ստացված արդյունքները կարող են կիրառվել այնպիսի համակարգերի մաթեմատիկական մոդելավորման համար, որոնց սուբյեկտները ենթակա են երկու հակադիր ազդեցությունների և պահանջվում է նվազեցվել կոնֆլիկտների հավանականությունը: Ապացուցված է երկկողմանի գրաֆների լոկալ-հավասարակշռվածi 2-տրոհումների, i∈{1,2}, գոյության խնդիրների NP-լրիվությունը, ցիկլերի կառուցվածքի վրա դրված որոշ սահմանափակումների ներքո ստացված է անհրաժեշտ և բավարար պայման երկկողմանի գրաֆի լոկալ-հավասարակշռված1 2-տրոհման գոյության համար, ծառի համար ստացված է անհրաժեշտ և բավարար պայման լոկալ-հավասարակշռված2 2-տրոհման գոյության համար, ծառի համար ստացված է տրված մասնակի 2-տրոհման ընդլայնում հանդիսացող լոկալ-հավասարակշռված1 2-տրոհման գոյության անհրաժեշտ և բավարար պայման:

    Item Type: Thesis (PhD)
    Additional Information: Գրաֆների լոկալ-հավասարակշռված 2-տրոհումների մասին: On locally-balanced 2-partitions of graphs.
    Uncontrolled Keywords: Բալիկյան Սուրեն Վարուժանի, Balikyan Suren V.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 15 Mar 2017 13:10
    Last Modified: 15 Mar 2017 13:10
    URI: http://etd.asj-oa.am/id/eprint/4274

    Actions (login required)

    View Item