Ամսագրի կամ հրապարակման վերնագիր:

«Կաճառ» Գիտական հոդվածների ժողովածու. ՀՀ ԳԱԱ Գիտակրթական միջազգային կենտրոն = ״Качар״ Сборник научных трудов. НАН РА Международный научно-образовательный центр =“Katchar” Collection of Scientific Articles. International Scientific-Educational Center NAS RA

Հրապարակման ամսաթիվ:

2022

Համար:

2

ISSN:

2579-2903

Պաշտոնական URL:

սեղմիր այստեղ կապին հետևելու համար

Լրացուցիչ տեղեկություն:

Պետրոսյան Պետրոս,Պետրոսյան Տիգրան, Петросян Петрос, Петросян Тигран

Այլ վերնագիր:

Որոշ լրիվ բազմակողմանի գրաֆների գագաթ-տարբերակող կողային ներկումներ ; Вершинно-различающие рёберные раскраски некоторых полных многодольных графов

Համատեղ հեղինակները:

Russian-Armenian (Slavonic) University, Yerevan, Armenia ; Yerevan State University (YSU)

Ծածկույթ:

136-143

Ամփոփում:

In graph theory, an edge coloring of a graph is a coloring of the edges, meaning an assignment of colors to edges. Edge coloring can be described as function f:E(G)→N, where E(G) is the set of graph edges and N is the set of natural numbers. Graph coloring has been studied as an algorithmic problem since the early 1970s. The main objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G with specified conditions is called chromatic number of that graph and is denoted by χ'(G). By a result of Holyer [1], the determination of the chromatic index is an NP-hard optimization problem. The NP-hardness give rise to the necessity of using heuristic algorithms. In particular, we are interested in upper bounds for the chromatic index that can be efficiently realized by a coloring algorithm.
Գրաֆների տեսության մեջ կողային ներկում է կոչվում կողերի ներկումը, այսինքն՝ գրաֆի յուրաքանչյուր կողին գույնի համապատասխանեցումը։ Կողային ներկումը կարելի է ներկայացնել f:E(G)→N ֆունկցիայի միջոցով, որտեղ E(G)-ով նշանակվում է գրաֆի կողերի բազմությունը, N-ով բնական թվերի բազմությունը։ Գրաֆների ներկման խնդիրները, որպես ալգորիթմիկ խնդիրներ, սկսել են դիտարկվել 1970-ականներից։ Հիմնական նպատակն է նվազագույնի հասցնել օգտագործվող գույների քանակը։ Գույների փոքրագույն քանակը, որոնց միջոցով կարելի է իրականցնել գրաֆի կողային ներկում, կոչվում է քրոմատիկ համար և նշանակվում χ'(G)։ Holyer [1]-ի կողմից ապացուցվել է, որ քրոմատիկ թվի որոշումը NP-բարդ օպտիմիզացիայի խնդիր է։ Այդ պատճառով էվրիստիկ ալգորիթմների կարիք է առաջանում։ Հեղինակի խնդիրն է՝ գտնել քրոմատիկ թվի վերին սահմաններ, որոնք կարելի է արդյունավետ ձևով ստանալ՝ օգտագործելով համապատասխան ներկման ալգորիթմներ։
В теории графов рёберной раскраской называется раскраска рёбер графа, то есть при раскраске графа всем рёбрам соответствуют метки или так называемые цвета. Для графа G функция f:E(G)→N называется рёберной раскраской графа G, где E(G)-множество рёбер графа, а N-множество натуральных чисел. Рёберную раскраску графов стали рассматривать как алгоритмическую проблему начиная с 1970-ых годов. Главной задачей в теории раскрасок графов является нахождение минимального количества цветов, используемых в раскраске графа. Минимальное количество цветов, необходимое для раскраски графа при определённых условиях, называется хроматический индекс и обозначается через χ'(G). По результатам исследования Holyer-а, нахождение хроматического индекса графа является NP-сложной задачей оптимизации. Из-за NP-сложности данной задачи возникает необходимость нахождения эвристических алгоритмов. В частности, авторов интересует нахождение верхних оценок для хроматического индекса раскраски графов путём эффективной реализации раскраски.

Հրատարակիչ:

ՀՀ ԳԱԱ

Ձևաչափ:

pdf

Նույնացուցիչ:

սեղմիր այստեղ կապին հետևելու համար ; oai:arar.sci.am:325593

Լեզու:

en

Բնօրինակի գտնվելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան