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

Գրաֆների միջակայքային տոտալ ներկումներ

Խաչատրյան, Ներսես Արմենի (2016) Գրաֆների միջակայքային տոտալ ներկումներ. PhD thesis, ԵՊՀ.

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

Download (6Mb) | Preview
    [img]
    Preview
    PDF (Abstract)
    Available under License Creative Commons Attribution.

    Download (2934Kb) | Preview

      Abstract

      Ներկումների խնդիրները հանդիսանում են դիսկրետ մաթեմատիկայի հայտնի և արդի հետազոտման թեմաներից մեկը: Այդ խնդիրների կարևորությունը պայմանավորված է առկա սերտ կապով մի շարք կարևոր կիրառական խնդիրների հետ: Մասնավորապես, նշանակալի փոխադարձ կապ կա կարգացուցակների տեսության խնդիրների և գրաֆների ներկումների խնդիրների միջև: Օրինակ, քննաշրջանի օպտիմալ կարգացուցակ կառուցելու խնդիրը բերվում է գրաֆի քրոմատիկ թվի որոշմանը: Գրաֆի քրոմատիկ դասը գտնելու խնդրին բերվում է սպորտային մրցումների կարգացուցակ կազմելու խնդիրը, իսկ երկկողմանի գրաֆների հատուկ տիպի կողային ներկումների խնդիրները բազմաթիվ աշխատանքներում ծառայել են որպես ուսումնական դասացուցակների գոյության, կառուցման և թվային պարամետրերի գնահատման հարցերի հետազոտման մոդելներ: Գրաֆների տոտալ ներկումները ներմուծվել են Վ. Վիզինգի [27] և Մ. Բեհզադի [4] կողմից 60 -ական թվականներին: Գրաֆի տոտալ ներկումն այդ գրաֆի գագաթների և կողերի ներկում է, որի դեպքում հարևան գագաթները, կողերը, ինչպես նաև կից գագաթները և կողերը ներկվում են տարբեր գույներով: գրաֆի տոտալ քրոմատիկ թիվը գույների այն նվազագույն քանակն է, որն անհրաժեշտ է գրաֆի տոտալ ներկման համար: Նշենք նաև, որ [4, 27]-ում առաջարկվել է հիպոթեզ, համաձայն որի բոլոր գրաֆների համար, որտեղ ն գրաֆի գագաթների առավելագույն աստիճանն է: Այս հիպոթեզն այժմ հայտնի է որպես Տոտալ Ներկումների Հիպոթեզ [12]: Հայտնի է նաև, որ այն ճիշտ է լրիվ գրաֆների [5], երկկողմանի գրաֆների, լրիվ կողմանի գրաֆների [10, 24], տրոհվող գրաֆների [9], հարթ գրաֆների, որոնց [6, 7, 15, 25, 28], գրաֆների, որոնց [11], որտեղ ն գրաֆի գագաթների նվազագույն աստիճանն է, և գրաֆների, որոնց առավելագույն աստիճանը բավականին փոքր է: Մ. Ռոզենֆելդի [24] և Ն. Վիժայադիտյայի [26] կողմից ապացուցվել է, որ գրաֆի տոտալ քրոմատիկ թիվը չի գերազանցում 5 - ի, երբ : Ա. Կոստոչկան [13, 14] աշխատանքներում ապացուցել է, որ գրաֆի տոտալ քրոմատիկ թիվը չի գերազանցում 6 - ի (7 - ի), երբ ( ): Գրաֆների տոտալ քրոմատիկ թվի ընդհանուր գնահատականը տրվել է Մոլլոյի և Ռիդի [16] կողմից, որոնք ապացուցել են, որ բոլոր գրաֆների համար: Նշենք նաև, որ տոտալ քրոմատիկ թվի ճշգրիտ արժեքը հայտնի է միայն պարզ շղթաների, պարզ ցիկլերի, լրիվ և լրիվ երկկողմանի, չափանի խորանարդի [5, 30], լրիվ կողմանի գրաֆների համար, որոնց գագաթների քանակը կենտ է [10] և հարթ գրաֆների համար, որոնց [6, 7, 15, 25, 28]: Դասացուցակների տեսության մեջ կարևոր տեղ են զբաղեցնում պատուհան չունեցող դասացուցակների գոյության և կառուցման խնդիրները: Նշված խնդիրների հետազոտման նպատակով Ա. Ս. Հասրաթյանի և Ռ. Ռ. Քամալյանի կողմից ներմուծվել է միջակայքային կողային ներկման սահմանումը [1]: Սակայն, պետք է նշել, որ նույնիսկ երկկողմանի գրաֆների դեպքում այդ ներկման գոյության խնդիրը հանդիսանում է լրիվ խնդիր: Նշված փաստը, ինչպես նաև իրական խնդիրներում առաջացող սահմանափակումները կարևոր են դարձնում միջակայքային կողային ներկումներին «մոտ» ներկումների ուսումնասիրությունը: Վերոնշյալ կողային ներկումների հետազոտման նպատակով Պ. Ա. Պետրոսյանի և Հ. Զ. Առաքելյանի կողմից ներմուծվել է միջակայքային ներկման հասկացությունը [19,20], որով, ըստ էության, ներկայացվում է ոչ ավել քան մեկ պատուհան ունեցող միջակայքային կողային ներկման գաղափարը: Միջակայքային կողային ներկումներին «մոտ» ներկումների մեկ այլ տարբերակ են հանդիսանում գրաֆների միջակայքային տոտալ ներկումները [17]: Այս ներկումները սինթեզում են միջակայքային կողային և գրաֆների տոտալ ներկումները: [17, 18, 23] - ում Պ. Ա. Պետրոսյանի կողմից հետազոտվել են որոշ գրաֆների միջակայքային տոտալ ներկումների գոյության և կառուցման հարցեր: [21] - ում հետազոտվել են ծառերի միջակայքային տոտալ ներկումները, իսկ [21, 22] - ում ցույց է տրվել, որ համասեռ, ենթախորանարդ, երկհամասեռ, երկակի ուռուցիկ և որոշ աստիճան ունեցող երկկողմանի գրաֆներն ունեն միջակայքային տոտալ ներկում: Նշենք նաև, որ ոչ բոլոր գրաֆներն ունեն միջակայքային տոտալ ներկում [21]: Սակայն, վերոնշյալ արդյունքները հիմնականում վերաբերվում են գրաֆների միջակայքային տոտալ ներկումների գոյությանը: Ընդհանուր առմամբ, քիչ են հետազոտված գրաֆների միջակայքային տոտալ ներկումների կառուցման և պարամետրերի գնահատման խնդիրները: In the dissertation finite, undirected graphs without loops and multiple edges are considered. Let and denote the sets of vertices and edges of , respectively. A proper edge -coloring of a graph is a mapping such that all colors are used, and for every pair of adjacent edges If is a proper edge-coloring of a graph and , then denotes the set of colors appearing on edges incident to. A total -coloring of a graph is a mapping such that all colors are used, and no adjacent vertices, edges, and no incident vertices and edges obtain the same color. The total chromatic number of a graph is the smallest number of colors needed for a total coloring of If is a total coloring of a graph and , then define a set as follows: A total -coloring of a graph is called an interval total -coloring of a graph if for any , the set is an interval of integers. For let denote the set of graphs which have an interval total -coloring, and let: For a graph the least and the greatest values of for which are denoted by and respectively. In this work the problems of existence, construction and estimating the numerical parameters of interval total colorings of graphs were investigated. In particular, the following results were obtained: general bounds on the parameters and for graphs which have an interval total coloring; sharp lower and upper bounds for the parameters and of complete balanced multipartite graphs; the set of all possible number of colors in interval total colorings of dimensional cubes, fans and wheels; 4sharp lower and upper bounds for the parameters and of block graphs; general bounds on the numerical parameters of interval total colorings of cartesian products of graphs; the exact value of the parameter for the planar Cartesian product some methods for constructing of graphs that have no interval total colorings. В диссертационной работе рассматриваются конечные неориентированные графы без кратныx ребер и петель. Пусть - множество вершин графа а - множество ребер графа Функция называется правильной реберной -раскраской графа если смежные ребра окрашены в различные цвета, и каждый из цветов использован. Если правильная реберная раскраска графа and то через обозначим множество цветов ребер, инцидентных Функция называется тотальной -раскраской графа если смежные вершины, смежные ребра и вершины, инцидентные ребрам, окрашены в различные цвета. Тотальным xроматическим числом графа называется минимальное число цветов, которое необxодимо для тотальной раскраски графа Если тотальная раскраска графа and то через обозначим множество Тотальная -раскраска графа называется интервальной тотальной -раскраской графа если для каждой вершины - интервал натуральныx чисел. Для обозначим через множество графов, обладающиx интервальной тотальной -раскраской, и положим: Для графа обозначим через и соответственно, наименьшее и наибольшее , для которого имеет интервальную тотальную -раскраску. В настоящей работе исследованы задачи существовния, построения и оценки числовыx параметров интервальныx тотальныx раскрасок графов. В частности, получены следующие результаты: Общие оценки параметров и графов обладающиx интервальной тотальной раскраской; достижимые нижние и верxние оценки параметров и полныx многодольныx сбалансированныx графов; множество всеx возможныx количеств цветов в интервальныx тотальныx раскраскаx мерного куба, вееров и колес Татта, достижимые нижние и верxние оценки параметров и графов блоков; общие оценки числовыx параметров интервальныx тотальныx раскрасок декартовыx произведений графов; точное значение параметра планарного декартового произведения некоторые методы построения графов, не обладающиx интервальной тотальной раскраской.

      Item Type: Thesis (PhD)
      Additional Information: Интервальные тотальные раскраски графов. Interval total colorings of graphs.
      Uncontrolled Keywords: Хачатрянн Н. А., Khachatryan N. A.
      Subjects: Mathematics and Cybernetics
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 06 Sep 2016 19:22
      Last Modified: 07 Sep 2016 12:21
      URI: http://etd.asj-oa.am/id/eprint/3367

      Actions (login required)

      View Item