О хроматическом числе натуральных арифметических графов с тремя образующими
Рассматриваются натуральные арифметические графы с тремя образующими. Доказывается, что хроматическое число этих графов равно трем. Розглядаються натуральні арифметичні графи з трьома твірними. Доводиться, що хроматичне число таких графів дорівнює трьом. Natural arithmetical graphs with three genera...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/12698 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О хроматическом числе натуральных арифметических графов с тремя образующими / Г.А. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 50-60. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859796243781255168 |
|---|---|
| author | Донец, Г.А. Шулинок, И.Э. |
| author_facet | Донец, Г.А. Шулинок, И.Э. |
| citation_txt | О хроматическом числе натуральных арифметических графов с тремя образующими / Г.А. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 50-60. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| description | Рассматриваются натуральные арифметические графы с тремя образующими. Доказывается, что хроматическое число этих графов равно трем.
Розглядаються натуральні арифметичні графи з трьома твірними. Доводиться, що хроматичне число таких графів дорівнює трьом.
Natural arithmetical graphs with three generatrixes are considered. It is proved that the chromatic number of such kind graphs is three.
|
| first_indexed | 2025-12-02T13:41:51Z |
| format | Article |
| fulltext |
50 Теорія оптимальних рішень. 2008, № 7
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются натуральные
арифметические графы с тремя
образующими. Доказывается, что
хроматическое число этих графов
равно трем.
Г.А. Донец, И.Э. Шулинок,
2008
ÓÄÊ 519.8
Ã.À. ÄÎÍÅÖ, È.Ý. ØÓËÈÍÎÊ
Î ÕÐÎÌÀÒÈ×ÅÑÊÎÌ ×ÈÑËÅ
ÍÀÒÓÐÀËÜÍÛÕ ÀÐÈÔÌÅÒÈ×ÅÑÊÈÕ
ÃÐÀÔÎÂ Ñ ÒÐÅÌß ÎÁÐÀÇÓÞÙÈÌÈ
Рассмотрим произвольный натуральный
арифметический граф (NА-граф) ),( YXG =
с тремя образующими ( )321 ,, uuuU = , где
3211 uuu <<< . Для определения хромати-
ческого числа (не меньше двух) таких произ-
вольных графов висячие вершины не играют
никакой роли, так как их всегда можно рас-
красить цветом, который отличается от цвета
соседней вершины. Поэтому путем удаления
таких вершин вместе с инцидентными реб-
рами всегда можно добиться того, что во-
прос о хроматическом числе произвольных
графов решался для графов, степень вершин
которых не меньше двух.
Лемма 1. Хроматическое число n-
вершинного NA-графа с произвольными об-
разующими ( )321 ,, uuuU = равно хроматиче-
скому числу NA-графа с теми же (или двой-
ственными к ним) образующими с числом
вершин 12 −=′ un .
Доказательство. Пусть NA-граф состо-
ит из произвольного числа вершин. Оно
должно быть не меньше 11 −u , иначе тогда
первая образующая будет излишней. Если в
исходном графе 12 +> nu , то с помощью
преобразований )3,2,1(22 =−+=′ iunu ii
переходим к двойственным образующим iu′ ,
у которых 12 +≤′ nu . Таким образом, не на-
рушая общности, считаем, что в исходном
NA-графе 12 +≤ nu . В этом случае все вер-
шины с номерами, большими чем 12 −u ,
О ХРОМАТИЧЕСКОМ ЧИСЛЕ НАТУРАЛЬНЫХ АРИФМЕТИЧЕСКИХ ГРАФОВ …
Теорія оптимальних рішень. 2008, № 7 51
инцидентны ребрам, которые соответствуют только одной образующей 3u , по-
этому имеют степень 1. Как указывалось выше, их можно удалять, не изменяя
хроматического числа исходного графа. В результате и получим в остатке
12 −=′ un вершин.
Будем называть такие NA-графы с тремя образующими нормированными
графами. В дальнейшем, если потребуется, на рисунках ребра графов, соответ-
ствующие образующей 1u , будем изображать тонкой линией, образующей 2u –
жирной линией и образующей 3u – двойной линией. Поскольку хроматическое
число каждой компоненты графа не зависит от других компонент, будем рас-
сматривать только связные графы. О связности NA-графов с тремя образующи-
ми можно судить из [1].
Лемма 2. Число компонент связности нормированного NA-графа с тремя
образующими ( )321 ,, uuuU = равно числу решений сравнения
( )ruji mod1≡+ , (1)
где ( )1223 , uuuuНОДr −−= .
По формуле (1) получается, что если 1=r , то граф связен, так как тогда
)1(mod01 ≡u , и решением (1) является единственная пара ( )( )rmod0,0 , а если
2=r , то граф связен только для ( )2mod11 ≡u с единственным решением ( )1,0 .
Если ( )2mod01 ≡u , то (1) имеет два решения ( )0,0 и ( )1,1 , тогда граф будет
несвязным. Действительно, в данном случае граф разбивается на два подграфа –
с нечетными и с четными номерами вершин. Если какие-то две вершины из раз-
ных подграфов смежные, то тогда какое-то ( ) { }3,2,12mod1 ∈≡ iui , но это про-
тиворечит начальным условиям, так как из ( )2mod01 ≡u , ( )2mod023 ≡− uu и
( )2mod012 ≡− uu следует ( )2mod0321 ≡≡≡ uuu .
Рассмотрим всевозможные сочетания трех образующих с точки зрения их
четности, или нечетности: 1) ( )2mod1≡iu ; 2) ( ) ( )3,2,12mod0 =≡ iui ; 3) только
одна образующая равна ( )2mod1 ; 4) две образующие равны ( )2mod1 . Для пер-
вого случая справедлива
Теорема 1. Хроматическое число нормированного NA-графа с тремя обра-
зующими ( )321 ,, uuuU = для ( )2mod1≡iu , ( )3,2,1=i равно 2.
Доказательство. Графы с хроматическим числом 2 называются бихромати-
ческими. По теореме Кёнига [2] такие графы не содержат циклов нечетной дли-
ны. Предположим противное, что в заданном графе существует цикл нечетной
длины, который проходит через вершины с номерами )1(,,...,, 11221 ≥+ kxxxx k .
Тогда для какой-то последовательности образующих 12321 ,...,,, +kvvvv , где
( )12,...,2,1 +=∈ kiUvi получаем
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
52 Теорія оптимальних рішень. 2008, № 7
( )∑
=
+
+ +−=+−=−=
k
i
i
i
k xvxxvvxxvx
2
1
1
1
121123112 1;...;; , (2)
замыкая цикл, получаем ( )∑
+
=
+
−−=
12
1
1
1
1 1
k
i
i
i
xvx . Отсюда ( )∑
+
=
+
−=
12
1
1
1 1
2
1 k
i
i
i
vx .
Но сумма нечетного числа нечетных чисел является нечетным числом и не
делится на 2. Следовательно, в графе нет циклов с нечетной длиной, что и тре-
бовалось доказать.
Следствие. В любой последовательности образующих, соответствующих
ребрам, не может быть двух подряд одинаковых.
Действительно, если представить в доказательстве теоремы 1, что 21 vv = ,
то это приводит к 13 xx = , а это невозможно.
Лемма 3. Если ( )∑
=
≡
3
1
2mod0
i
iu , то граф содержит единственный цикл
длиною 3.
Из теоремы 1 и следствия видно, что любой цикл длиною 3 (треугольник)
должен соответствовать трем разным образующим, тогда вершинам должны со-
ответсвовать числа
2
321 uuu
x
±±±
= . (3)
Подставляя различные знаки (+ или – ), получим 8 разных чисел. Но не все
эти числа соответствуют вершинам нормированного графа. Необходимо, чтобы
11 2 −≤≤ ux . (4)
Прежде всего очевидно, что невозможно сочетание (–, –, –), так как не вы-
полняется левое неравенство (4) или (+, +, +), тогда не выполняется правое не-
равенство (4). Если 123 uuu +≥ , то тогда этой образующей не соответствует ни
одно ребро. Следовательно, должно быть 123 +< uu . В этом случае в формуле
(3) не может быть двух знаков минус, иначе получается отрицательное число.
Для каждого минуса получаем три значения, которые и определяют ровно три
вершины искомого треугольника, поэтому треугольник единственный. Его вер-
шины имеют координаты
2
;
2
;
2
132
3
231
2
321
1
uuu
x
uuu
x
uuu
x
−+
=
−+
=
−+
= . (5)
Например, у графа с образующими ( )27,22,19=U , с числом вершин
2112 =−= un получаем треугольник с координатами 12,7 21 == xx и
153 =x . Здесь 231121 , uxxuxx =+=+ и 332 uxx =+ .
О ХРОМАТИЧЕСКОМ ЧИСЛЕ НАТУРАЛЬНЫХ АРИФМЕТИЧЕСКИХ ГРАФОВ …
Теорія оптимальних рішень. 2008, № 7 53
Теорема 2. Нормированный NA-граф с тремя четными образующими со-
стоит из нескольких компонент, каждую из которых можно представить в виде
нормированного NA-графа.
Доказательство. Так как ( ) ( )3,2,12mod0 =≡ iui , то найдется такое =r
( ) ( )2mod0, 1223 ≡−−= uuuuНОД . По этому определению ( )ruuu mod321 ≡≡ ,
и существуют такие числа cba <<≤0 и rs <≤0 , что
( )2mod0;;; 321 ≡+=+=+= sscrusbrusaru . (6)
Тогда уравнение (1) имеет 1
2
+
r
решений, которые имеют вид
( ) ( ) ( ) ( )
++
−+
−−
2
,
2
,...,1,1,,,
2
,
2
,...,2,2,1,1
srsr
rsrs
ss
ss . (7)
Например, для графа с ( )80,68,44=U получаем 67=n , 3=a , 5=b ,
6=c , 12=r , 8=s и (7) представится так
(1,7), (2,6), (3,5), (4,4), (8,12), (9,11), (10,10). (8)
Все множество (7) можно разбить на четыре группы, которые между собой
различаются. Рассмотрим первую такую группу, которая представляется парами
( )ji, , где
2
,,
s
ijiji <≠< . В нашем примере это пары ( ) ( )6,2,7,1 и ( )5,3 . Ка-
ждая пара ( )ji, представляет подграф, который состоит из вершин только двух
видов:
( ) 2mod ukririxk <+=≡ и ( ) ( )0,;mod 2 ≥<+=≡ lkulrjrjyk .
Произведем в каждом таком подграфе перенумерацию вершин:
( ) ( )
2
2
;1
2
+
−
=′+
−
=′
r
jy
y
r
ix
x k
k
k
k . (9)
Благодаря этому все подграфы первой группы превратятся в один и тот же
граф G′ . Действительно, номера kx , принимающие значения i , ri + ,
iruri +−+ 2,...,2 , перейдут в номера
( )
1
2
,...,5,3,1 2 +
−
r
su
. Анало-
гично ky , принимающие номера jrurjrjj +−++ 2,...,2,, , перейдут в
номера
( )
2
2
,...,6,4,2 2 +
−
r
su
.
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
54 Теорія оптимальних рішень. 2008, № 7
Таким образом в графе G′ будет всегда четное число вершин, равное
( )
( )122
2 2 +=+
−
b
r
su
. Всякое сложение kx′ и ky′ дает определенную обра-
зующую, которую можно вычислить непосредственно:
( ) ( )
3
22
+
+
−
+
=′+′
r
ji
r
yx
yx kk
kk .
Так как ( )3,2,1=λ=+ λuyx kk , а sji =+ , то получаем
( )
( )3,2,13
2
=λ+
−
=′ λ
λ
r
su
u .
Отсюда 32;32;32 321 +=′+=′+=′ cubuau .
Поскольку все ( )2mod1≡′λu , то согласно теореме 1 граф G′ имеет только
четные циклы и его хроматическое число равно 2. На рис.1 показано, где из (8)
реализованы пары ( ) ( )6,2,7,1 и ( )5,3 .
67 13 31 37
1 55 49 7
43 25 19 61
66 14 30 38
2 54 50 6
42 26 18 62
65 15 29 39
3 53 51 5
41 27 17 63
(1,7)
Граф G :
U = (44, 68, 80)
(2,6)
(3,5)
Граф G′
U′= (9, 13, 15)
12 3 6 7
1 10 9 2
8 5 4 11
РИС. 1. Первая группа подграфов графа G
О ХРОМАТИЧЕСКОМ ЧИСЛЕ НАТУРАЛЬНЫХ АРИФМЕТИЧЕСКИХ ГРАФОВ …
Теорія оптимальних рішень. 2008, № 7 55
Рассмотрим строение подграфов, которые соответствуют в (7) парам
( ) ( )
+
+
−
+
−+ 1
2
,1
2
,...,1,1,,
srsr
rsrs , т. е. парам ( )ji, , где первый номер
соответствует вершинам
≤≤+
+
−+−+= rj
sr
sjruriixk 1
2
,...,, 2 ( )1≥k .
Если подставить сюда sbru +=2 , то в результате получаем, что каждый под-
граф содержит b2 вершин. Сделаем для каждого подграфа перекодировку вер-
шин по формулам (9), при этом bk ≤≤1 . В результате каждый подграф пре-
вратится в граф G′ , для которого получим образующие
( ) ( )
3
22
+
+
−
+
=′+′=′λ
r
ji
r
yx
yxu kk
kk .
Так как srji +=+ , то
( )
( )3,2,1,1
2
=λ+
−
=′ λ
λ
r
su
u .
Отсюда 12,12,12,2 321 +=′+=′+=′=′ cubuaubn . Это нормированный
NA-граф, у которого все образующие – нечетные числа, поэтому по теореме 1
его хроматическое число равно 2. Соответствующие преобразования для нашего
примера показаны на рис. 2.
(8,12)
Граф G :
U = (44, 68, 80)
(9,11)
8
36 60
32
48
12
44 56 20
24
9
35 59
33
47
11 57
45 21
23
Граф G′
U′= (7, 11, 13)
1
6 5 10
8
2
7 9
3
4
РИС. 2. Вторая группа подграфов графа G
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
56 Теорія оптимальних рішень. 2008, № 7
Рассмотрим теперь подграф, который соответствует в (7) паре ( )
2
;
2
ss .
Этим числам в подграфе соответствует множество вершин графа G с кодами
2
,...,
2
,
2
2
s
ur
ss
−+ , т. е. 112 +=+
−
=′ b
r
su
n вершин. Перекодируем их по
правилу
bi
s
x
r
x ii ,...,2,1,1
2
1
=+
−=′ . (10)
Найдем теперь образующие данного графа
r
s
r
xx
xxu
ji
jik −+
+
=′+′=′ 2 .
Так как kji uxx =+ , то ( )3,2,1,2 =+
−
=′ k
r
su
u k
k .
Окончательно получаем граф G′ с параметрами 1+=′ bn , 21 +=′ au ,
22 +=′ bu , 23 +=′ cu . Из определения r следует, что
( ) ( ) 1,, 1223 =−−=′−′′−′ abbcНОДuuuuНОД . Поэтому граф G′ связен и являет-
ся нормированным NA-графом, у которого не все образующие равны ( )2mod0 .
Из множества решений (7) остался еще один тип подграфа, соответствую-
щий паре
++
2
,
2
rsrs
. Коды вершин этого подграфа образуют последователь-
ность
( )
2
12
,...,
2
3
,
2
srbsrsr +−++
, число которых равно b . Перекодируем
вершины этого подграфа по правилу
( )bi
sr
x
r
x ii ,...,2,1,1
2
1
=+
+
−=′ , (11)
отсюда выведем значения образующих
( ) ( )3,2,1,12
1
=+
−
=+
+
−+=′+′=′ k
r
su
r
sr
xx
r
xxu k
jijik .
В результате получаем граф G′ с параметрами bn =′ , 11 +=′ au , 12 +=′ bu ,
13 +=′ cu . Так же, как и выше, этот граф G′ является связным нормированным
NA-графом, у которого не все образующие равны ( )2mod0 . Преобразования для
двух последних графов показаны на рис. 3.
О ХРОМАТИЧЕСКОМ ЧИСЛЕ НАТУРАЛЬНЫХ АРИФМЕТИЧЕСКИХ ГРАФОВ …
Теорія оптимальних рішень. 2008, № 7 57
1
6 4
5
2 3
Граф G′ : U ′= (5, 7, 8)
1
3 5
4 2
Граф G′ : U ′= (4, 6, 7)
(4,4)
Граф G :
U = (44, 68, 80)
(10,10)
4
64 40
52
16 28
10
34 58
46 22
РИС. 3. Последние два подграфа графа G
Этим и завершается доказательство данной теоремы. Из рисунков 1–3 вид-
но, что для нашего графа подтверждается справедливость леммы 3. На рис. 3
показан единственный треугольник исходного графа G .
Теорема 3. Хроматическое число NA-графов с тремя образующими равно 2
или 3.
Доказательство. Как следует из теоремы 2, все нормированные NA-графы с
тремя образующими представляют собой набор компонент, из них либо некото-
рые, либо все имеют хроматическое число 2, а остальные сводятся к нормиро-
ванным NA-графам, у которых не все ( ) ( )3,2,12mod1 =≡ iui . Нам необходимо
рассмотреть только такие графы и доказать, что их хроматическое число мень-
ше 4. Если граф не содержит вершины со степенью больше 2, то его хроматиче-
ское число равно 2. Если он содержит вершины со степенью 3, то это возможно
при условии, что код вершины nu −3 меньше кода вершины 11 −u , а для нор-
мированного графа, учитывая значение 12 += nu , это равносильно
2321 ≥−+ uuu . (12)
Если две из образующих нечетные, то по лемме 3 граф содержит единст-
венную треугольную грань, одна из вершин которого имеет код
( )
2
321 uuu
x
−+
= . Следовательно, хроматическое число таких графов не
меньше 3. Если в нормированном NA-графе только одна из трех образующих
нечетная и выполняется условие (12), то граф может содержать нечетные циклы
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
58 Теорія оптимальних рішень. 2008, № 7
длиной 5 и больше. Предположим, что при раскраске графа тремя красками од-
на из вершин (критическая) не может быть окрашена. Такая ситуация показана
на рис. 4, где соседние к критической вершине x вершины окрашены в цвета
βα, и γ . Выделим двухцветную компоненту графа αβG , в которую входят
вершины 321 ,, xxx и 4x .
γ
x γ
γ x 1 x 5
x 3 α
β
α x 4 β x 2
α
β
РИС. 4. Граф с критической вершиной x
Если αβG несвязен, то в компоненте, содержащей вершину 1x , поменяем
местами цвета α и β , после чего вершина 1x приобретет цвет β и x можно ок-
расить цветом α . Поэтому будем считать, что все двухцветные компоненты
αβG , αγG и βγG связны, и никакая перекраска не приведет к изменению ситуа-
ции на рис. 4. Возьмем любую двухцветную компоненту, к примеру, αβG и рас-
смотрим в ней наименьший цикл, соединяющий вершины 1x и 3x . Этот цикл
единственный, так как при первом разветвлении можно его разорвать, окрасив
точку разветвления в цвет γ . Очевидно, что вместе с вершиной x это будет цикл
нечетной длины. Если в нем хотя бы одна вершина имеет степень 2, то окраши-
вая ее в цвет γ , мы добиваемся несвязности подграфа αβG , что позволит полу-
чить правильную раскраску вершины x. Поэтому будем считать, что все верши-
ны цикла имеют степень 3 и окрашены в цвета α и β, а все вершины, смежные с
циклом – в цвет γ. Если хотя-бы одна такая вершина окрашена в цвет α или β,
то тогда соответствующую вершину цикла можно перекрасить в цвет γ и опять
тем самым мы разорвем цикл подграфа αβG . Таким образом, осталось рассмот-
реть случай, когда компонента αβG представляет собой единственный цикл с
вершинами степени 3, а все отходящие от цикла внешние вершины имеют цвет
γ. Так как каждой образующей соответствует опредленное ребро и при этом
О ХРОМАТИЧЕСКОМ ЧИСЛЕ НАТУРАЛЬНЫХ АРИФМЕТИЧЕСКИХ ГРАФОВ …
Теорія оптимальних рішень. 2008, № 7 59
одинаковые ребра не могут быть смежными, то это равносильно тому, что ребра
графа правильно окрашены тремя цветами.
Лемма 4. Будь-какой цикл из пяти вершин содержит вершину степени 2.
Представим противоположное, что существует цикл из пяти вершин и все
их степени равны 3 (рис. 5).
y1
y5
y2
y4 y3
y6
u1
u2
u3
РИС. 5. Цикл из пяти вершин
Из рис. 5 следует 115 yuy −= , 113534 yuuyuy +−=−= , =−= 423 yuy
1132 yuuu −+−= . С другой стороны, 122 yuy −= , =−= 233 yuy
123 yuu +−= , 1231316 yuuuyuy −+−=−= . Отсюда следует равенство
63 yy = , что невозможно, поэтому вершина 6y не существует и степень верши-
ны 3y равна 2. Представим теперь, что в графе все нечетные циклы имеют
больше пяти вершин.
Лемма 5. В цикле нечетной длины, ребра которого правильно раскрашены
тремя цветами 1, 2 и 3 всегда найдется последовательность из четырех ребер,
крайние из которых раскрашены одинаково.
Доказательство. Для пяти вершин это следует из леммы 4. Пусть число
вершин цикла больше пяти. Предположим противное, что такой последователь-
ности не существует. Выделим все ребра цвета 3. Если между какими-то бли-
жайшими из них лежат два ребра, то проблема решена. Путем стягивания двух
соседних ребер добьемся, чтобы между ближайшими ребрами цвета 3 находи-
лось больше двух других ребер, при этом четность длины цикла не изменится. В
силу нечетности длины цикла найдется такое ребро цвета 3, которое имеет сосе-
дями ребра цвета 1 и 2. Если продолжить в лево и вправо последовательность,
то получим цвета 1321 или 2312, что и требовалось доказать.
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
60 Теорія оптимальних рішень. 2008, № 7
РИС. 6. Подграф αβG
Для доказательства теоремы 3 используем лемму 5, что дает нам 2 варианта
рис. 6. В цикле нечетной длины больше пяти вершин находим четыре ребра, со-
ответствующие образующим 3123 ,,, uuuu . По построению, если вершина x в
цикле из шести вершин, то xuuuxxuuu −+−===+− 13265231 . Если нижняя
вершина от 5x имеет цвет )(βα , то взаимно меняя цвета в вершинах )( 24 xx и
)( 65 xx , получим разрыв компоненты αβG . Если вершина x принадлежит ос-
тавшейся части цикла, то вершины 3y и 5y окрашены в один цвет и в зависи-
мости от цвета нижней к 6y вершине можна так перекрасить вршины
653 ,, yyy , что получим разрыв компоненты αβG . Это и завершает доказатель-
ство теоремы 3.
Г.П. Донець, І.Е. Шулінок
ПРО ХРОМАТИЧНЕ ЧИСЛО НАТУРАЛЬНИХ АРИФМЕТИЧНИХ ГРАФІВ З ТРЬОМА
ТВІРНИМИ
Розглядаються натуральні арифметичні графи з трьома твірними. Доводиться, що хроматичне
число таких графів дорівнює трьом.
G.A. Donets,I.E. Shulinok
ABOUT CHROMATIC NUMBER OF NATURAL ARITHMETICAL GRAPHS WITH THREE
GENERATRIXES
Natural arithmetical graphs with three generatrixes are considered. It is proved that the chromatic
number of such kind graphs is three.
1. Донец Г.А. Необходимые и достаточные условия связности арифметических графов //
Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М. Глушкова, 1989. – С. 19–24.
2. Берж К. Терия графов и ее применение. – М.: ИЛ, 1962. – 319 с.
Получено 11.04.2008
|
| id | nasplib_isofts_kiev_ua-123456789-12698 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-02T13:41:51Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Шулинок, И.Э. 2010-10-20T09:49:30Z 2010-10-20T09:49:30Z 2008 О хроматическом числе натуральных арифметических графов с тремя образующими / Г.А. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 50-60. — Бібліогр.: 2 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/12698 519.8 Рассматриваются натуральные арифметические графы с тремя образующими. Доказывается, что хроматическое число этих графов равно трем. Розглядаються натуральні арифметичні графи з трьома твірними. Доводиться, що хроматичне число таких графів дорівнює трьом. Natural arithmetical graphs with three generatrixes are considered. It is proved that the chromatic number of such kind graphs is three. ru Інститут кібернетики ім. В.М. Глушкова НАН України О хроматическом числе натуральных арифметических графов с тремя образующими Про хроматичне число натуральних арифметичних графів з трьома твірними About chromatic number of natural arithmetical graphs with three generatrixes Article published earlier |
| spellingShingle | О хроматическом числе натуральных арифметических графов с тремя образующими Донец, Г.А. Шулинок, И.Э. |
| title | О хроматическом числе натуральных арифметических графов с тремя образующими |
| title_alt | Про хроматичне число натуральних арифметичних графів з трьома твірними About chromatic number of natural arithmetical graphs with three generatrixes |
| title_full | О хроматическом числе натуральных арифметических графов с тремя образующими |
| title_fullStr | О хроматическом числе натуральных арифметических графов с тремя образующими |
| title_full_unstemmed | О хроматическом числе натуральных арифметических графов с тремя образующими |
| title_short | О хроматическом числе натуральных арифметических графов с тремя образующими |
| title_sort | о хроматическом числе натуральных арифметических графов с тремя образующими |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/12698 |
| work_keys_str_mv | AT donecga ohromatičeskomčislenaturalʹnyharifmetičeskihgrafovstremâobrazuûŝimi AT šulinokié ohromatičeskomčislenaturalʹnyharifmetičeskihgrafovstremâobrazuûŝimi AT donecga prohromatičnečislonaturalʹniharifmetičnihgrafívztrʹomatvírnimi AT šulinokié prohromatičnečislonaturalʹniharifmetičnihgrafívztrʹomatvírnimi AT donecga aboutchromaticnumberofnaturalarithmeticalgraphswiththreegeneratrixes AT šulinokié aboutchromaticnumberofnaturalarithmeticalgraphswiththreegeneratrixes |