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

Գրաֆների միջակայքային կողային ներկումների հետազոտում

Խաչատրյան, Հրանտ Հարությունի (2017) Գրաֆների միջակայքային կողային ներկումների հետազոտում. PhD thesis, ԵՊՀ.

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

Download (2085Kb)
    [img] PDF (Abstract)
    Available under License Creative Commons Attribution.

    Download (273Kb)

      Abstract

      Դիսկրետ մաթեմատիկայում մեծ ուշադրություն է հատկացվում ներկումների խնդիրների հետազոտություններին: Պատմականորեն ներկումների հանդեպ հետաքրքրությունը պայմանավորված էր «Չորս գույների հիպոթեզ» հանրահայտ խնդրով, համաձայն որի ամեն մի աշխարհագրական քարտեզ հնարավոր է ներկել չորս գույների միջոցով այնպես, որ յուրաքանչյուր երկրի տարածք ներկված լինի մեկ գույնով, իսկ ընդհանուր սահման ունեցող երկրները ներկված լինեն տարբեր գույներով: Դիսկրետ մաթեմատիկայի հետագա զարգացումը ցույց տվեց, որ դա պայմանավորված է ինչպես ներկումների խնդիրների՝ մի շարք կարևոր կիրառական խնդիրների հետ առկա սերտ կապով, այնպես էլ նրանով, որ դիսկրետ մաթեմատիկայում առկա են բազմաթիվ խնդիրներ, որոնք կարելի է ձևակերպել որպես ներկումների խնդիրներ (ֆակտորիզացիայի խնդիրներ, տրոհման խնդիրներ, Ռամսեյի տեսության խնդիրներ և այլն): Մասնավորապես, նշանակալի փոխադարձ կապ կա կարգացուցակների տեսության խնդիրների և գրաֆների ներկումների խնդիրների միջև: Օրինակ, քննաշրջանի օպտիմալ կարգացուցակ կառուցել ٳ խնդիրը բերվում է գրաֆի քրոմատիկ թվի որոշմանը: Գրաֆի քրոմատիկ դասը գտնելու խնդրին բերվում է սպորտային մրցումների կարգացուցակ կազմելու խնդիրը: Կարգացուցակների տեսության բազմաթիվ խնդիրներ կարելի է բերել ոչ միայն գրաֆների դասական ներկումների խնդիրներին, այլև լրացուցիչ պայմաններով ճիշտ գագաթային և կողային ներկումների գոյության ու կառուցման խնդիրներին:Կիրառական խնդիրների մոդելավորման ժամանակ հաճախ հետազոտման օբյեկտներ են հանդիսանում ոչ միայն հասարակ գրաֆները, այլև մուլտիգրաֆները: Այսպես, օրինակ, ուսումնական դասացուցակների կառուցման խնդիրներում հաճախ առաջանում են իրավիճակներ, երբ ուսուցիչը միևնույն խմբի հետ անցկացնում է մեկից ավելի դասաժամ: Միջակայքային կողային ներկումներին նվիրված հետազոտությունները վերջին երեք տասնամյակներում հիմնականում վերաբերում էին պատիկ կողեր չպարունակող գրաֆներին, մինչդեռ մուլտիգրաֆները մնում են քիչ հետազոտված: Մյուս կողմից՝ վերոհիշյալ աշխատանքներում հիմնականում ուսումնասիրվել են միջակայքային ներկումների գոյության և կառուցման խնդիրները, սակայն քիչ է անդրադարձ կատարվել ներկումների թվային պարամետրերի գնահատման հարցերին: Միջակայքային ներկումների հետազոտություններում անարդարացիորեն քիչ է ուշադրություն հատկացված այդպիսի ներկումների կայունության հարցերին տարբեր գրաֆային գործողությունների նկատմամբ, ինչպիսիք են, օրինակ, գրաֆների գումարումը, դեկարտյան արտադրյալը, գրաֆից գագաթների, կողերի կամ զուգակցումների հեռացումը, կողերի տրոհումը և այլն: Նման դրվածքով խնդիրների կարևորությունը հատկապես մեծ է այնպիսի համակարգերի մոդելավորման դեպքում, որոնցում ժամանակի ազդեցության տակ կարող են կատարվել նկարագրող գրաֆի (մուլտիգրաֆի) չնախատեսված փոփոխություններ: Многие задачи составления расписаний сводятся к реберным раскраскам графов с различными ограничениями. В частности, задачи существования и построения расписаний без “окон” моделируются с помощью интервальных реберных раскрасок графов и мультиграфов. Настоящая диссертация посвящена исследованию интервальных реберных раскрасок и их обобщений.В диссертационной работе рассматриваются конечные неориентированные графы без кратныx ребер и петель, а также мультиграфы, которые допускают наличие кратных ребер.В настоящей работе исследованы задачи существования, построения и оценки числовыx параметров интервальныx реберных раскрасок различных классов мультиграфов, а также задачи устойчивости интервальных реберных раскрасок относительно некоторых графовых операций.Частичное решение проблемы Дженсена и Тофта о наименьшем интервально не раскрашиваемом двудольном графе, построение наименьших известных таких графов, а также интервальная раскрашиваемость всех двудольных графов с числом вершин не превосходящим 16. Many important problems in scheduling theory are reduced to edge colorings of graphs with various restrictions. In particular, the problems of existence and construction of school timetables without gaps are modeled using interval edge-colorings of graphs and multigraphs. This dissertation is devoted to investigation of such colorings and their generalizations.We consider finite undirected graphs without loops and multiple edges, and multigraphs, which can have multiple edges.In the dissertation we consider the problems of the existence, construction and estimation of numerical parameters of interval edge-colorings for various classes of multigraphs, as well as the problems of stability of interval edge-colorings under some operations.A partial solution is given to the problem by Jensen and Toſt on the smallest interval noncolorable bipartite graphs, the smallest known examples of such graphs are constructed, and it is shown that all bipartite graphs having at most 16 vertices are interval colorable.

      Item Type: Thesis (PhD)
      Additional Information: Исследование интервальных реберных раскрасок графов.
      Uncontrolled Keywords: Xaчатрян Грант Арутюнович
      Subjects: Mathematics and Cybernetics
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 01 Sep 2017 16:06
      Last Modified: 01 Sep 2017 16:06
      URI: http://etd.asj-oa.am/id/eprint/5532

      Actions (login required)

      View Item