Про хроматичне число натуральних модульних графів
The problem of chromatic number definition for a subclass of numerical graphs, namely natural modular graphs, is raised for the first time. A few affirmations are proved which allow defining the chromatic number of these graphs with the number of generatrixes not over three. To solve a general probl...
Saved in:
| Date: | 2019 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/165508 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302348747341824 |
|---|---|
| author | Donets, G. P. Shulinok, G. O. |
| author_facet | Donets, G. P. Shulinok, G. O. |
| author_sort | Donets, G. P. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-04-25T14:46:04Z |
| description | The problem of chromatic number definition for a subclass of numerical graphs, namely natural modular graphs, is raised for the first time. A few affirmations are proved which allow defining the chromatic number of these graphs with the number of generatrixes not over three. To solve a general problem, a method of differences is proposed, possibilities of which are described and an example of its use is given. |
| first_indexed | 2025-07-17T10:24:53Z |
| format | Article |
| fulltext |
© Г.А. Донец, Г.А. Шулинок, 2006
Системні дослідження та інформаційні технології, 2006, № 1 133
УДК 519.1
О ХРОМАТИЧЕСКОМ ЧИСЛЕ НАТУРАЛЬНЫХ
МОДУЛЬНЫХ ГРАФОВ
Г.А. ДОНЕЦ, Г.А ШУЛИНОК
Впервые поставлена задача определения хроматического числа для одного
подкласса числовых графов — натуральных модульных графов. Доказано не-
сколько утверждений, позволяющих находить хроматическое число указанных
графов с числом образующих не больше трех. Для решения общей задачи
предлагается метод разностей, описываются его возможности и пример реали-
зации.
ВВЕДЕНИЕ
Известно [1], что задача определения хроматического числа произвольных
графов в общем случае является NP-полной. Только для хроматического
числа меньшего трех она является полиномиальной. Однако существуют
некоторые довольно обширные подклассы графов, где эта задача может
быть решена полиномиальными алгоритмами. Речь идет о числовых графах,
исследование которых начато более 20 лет назад [2–8]. В этих работах в ос-
новном исследовалась структура числовых графов (связность, цикломатиче-
ское число, факторизация) и способы оптимального представления обыкно-
венных графов в виде числовых.
В данной работе решается задача определения хроматического числа
одного из главных представителей числовых графов — натуральных мо-
дульных графов (NM-графов).
Определение 1. Натуральным модульным графом ),( UXG называется
n -вершинный граф )1( >n , представленный двумя множествами:
nn NxxxX == },,,{ 21 … — множеством вершин и
NuuuU m ∈= },,,{ 21 … — множеством образующих.
Две вершины Xxx ji ∈, смежны, если Uxx ji ∈− .
Каждая образующая ),,2,1( miui …= соответствует iun − ребрам
графа. Регулярный NM-граф степени 2 представляется множеством из
двух образующих },{ unuU −= и состоит из k циклов длины
k
n , где
),(НОД nuk = . Если n и u взаимно просты, то 1=k , и такой граф пред-
ставляет собой гамильтонов цикл. Регулярный граф степени ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⎥⎥
⎤
⎢⎢
⎡<
2
2 nkk
описывается множеством образующих
},,,,,,,{ 1221 unununuuuU kk −−−= …… ,
Г.А. Донец, Г.А. Шулинок
ISSN 1681–6048 System Research & Information Technologies, 2006, № 1 134
где ⎥⎦
⎥
⎢⎣
⎢≤≤
2
1 nui . Регулярный граф степени )1(12 ≥+ kk существует только
для четных n и отличается от предыдущего наличием дополнительной об-
разующей
2
nu = .
Определение 2. Хроматическим числом NM-графа называется наи-
меньшее число )(Gλ , которому соответствует разбиение множества вершин
X на )(Gλ взаимно непересекающихся подмножеств )(,),2(),1( λXXX …
таких, что любые две вершины ),,2,1()(, λ…=∈ iiXyx несмежны, т.е.
Uyx ∉− .
Очевидно, что если 1),,,(НОД 21 >= cuuu m… , то граф состоит из c
компонент связности, и вопрос о хроматическом числе исходного графа
сводится к тому же вопросу для графа с ⎥⎥
⎤
⎢⎢
⎡
c
n вершинами и множеством об-
разующих
⎭
⎬
⎫
⎩
⎨
⎧
=′
c
u
c
u
c
u
U m,,, 21 … .
ХРОМАТИЧЕСКОЕ ЧИСЛО ПРОСТЕЙШИХ NM-ГРАФОВ
Для NM-графов с числом образующих меньше трех определить хроматиче-
ское число несложно. Так как NM-граф с одной образующей }{uU = пред-
ставляет собой набор из u цепей, то справедливо следующее
Утверждение 1. Хроматическое число )(Gλ NM-графа с одной обра-
зующей равно 2.
Рассмотрим теперь NM-графы с двумя образующими, при этом число
вершин NM-графа будем считать произвольным.
Теорема 1. Хроматическое число NM-графа ),( UXG для },{ 21 uuU =
равно
( )⎪⎩
⎪
⎨
⎧
+−+≥
+
+
+−+<
=
,1если,2mod2
,1если,2
)(
21
21
21
cuun
c
uu
cuun
Gλ (1)
где ),(НОД 21 uuc = .
Доказательство. Рассмотрим сначала случай, когда 1=c . Тогда граф
для 21 uun +< представляет собой несколько отдельных цепей, поэтому для
него 2)( =Gλ . Для 21 uun +≥ граф состоит из одного большого цикла дли-
ной 21 uu + и нескольких циклов длиной 4 [9]. В зависимости от четности
числа 21 uu + большой цикл можно раскрасить двумя или тремя цветами.
Каждая вершина )0(21 >++= iiuuj соединяется с вершинами iu +1 и
iu +2 , которые смежны с вершиной i . Придадим вершине j тот же цвет,
что и вершине i . Поскольку цвет этой вершины не противоречит цветам
О хроматическом числе натуральных модульных графов
Системні дослідження та інформаційні технології, 2006, № 1 135
смежных с ней вершин, а вершина j смежна с теми же вершинами, то такая
раскраска не увеличит хроматическое число графа и формула (1) верна для
этого случая.
Пусть теперь 1>c . В этом случае граф состоит из c компонент связно-
сти. Компонента с номером )1( cii ≤≤ состоит из тех вершин, номер кото-
рых )(mod ci . Рассмотрим компоненту 1=i . Она содержит не меньше вер-
шин, чем остальные, и число их ⎥⎥
⎤
⎢⎢
⎡=′
c
nn . Таким образом эта компонента
изоморфна NM-графу с числом вершин n′ и множеством образующих
},{, 21
21 uu
c
u
c
u
U ′′=
⎭
⎬
⎫
⎩
⎨
⎧=′ , где 1),(НОД 21 =′′ uu . Тем самым вопрос о хромати-
ческом числе исходного графа свелся к этому же вопросу для графа
),( UXG ′′ , где },,2,1{ nX ′=′ … . Этот граф не будет содержать большой
цикл, если 21 uun ′+′<′ . Если cuun −+= 21 , то 2121 1 uuuun ′+′<−′+′=′ . Ес-
ли же 121 +−+= cuun , то 21 uun ′+′=′ , и появляется большой цикл, кото-
рый можно раскрасить двумя или тремя цветами в зависимости от четности
суммы 21 uu ′+′ . Тем самым подтверждается формула (1) и теорема доказана.
Рассмотрим теперь некоторые NM-графы с числом образующих боль-
ше двух, при этом число вершин будем считать произвольным. Как правило,
21 uun +≥ . Множество раскрасок на рисунках обозначим с помощью мно-
жества },,,,{ …δγβα=Q . Поставим ему в соответствие множество чисел
},3,2,1,0{ …=′Q , а цвет вершины i обозначим Qqi ′∈ .
Лемма 1. NM-граф с образующими )2(},2,1{ >= kkU имеет хрома-
тическое число
3mod)1(3)( 2kG −+=λ . (2)
Действительно, если изобразить такой граф в виде линейной последо-
вательности вершин, то получим рис. 1. Образующие 11 =u и 22 =u делают
раскраску графа вынужденной, если первые три его вершины окрасить цве-
тами βα , и γ .
Вершина 4 смежна с вершиной 2 цвета β и вершиной 3 цвета γ , по-
этому ее цвет однозначен — α , т.е. 04 =q . Аналогично рассуждая, получа-
ем )3)(mod1( −≡ iqi . Если )3(mod0≡k , то эта образующая будет соеди-
нять одноцветные вершины, что делает невозможным окрасить весь граф
тремя цветами. Его легко раскрасить четырьмя цветами, так как после рас-
краски трех первых вершин последующие связаны не более, чем с тремя
Рис. 1. Граф для },2,1{ kU =
1 5 6 n-2 n-1 n432
α γβαγβ
...
...
...
u=kα β γ α β γ
Г.А. Донец, Г.А. Шулинок
ISSN 1681–6048 System Research & Information Technologies, 2006, № 1 136
уже раскрашенными вершинами. Это дает возможность всегда выбрать сво-
бодную четвертую краску. Таким образом, если )3(mod0≠k , то в форму-
ле (2) )3(mod12 ≡k , и формула верна.
Лемма 2. Если в NM-графе все )2(mod1≡iu , то
2)( =Gλ .
Это можно легко показать, если всем вершинам с четными номерами
приписать цвет β , всем вершинам с нечетными — α . В общем случае по-
ложить )2(modiqi ≡ . Образующие не могут соединять вершины, номера
которых имеют одинаковую четность, поэтому вершины с одинаковой окра-
ской всегда несмежны.
Следствие. Если в NM-графе ),( UXG все образующие имеют вид
llku ii += 2 , где 0≥ik , а l — заданная положительная константа, то
2)( =Gλ .
Действительно, в этом случае luuu m =),,,(НОД 21 … , и каждая обра-
зующая имеет вид )12( +ikl . Вопрос о хроматическом числе исходного
графа сводится к графу, у которого число вершин ⎥⎥
⎤
⎢⎢
⎡=′
l
nn и образующие
имеют вид 12 += ii ku или ),,2,1()2(mod1 miui …=≡ . По лемме 2 это рав-
носильно 2)( =Gλ .
Теорема 2. Хроматическое число NM-графов с образующими
},,{ lklkU += при )(2 lkn +≥ равно
)3(mod)(3)( 2klG −+=λ . (3)
Доказательство. Как указывалось выше, для lkn +< 2)( =Gλ . Пусть
lkn += . В этом случае NM-граф представляет собой гамильтонов цикл.
Если проследить за последовательностью номеров вершин, образующих
ребра цикла, то они представляют k возрастающих арифметических про-
грессий типа ),,2,1(,2, kikiki …… =++ . Как только номер попадает в
интервал ),1( nkn +− , то с помощью ребра, соответствующего образующей
l , делается переход (путем вычитания l ) к следующей возрастающей по-
следовательности.
Положим теперь lkn += 2 . Каждая вершина ilk ++ ),,2,1( ki …= бу-
дет смежной с вершиной i и двумя соседними с ней по циклу. На рис. 2 ка-
ждой такой вершине соответствуют две соседние заштрихованные тре-
угольные грани. Дополним число вершин до lk 22 + и получим рис. 2.
Если окрасить вершину 1 цветом α , а вершину 5 цветом β , то рас-
краска всего графа тремя цветами произойдет однозначно. Если взять за
основание внутренний цикл, то весь граф на рис. 2 можно разбить на lk +
четырехугольников с диагоналями (блоков). Если придерживаться упорядо-
ченности раскрасок во множестве Q , то все вертикальные ребра в блоках
О хроматическом числе натуральных модульных графов
Системні дослідження та інформаційні технології, 2006, № 1 137
имеют раскраску вершин ),(),,( γββα или ),( αγ , что соответствует числам
из множества Q′ )3(mod)1,( +ii )2,1,0( =i . Если теперь в блоках просле-
дить переход раскраски вершин левого ребра к раскраске вершин правого,
то получим следующую зависимость: в одних блоках происходит пере-
ход ),(),( γββα → , ),(),( αγγβ → и ),(),( βααγ → , а в других —
),(),( αγβα → , ),(),( βαγβ → и ),(),( γβαγ → . Эти блоки различаются
положением диагонали. Назовем блоки первого типа плюс-блоками, так как
в них происходит переход )3)](mod2,1()1,[( ++→+ iiii . Соответственно
блоки второго типа назовем минус-блоками, так как в них происходит пе-
реход )3)](mod,1()1,[( iiii −→+ (рис. 3).
Как видно из рис. 2, минус блоки являются левыми частями в парах
раскрашенных треугольников, поэтому их число равно k . Так как число
блоков lk + , то отсюда вытекает, что число плюс-блоков l . Раскраска графа
будет непротиворечивой, если сумма всех знаков плюс- и минус-блоков
)3(mod0 . Отсюда условие существования раскраски графа тремя цветами
20
17
21
18
22
19 23
165
8
1
12
15
4
11
7
3
14
10 6
9
2
13
α
α
α
α
α
α
α
α
β
β
β
β
β
β
β
β
γ
γ
γ
γ
γ
γ
γ
Рис. 2. Граф с образующими }11,7,4{=U
i
i+1 i
i-1
i+2i+1
ii
+-
i+1
i-1
i i+1 i+2
i i i
Рис. 3. Два типа раскрашенных блоков
Г.А. Донец, Г.А. Шулинок
ISSN 1681–6048 System Research & Information Technologies, 2006, № 1 138
)3(mod0≡− kl ,
что дает первое условие (3). Для большего числа вершин дальнейшая рас-
краска однозначна, так как в качестве основания выбирается внешний цикл.
Это видно на примере вершины 23 на рис. 2. Покажем теперь, что для лю-
бых k и l достаточно четырех красок, чтобы раскрасить исходный NM-
граф. Это достигается многими способами. Один из них состоит в том, что-
бы раскрасить тремя цветами исходный цикл (вершины от 1 до lk + ). Сле-
дующие вершины смежны только с тремя ранее окрашенными вершинами,
поэтому всегда есть четвертый свободный цвет.
Лемма 3. Хроматическое число NM-графов с множеством образующих
},,{ 321 uuuU = , где iu не удовлетворяют условиям леммы 2 и ее следствию,
и )3,2,1()3(mod0 =≠ iui равно
3)( =Gλ .
Действительно, в этом случае вершине с номером i можно придать
цвет )3(modiqi ≡ . Любые две одинаково окрашенные вершины x и y не-
смежны, иначе было бы Uyx ∈− , т.е. какая-то образующая равна )3(mod0 ,
что противоречит начальному условию. Очевидно, что лемма 1 является
следствием леммы 3.
МЕТОДЫ РАСКРАСКИ NM-ГРАФОВ
Существует несколько способов (алгоритмов) раскраски графов произволь-
ным числом цветов. Обозначим ),( λGf число всех раскрасок n -вершинно-
го графа ),( UXG с помощью λ различных цветов. Известно [10], что если
в графе G существует две несмежные вершины a и b , то
)),((),(),( λλλ baGfbaGfGf ≡+∪= , (4)
где abG∪ — граф G , у которого вершины a и b соединены ребром, а
)( baG ≡ — граф G , у которого вершины a и b стянуты в одну. Продол-
жая применять формулу (4) для графов в правой части до тех пор, пока в
них найдутся несмежные вершины, получаем окончательное выражение
∑
=
=
n
si
ii kfcGf ),(),( λλ , (5)
где ik — полный −i вершинный граф, а ic — неотрицательные целые чис-
ла. Очевидно, что 0),( =λikf , если λ>i . Поэтому исходный граф G мо-
жет быть раскрашенным в λ цветов только тогда, когда λ≤s .
Однако на практике применять формулу (5) очень сложно, разве что
для очень специальных или простых графов. Рассмотрим произвольный
NM-граф с двумя образующими },{ 21 uuU = и 21 uun += , 1),(НОД 21 =uu .
Этот граф является гамильтоновым циклом. Если добавлять к нему новые
вершины с номерами )1(21 ≥++ iiuu , то к исходному циклу добавятся
О хроматическом числе натуральных модульных графов
Системні дослідження та інформаційні технології, 2006, № 1 139
новые внешние циклы длиной 4 вида ),,,( 2211 uiuuiuii ++++ . В этих
циклах всегда вершины i и 21 uui ++ несмежны, поэтому к ним можно
применить формулу (4). Отбросим в правой части те слагаемые, которые
соответствуют графам, где добавляются ребра, соединяющие несмежные
вершины. В результате равенство (4) превращается в неравенство (рис. 4).
Хроматическое число графа, полученного справа, равно 2 или 3 в зави-
симости от четности числа 21 uu + . Граф слева также может быть окрашен
как и правый граф, если склеенные вершины окрасить одним цветом. Зна-
чит, его хроматическое число не может быть больше, чем у графа справа.
Можно сказать, что здесь повторно доказана теорема 1.
Но для NM-графов
уже с тремя образую-
щими, применяя только
операции стягивания,
можно получить в пра-
вой части (4) очень
сложный граф. Его хро-
матическое число вы-
числить не всегда про-
сто. Поэтому для таких
графов предлагается
другой метод раскраски,
который назовем мето-
дом разностей. Для
лучшего усвоения сути
этого метода рассмот-
рим пример NM-графа
на рис. 5, раскрашенно-
го в три цвета. Для него
21=n и }8,6,3{=U .
В дальнейшем будем предполагать, что в раскрашенном графе всегда
вершина с номером 1 имеет цвет α , а следующая с наименьшим номе-
ром — β . Выпишем последовательности вершин графа на рис. 5, которые
соответствуют каждому цвету, в возрастающем порядке.
7
14
11
19
16
13
10
21
18
15
4
1
12
20
17
9
6
3
8 5
2
γ
γ
γ
γγ
γ
γ
α
α
αα α
α
α
β
β
β
β
β
β
β
Рис. 5. Граф с }8,6,3{=U и 21=n
f( ≥) f( )
7
1
3
5
2
4
6
8
10
12
14
9
11
13
1, 8
6,13
4,11
3,10
5,12
2, 9 7,14
Рис. 4. Пример для графа с }5,2{=U и 14=n
Г.А. Донец, Г.А. Шулинок
ISSN 1681–6048 System Research & Information Technologies, 2006, № 1 140
.21,16,14,12,7,5,3~
,20,18,13,11,9,4,2~
,19,17,15,10,8,6,1~
γ
β
α
(6)
Вычислим разности между соседними элементами этих последователь-
ностей:
.5,2,2,5,2,2~
,2,5,2,2,5,2~
,2,2,5,2,2,5~
γ
β
α
(7)
Легко заметить, что последние последовательности периодические. Для
цвета α периодически повторяющиеся числа (5,2,2), для β — (2, 5, 2) и для
γ — (2, 2, 5). Назовем эти числа кодами раскраски и обозначим их соответ-
ственно α∆ , β∆ , γ∆ . В данном примере все коды раскраски имеют одина-
ковую длину, а β∆ и γ∆ можно получить из кода α∆ путем сдвига его
компонент по циклу. Однако эти свойства для них выполняются не всегда.
Если коды раскраски известны, то тем самым определяется и раскраска гра-
фа для произвольного числа вершин. Покажем, что коды раскрасок облада-
ют некоторыми постоянными свойствами, которые помогут нам в некото-
рых случаях.
Свойство 1. Любая сумма последовательных чисел кода раскраски в
(7) не принадлежит U .
Действительно, если бы это было так, то в какой-то одноцветной по-
следовательности (6) нашлись бы два таких номера вершин, разность между
которыми принадлежала бы U , что означало бы: вершины смежны, но та-
кого не может быть в силу их одноцветности. В нашем примере суммы рав-
ны 2, 4, 5, 7, 9 и больше, и ни одно из этих значений не равно какой-либо
образующей.
Пусть длина кода соответствующей раскраски равна αl , βl и γl . Обо-
значим компоненты кодов раскраски верхними индексами в скобках. На-
пример, 5)1( =∆α , 2)3()2( =∆=∆ αα .
Свойство 2. Для кодов раскраски NM-графа справедливо
∑ ∑ ∑
= = =
++=∆=∆=∆
α β γ
γβαγβα
l
i
l
i
l
i
iii lll
1 1 1
)()()( . (8)
Предположим сначала, что в каком-то коде раскраски это условие не
выполняется. Не нарушая общности, пологаем, что
∑
=
≥+++=∆
α
εεγβαα
l
i
i lll
1
)( )1( . (9)
Среди первых 1l чисел в строке α , первых 2l чисел в строке β и пер-
вых 3l чисел в строке γ (6) находятся все числа от 1 до 1321 +++ lll . Все-
гда можно найти некоторое число x в строке α , а в других строках число
y такое, что ε=− xy . Это невозможно только в случае, если εα =∆ )(i
),,2,1( αli …= , но тогда α∆ не может быть кодом раскраски.
О хроматическом числе натуральных модульных графов
Системні дослідження та інформаційні технології, 2006, № 1 141
Рассмотрим в строке, где находится x , вершину с номером =1N
∑
=
∆+=
α
α
l
i
ix
1
)( . Эта вершина должна быть окрашена цветом α , так как разни-
ца между 1N и x равна повторяющемуся периоду. С другой стороны, вер-
шина с номером γβα lllyN +++=2 окрашена в тот же цвет, что и вершина
y по той же причине. Но согласно (9) 21 NN = , поэтому вершины x и y
окрашены одним цветом. Пришли к противоречию, что подтверждает спра-
ведливость формулы (8).
Метод разностей позволяет, анализируя состав образующих NM-графа,
находить правильную раскраску графа и на этом основании судить о его
хроматическом числе. В последующих работах будет более подробно
показано, как на практике пользоваться таким методом для нахождения со-
ответствующих кодов раскраски. Воспользуемся им для доказательства сле-
дующего результата.
Теорема 3. Хроматическое число NM-графа ),( UXG с }2,3,1{ kU =
3)( ≥k равно 3.
Если в кодах раскраски некоторые компоненты повторяются, то мы бу-
дем иногда пользоваться записью в виде основания с показателем. Напри-
мер, )5,2,2,2,1,1(=∆α можно записать как )5,2,1( 32=∆α . Чтобы дока-
зать теорему, просто укажем вид кодов раскрасок для соответствующего
цвета. Находим сначала число ⎥⎦
⎥
⎢⎣
⎢ +
=
4
12 kd . Теперь докажем, что коды раск-
расок строятся так:
).3,2(
),2,3,2(
),2,3(
22
+=∆
+=∆
+=∆
d
d
d
d
d
d
d
γ
β
α
(10)
Так как в этих кодах 1+=== dlll γβα , то второе свойство кодов для
них легко проверить:
∑ ∑ ∑
+
=
+
=
+
=
+=++=∆=∆=∆
1
1
1
1
1
1
)()()( )1(323
d
i
d
i
d
i
iii dddγβα .
Чтобы проверить первое свойство, образуем всевозможные последова-
тельные суммы компонент кодов раскраски. Легко видеть, что никакие та-
кие суммы не равны 11 =u или 32 =u . Если взять только двойки, то суммы
принимают значения ⎥⎦
⎥
⎢⎣
⎢ +
=
4
142,,4,2 kd… . Для всех 0, >qp справедливо
)(mod qpp
q
pq −=⎥
⎦
⎥
⎢
⎣
⎢
. Поэтому 32)4)(mod1(12 ukkkd =<+−+= . Если
брать суммы с привлечением одного слагаемого 3+d , то полученные сум-
мы будут нечетными. Поэтому k2≠ . Если слагаемое 3+d использовать два
раза, то все полученные суммы будут не меньше =+=++ ]32[22)3(2 ddd
Г.А. Донец, Г.А. Шулинок
ISSN 1681–6048 System Research & Information Technologies, 2006, № 1 142
]3)4)(mod11[2 ++−+= kk . Так как наибольшее значение )4)(mod1( +k
равно 3, то все суммы будут не меньше )1(2 +k , т. е. больше 3u .
Согласно кодам (10) построим непосредственно последовательности
раскрашенных вершин (6) с номерами от 1 до 33 +d .
.________32,,7,5,3,,7,5,3~
,33,,52_______,2,,6,4,2~
,23,,42,22,,6,4________,1~
++++
+++
+++++
dddd
ddd
ddddd
……
……
……
γ
β
α
Здесь прямыми отрезками отмечены разности, равные 3+d , осталь-
ные — 2. Эти последовательности можно продлевать до любой величины,
так как они периодические с периодом 33 +d , что и подтверждает справед-
ливость теоремы.
Очевидно, что найденные выше раскраски являются избыточными, т. е.
они годятся и для NM-графов с большим числом образующих. Так как наи-
меньшая нечетная сумма последовательных компонент кодов раскраски
равна 3+d , то U может содержать нечетные образующие, которые меньше
этого числа. Это значит, что раскраска исходного NM-графа та же, что и у
графа с образующими }2,1,,5,3,1{ kdU +=′ … . Отсюда можно сделать вы-
вод, что раскраска с помощью метода разниц может применяться для NM-
графов с произвольным числом образующих.
ЛИТЕРАТУРА
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. —
М.: Мир, 1982. — 416 с.
2. Донец Г.А. О графах, задаваемых аналитическим образом // Теория
оптимальных решений. — Киев: Ин-т кибернетики им. В.М. Глушкова АН
УССР, 1987. — С. 20 –27.
3. Донец Г.А. Об оптимальном кодировании однородных деревьев в арифметиче-
ских графах // Методы решения экстремальных задач и смежные вопросы. —
Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1987. — С. 72–77.
4. Донець Г.П., Неженцев Ю.І. Арифметичні графи та їх представлення // Доп.
АН УРСР. Сер. А. — 1990. — № 11. — С. 5 – 8.
5. Донец Г.А., Шулинок И.Э. Об общем представлении числовых графов // Теория
оптимальных решений. — Киев: Ин-т кибернетики им. В.М. Глушкова
НАН Украины, 2004. — С. 11 – 18.
6. Шулинок И.Э. Об одном классе числовых графов // Теория и приложения
методов оптимизации. — Киев: Ин-т кибернетики им. В.М. Глушкова НАН
Украины, 1998. — С. 24 – 29.
7. Шулинок И.Э. О связности и цикломатическом числе натуральных модульных
графов // Теория оптимальных решений. — Киев: Ин-т кибернетики им.
В.М. Глушкова НАН Украины, 1999. — С. 51 – 57.
8. Шулінок Г.О. Про ізоморфізм натуральних модульних графів // Теория опти-
мальных решений. — Киев: Ин-т кибернетики им. В.М. Глушкова НАН
Украины, 2004. — С. 69 – 73.
9. Шулинок Г.А. Об изоморфизме регулярных NM-графов // Теория оптимальных
решений. — Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины,
2005. — С. 100 – 106.
10. Лекции по теории графов / В.А Емеличев, О.И. Мельников, В.И. Сарванов,
Р.И. Тышкевич. — М.: Наука, 1990. — 384 с.
Поступила 20.10.2005
|
| id | journaliasakpiua-article-165508 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:24:53Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/8a/3f784e5570282d9a5420e34f563ebc8a.pdf |
| spelling | journaliasakpiua-article-1655082019-04-25T14:46:04Z On chromatic number of natural modular graphs О хроматическом числе натуральных модульных графов Про хроматичне число натуральних модульних графів Donets, G. P. Shulinok, G. O. The problem of chromatic number definition for a subclass of numerical graphs, namely natural modular graphs, is raised for the first time. A few affirmations are proved which allow defining the chromatic number of these graphs with the number of generatrixes not over three. To solve a general problem, a method of differences is proposed, possibilities of which are described and an example of its use is given. Впервые поставлена задача определения хроматического числа для одного подкласса числовых графов — натуральных модульных графов. Доказано несколько утверждений, позволяющих находить хроматическое число указанных графов с числом образующих не больше трех. Для решения общей задачи предлагается метод разностей, описываются его возможности и пример реализации. Вперше поставлено задачу визначення хроматичного числа для одного підкласу числових графів — натуральних модульних графів. Доведено декілька тверджень, що дозволяють знаходити хроматичне число вказаних графів із числом твірних не більше трьох. Для розв’язання загальної задачі пропонується метод різниць, описуються його можливості та приклад застосування. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-04-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/165508 System research and information technologies; No. 1 (2006); 133-142 Системные исследования и информационные технологии; № 1 (2006); 133-142 Системні дослідження та інформаційні технології; № 1 (2006); 133-142 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/165508/164744 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Donets, G. P. Shulinok, G. O. Про хроматичне число натуральних модульних графів |
| title | Про хроматичне число натуральних модульних графів |
| title_alt | On chromatic number of natural modular graphs О хроматическом числе натуральных модульных графов |
| title_full | Про хроматичне число натуральних модульних графів |
| title_fullStr | Про хроматичне число натуральних модульних графів |
| title_full_unstemmed | Про хроматичне число натуральних модульних графів |
| title_short | Про хроматичне число натуральних модульних графів |
| title_sort | про хроматичне число натуральних модульних графів |
| url | https://journal.iasa.kpi.ua/article/view/165508 |
| work_keys_str_mv | AT donetsgp onchromaticnumberofnaturalmodulargraphs AT shulinokgo onchromaticnumberofnaturalmodulargraphs AT donetsgp ohromatičeskomčislenaturalʹnyhmodulʹnyhgrafov AT shulinokgo ohromatičeskomčislenaturalʹnyhmodulʹnyhgrafov AT donetsgp prohromatičnečislonaturalʹnihmodulʹnihgrafív AT shulinokgo prohromatičnečislonaturalʹnihmodulʹnihgrafív |