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

Որոշ դասերի գրաֆների ճիշտ կողային ներկումների բազմության մեջ միջակայքային սպեկտրով գագաթների թվի էքստրեմալ արժեքների մասին

Դավթյան, Նարինե Նվերի (2015) Որոշ դասերի գրաֆների ճիշտ կողային ներկումների բազմության մեջ միջակայքային սպեկտրով գագաթների թվի էքստրեմալ արժեքների մասին. PhD thesis, ԵՊՀ.

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

Download (949Kb) | Preview

    Abstract

    Исследования задач об интервальных реберных раскрасках графов ведутся, в основном, в направлениях вопросов их существования и построения, а также нахождения нижних и верхних оценок возможного числа цветов в таких раскрасках. Известно, что интерес к интервальным реберным раскраскам графов обусловлен как их теоретическим значением (достаточно отметить, что в случае кубического графа задача о существовании интервальной реберной раскраски эквивалентна задаче определения хроматического класса), так и возможностью их использования при математическом моделировании задач существования и построения расписаний непрерывных производственных процессов, в частности, составления "безоконных" учебных расписаний и организации функционирования систем беспроводной связи. В работе рассматриваются конечные неориентированные графы О без кратных ребер и петель, для множеств вершин и ребер которых употребляются, соответственно, обозначения V(О) и Е(О). Непустое конечное подмножество последовательных натуральных чисел называется интервалом. Мощность произвольного конечного множества А обозначается через |А|. Правильной реберной граскраской графа О называется функция ф : Е(О) ^ (1,...,г}, при которой для любой пары в' и в" смеж¬ных ребер их цвета ф(в') и ф(в'') различны, и для любого цвета I, 1 < I < г, существует хотя бы одно ребро цвета I. Наименьшее значение г, при котором существует правильная реберная г-раскраска графа О, обозначается через х'(О). Множество всех правильных реберных г-раскрасок графа О обозначается через а(О,г), и пусть а(О) = и _х(О. а(О,г). Если О – граф, х Е V(О), ф Е а(О), то множество цветов, используемых в раскраске ф для ребер, смежных вершине х, называется спектром вершины х графа О при раскраске ф и обозначается через 8о(х,ф), а число вершин, спектр которых является интервалом, обозначается через /о(ф). ф Е а(О) называется интервальной реберной раскраской графа О, если /О(ф) _ IV(О)|. Множество графов, для которых существует интервальная реберная раскраска, обозначается через N. Ատենախոսությունում դիտարկվում են չկողմնորոշված G գրաֆներ առանց պատիկ կողերի և օղերի' գագաթների V(G) և կողերի E(G) բազմություններով: G գրաֆի' 1,2,...,t գույներով իրականացվող բոլոր ճիշտ կողային ներկումների բազմությունը նշանակենք a(G,t) -ով, G -ի քրոմատիկ դասը նշանակենք X'(G) -ով, և, դիցուք, a(G) = (^a>a(G,t): Հաջորդական ամբողջ թվերի կամայական ոչ դատարկ վերջավոր ենթաբազմությունն անվանում ենք միջակայք: Եթե G -ն գրաֆ է, x e V(G), pea(G), ապա այն գույների բազմությունը, որոնք p-ում օգտագործված են x գագաթին կից կողերի համար, անվանում ենք G -ի x գագաթի սպեկտր p ներկման մեջ: G -ի այն գագաթների թիվը, որոնց սպեկտրը միջակայք է, նշանակում ենք fG (p) -ով, և p-ն անվանում ենք G -ի միջակայքային կողային ներկում, եթե fG(p) = |V(G)| : Միջակայքային կողային ներկում ունեցող գրաֆների դասը նշանակում ենք N -ով: Հայտնի է, որ գրաֆների առավել կարևոր դասերի (խորանարդ, երկկողմանի և այլն) համար գրաֆի N դասին պատկանելիության խնդիրը NP -լրիվ է: Դրա հետ կապված կարևոր է դառնում a(G) բազմության վրա fG (p) ֆունկցիայի հատկությունների, մասնավորապես, նրա էքստրեմալ հատկությունների ուսումնասիրումը: G գրաֆի և t թվի համար, որտեղ X'(G) < t < |E(G)|, սահմանենք. M0,t) = mn fG(p), թ2(G,t) = max fG(p): pea(G,t) pea(G,t) G գրաֆի համար սահմանենք. u,,(G) = min u,(G,t), u,2(G) = max u,(G,t), I'(G)St<|E(G)r1V X (G)<t<\E(G)| 2 u2,(G) = min u2(G,t), u22(G) = max u2(G,t): X(G)<t <\E (G)G^ 22 X(G)<t <\E (G)~2K M11(G) , M12(G), M21(G), M22(G) պարամետրերը հանդիսանում են a(G,t) բազմության վրա միջակայքային սպեկտրով գագաթների թվի էքստրեմումևերի սահմաններ, երբ գույների է քանակը փոփոխվում է G գրաֆի քրոմատիկ դասի և կողերի քանակի միջև: In the dissertation finite simple undirected graphs G without multiple edges and loops are considered, with the set V(G) of vertices and the set E(G) of edges. The set of all proper edge colorings of G with colors 1,2,...,t is denoted by a(G,t), the chromatic index of G is denoted by x'(G), and let «(G) — Ut^V^, t). An arbitrary nonempty finite subset of consecutive integers is called an interval. If G is a graph, x eV(G), y e a(G), then the set of colors used by y for edges incident to x is called a spectrum of the vertex x of the graph G at y; the number of vertices of G with an interval spectrum is denoted by fG (y). y e a(G) is called an interval edge coloring of the graph G , if fG(y) = |V(G)| . The set of all graphs having an interval edge coloring is denoted by N . It’s known that for graphs G of the most important classes (cubic, bipartite and so on), having both theoretical and practical significanse, the problem of deciding whether G belongs to N or not is NP -complete. Due to it the problem of investigations of properties, particularly extremal properties, of the function fG (y) on the set a(G) becomes important. For a graph G and t e N , x'(G) < t < |E(G)|, set: Mշ(G,t) = max fG(y). yea(G,t) u,2(G) — max ii(G,t), l'(G)<t <|E (G)|r u22(G) — max u2(G,t). l'(G)<t <|E (G)|r The parameters H11(G) , H12(G), H21(G) and H22(G) are boundaries of extrema of the number of vertices with an interval spectrum on the set a(G, t) under variation of the number t of colors between the chromatic index and the number of edges of G.

    Item Type: Thesis (PhD)
    Additional Information: Որոշ դասերի գրաֆների ճիշտ կողային ներկումների բազմության մեջ միջակայքային սպեկտրով գագաթների թվի էքստրեմալ արժեքների մասին: On boundaries of extrema of the number of vertices with an interval spectrum on the sets of proper edge colorings of some classes of graphs.
    Uncontrolled Keywords: Դավթյան Նարինե Նվերի, Davtyan N. N.
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 13 Mar 2017 09:55
    Last Modified: 14 Mar 2017 11:21
    URI: http://etd.asj-oa.am/id/eprint/4262

    Actions (login required)

    View Item