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

Раскраски ерафов с локальными условиями

Камалян, Рафаел Рубенович (2016) Раскраски ерафов с локальными условиями. Doctor of Sciences thesis, ЕГУ.

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

Download (631Kb) | Preview

    Abstract

    Исследования задач о хроматическом числе и хрома¬тическом классе графа , сформулированных в связи с изучением вопросов прикладного характера, пройдя длинный исторический путь от определений раскрасок до оценок значений этих параметров, значительно обогатили теорию графов ценными теоремами, идеями, методами доказательств, новыми гипотезами и задачами, конструктивными алгоритмами раскрасок. После введения классов Р , ЫР и понятия ЫР -полной задачи были получены результаты, выявившие сложность задач о хроматическом числе и хроматическом классе даже для сравнительно узких классов графов и указавшие на принципиальные трудности в развитии классических подходов. Параллельно, в связи с растущей потребностью построения адекватных математических моделей все более усложняющихся задач различных сфер практики ֊ с одной стороны, и, в связи с обнаружившимися сложностями преодоления затруднений приближенными и вероятностными алгоритмами, - с другой, заметно возрастала необходимость исследований неклассических задач раскрасок графов. Видное место в этом направлении принадлежит таким раскраскам (реберным, вершинным) графов, в которых на множество цветов, используемых в окрестности (реберной, вершинной) вершины, налагается некоторое локальное условие X. Такие условия, как правило, отражают специфические особенности моде-лируемых прикладных задач и бывают связаны с природой ресурсов, техноло-гическими требованиями, особыми условиями труда, необходимостью приори-тетного выполнения некоторых заказов, желательностью равномерного рас-пределения противоборствующих влияний в системах, подверженных опаснос¬ти возникновения конфликтов и т.д.. При этом количественные ограничения чаще всего объясняются соответствующими ограничениями в реальных процес¬сах (необходимость экономии природного ресурса, ограниченное число испол¬нителей, малая производительность труда, завершение выполнения заказа к ус¬тановленному сроку и т.д.). Качественные ограничения происходят из особен¬ностей технологических процессов, условий труда и отдыха (непрерывность производственных процессов, учет индивидуальных пожеланий исполнителей и т.д.). Отметим, что многочисленные ограничения в реальных задачах заметно осложняют их исследование традиционными методами, какими являются, на-пример, методы линейного программирования, потоки в сетях и т.д. Ատենախոսությունում հետազոտվում են գրաֆների այնպիսի ներկումներ (կողային, գագաթային), որոնցում գրաֆի գագաթների շրջակայքերի (կողային, գագաթային) վրա դրվում է որևէ լոկալ X պայման: Հինգ տարբեր X -ների համար դիտարկված են գրաֆների X պայմանին բավարարող, ներկումների գոյության, կառուցման, կառուցվածքների ուսումնասիրման և թվային պարամետրերի գնահատման խնդիրներ: X (X ) պայմանը դրվում է գրաֆի գագաթի կողային շրջակայքի վրա, և պահանջում է, որպեսզի կողային ճիշտ ներկման մեջ գագաթի շրջակայքում օգտագործվող գույները կազմեն միջակայք (1-ից սկսվող միջակայք) բնական թվերի բազմության մեջ: X պայմանը նույնպես դրվում է գրաֆի գագաթի կողային շրջակայքի վրա, և պահանջում է, որպեսզի կողային ճիշտ ներկման մեջ գագաթի շրջակայքում օգտագործվող գույները կազմեն միջակայք, եթե ներկման մեջ մասնակցող բոլոր գույները ենթադրվում են դասավորված շրջանագծի վրա: X ( X ) պայմանը դրվում է գրաֆի գագաթի գագաթային շրջակայքի (գագաթի գագաթային ընդլայնված շրջակայքի, երբ գագաթը համարվում է իր շրջակայքին պատկանող) վրա, և պահանջում է, որպեսզի գագաթների երկգույնանի ներկման մեջ գագաթի շրջակայքում տարբեր գույների գագաթների թվերը տարբերվեն ոչ ավել, քան 1-ով: X պայմանի (Xe{X,XX}) և կամայական բնական է -ի համար N (-ով նշանակենք այն գրաֆների բազմությունը, որոնց համար գոյություն ունի գրաֆի կողային ճիշտ ներկում 1 գույներով, որը բավարարում է X պայմանին, և, դիցուք, 91ձ = Օ գրաֆի ւ> 1 համար նշանակենք ©^ (ի?) = 6 N / Ծ 6 9Հ,,} : Ատենախոսության հիմնական նպատակն է տարբեր դասերի գրաֆների համար հետազոտել դրանց գագաթների շրջակայքերի (կողային, գագաթային) վրա դրված տարբեր լոկալ X պայմաններին բավարարող ներկումների գոյության, կառուցման, կառուցվածքների ուսումնասիրման և թվային պարամետրերի գնահատման խնդիրներ: Ուսումնասիրվող հիմնական խնդիրներն են` Տրված են Օ գրաֆը և X պայմանը: Պարզել, Օ տ N թե ոչ, Տրված է Օ տ N գրաֆը : Գտնել ©X (Օ) բազմությունը: Graph colorings (edge,vertex) are investigated with some local condition X which is put on neighbourhoods (edge, vertex) of vertices. For five different X , prob¬lems of the existence, construction, structure investigations and estimations of numeric parameters of graph colorings satisfying such X are considered. The condition X (X) is applied in proper edge colorings, is put on the edge neighbourhood of a vertex of the graph, and requires that colors used for edges incident to any vertex of the graph to form an interval (interval beginning from 1) of integers. The condition X is applied in proper edge colorings, is put on the edge neighbourhood of a vertex of the graph, and requires that colors used for edges incident to any vertex of the graph to form an interval when all colors are supposed to be arranged on a circle. The condition X (X) is applied in bicolor vertex colorings, is put on the vertex neighbourhood (extended vertex neighbourhood in which the vertex itself is also included) of a vertex of the graph, and requires that the numbers of different colors used in the neighbourhood of any vertex of the graph to differ from each other by at most 1. For a condition X( Xe{\,X,X}) and an arbitrary positive integer t, NAI denotes the set of graphs for which there exists a proper edge coloring with colors 1,...,t satisfying the condition X, and let f°r a graph G, let />1 0, (G)S{(€N/GE»4 The aim of the dissertation is the investigation of the problem of existence, construction, structure and estimation of numerical parameters of colorings for various local conditions X that are imposed for (edge, vertex) neighborhoods of the vertices of some graphs. The main investigated problems are following: for a given graph G and condition X , determine whether G e N or not; for a given graph G e N, find the set ®A (G).

    Item Type: Thesis (Doctor of Sciences)
    Additional Information: Գրաֆների ներկումներ լոկալ պայմաններով:
    Uncontrolled Keywords: Քամալյան Ռաֆայել Ռուբենի, Kamalian R.R.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 10 Mar 2017 10:13
    Last Modified: 17 May 2018 10:31
    URI: http://etd.asj-oa.am/id/eprint/4257

    Actions (login required)

    View Item