Алгоритмы раскраски плоских графов
Two algorithms for colouring a maximal planar graphs (plane triangulation) with four colours are proposed . The first algorithm is based on solving system of linear equations by the module 2, which finds one variant of colorings. The second algorithm is based on solving system of linear inequalities...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2006 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84965 |
| 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: | Алгоритмы раскраски плоских графов / Г.А. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 136-144. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860093847869063168 |
|---|---|
| author | Донец, Г.А. |
| author_facet | Донец, Г.А. |
| citation_txt | Алгоритмы раскраски плоских графов / Г.А. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 136-144. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Two algorithms for colouring a maximal planar graphs (plane triangulation) with four colours are proposed . The first algorithm is based on solving system of linear equations by the module 2, which finds one variant of colorings. The second algorithm is based on solving system of linear inequalities by the module 3, which finds all variants of colorings.
|
| first_indexed | 2025-12-07T17:24:52Z |
| format | Article |
| fulltext |
136 Теорія оптимальних рішень. 2006, № 5
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Предлагаются два алгоритма рас-
краски максимальных плоских
графов (плоских триангуляций)
четырьмя цветами. Первый алго-
ритм основан на решении систе-
мы линейных уравнений по модулю
2 и находит один вариант рас-
краски. Второй алгоритм основан
на решении системы линейных
неравенств по модулю 3 и нахо-
дит все варианты раскрасок.
Г.А. ДОНЕЦ, 2006
ÓÄÊ 519.1
Ã.À. ÄÎÍÅÖ
ÀËÃÎÐÈÒÌÛ ÐÀÑÊÐÀÑÊÈ
ÏËÎÑÊÈÕ ÃÐÀÔÎÂ
Введение. Известно, что задача о нахожде-
нии хроматического числа графов принадле-
жит к числу NP-полных проблем. Алгоритмы
раскраски плоских графов в 4 цвета в лите-
ратуре встречались редко. Есть описание
псевдоалгоритма в [1], и там же упоминается
о программе раскраски, созданной для сис-
темы Хивуда [2]. Алгоритм раскраски пло-
ских триангуляций, основан на простом пе-
реборе всех вариантов, был реализован и
описан в [3]. Там же была описана гипотеза о
том, что число раскрасок f(n) n-вершинной
четырехсвязной плоской триангуляции удов-
летворяет соотношению
( )
33
8
11
4
5
−−
≤≤
nn
nf . (1)
В дальнейшем, за редким исключением,
практические расчеты показали устойчи-
вость этих границ.
1. Вывод канонической системы урав-
нений. Рассмотрим максимальный четырёх-
связной плоский граф G (плоская триангуля-
ция). По теореме Татта [4] рассматриваемый
граф G является гамильтоновым. Гамильто-
нов цикл делит граф на две области, которые
обозначим R1 и R2. Рассмотрим случай, когда
R1 и R2 – линейная последовательность тре-
угольных граней (рис. 1). Правильной рас-
краске плоской триангуляции четырьмя
красками соответствует такая раскраска рё-
бер тремя красками, когда рёбра каждой тре-
угольной грани раскрашены тремя цветами.
Если обозначить номера цветов цифрами 0,
1, и 2, то их двоичная запись будет (00), (01),
(10).
АЛГОРИТМЫ РАСКРАСКИ ПЛОСКИХ ГРАФОВ
Теорія оптимальних рішень. 2006, № 5 137
РИС. 1. Две области плоской триангуляции
Пусть xi(yi), i = 1,2,3 – первый (второй) разряд записи номеров цвета для любо-
го треугольника. Тогда раскраска ребер будет эквивалентна решению системы
для каждой треугольной грани графа
2mod
0
1
1
332211
321
321
≡≡≡
=++
=++
yxyxyx
yyy
xxx
. (2)
Занумеруем рёбра гамильтонова цикла последовательно по часовой стрелке.
Как видно из рис.1, внутренние рёбра области R1 естественно упорядочиваются.
Будем называть переменные yi, соответствующими ребрам гамильтонова цикла,
двойственными к xi. Обозначим переменные для внутренних рёбер ( )jj aa ′ . Их
легко выразить через переменные xi и yi по (2). Возрастающей последовательно-
сти переменных ( )jj aa ′ однозначно соответствует определённая последователь-
ность рёбер гамильтонова цикла. Эту последовательность легко определить:
S = (1, 2, 3, 13, 12, 4, 5, 6, 11, 10, 7, 8, 9). Обозначим is (или is′ ) сумму первых i
членов этой последовательности для переменных x (соответственно y). Тогда
можно записать систему
.;
;1;1
;1;1
;;
;;
;1;1
1391213912
12111211
22122212
122122
3232
2121
syasxa
sasa
sasa
sasa
sasa
sasa
kkkk
kkkk
′==′==
+′=′+=
+′=′+=
′=′=
′=′=
+′=′+=
++++
++
LLLLLLLLLLLLLL
LLLLLLLLLLLLLL
(3)
3 4 5 6 7
+ + 0 0 +
2 0 – 8
– 0 – + – 0
+ – 0 + – +
1 + + 0 0 9
13 12 11 10
R1
a
8 9 10
7 – + 0 11
+ 0 0
– + – + –
0 – 0 0 – + 12
6 0 + + 0 + +
5 4 3 2 1 13
R2
б
Г.А. ДОНЕЦ
138 Теорія оптимальних рішень. 2006, № 5
Используя последнее уравнение в (2), получим систему уравнений:
2mod
11
1
1
11
1
11
1313
12121212
4444
33
2222
≡′+
≡′+′+
≡′+′+
≡′+
≡′+′+
≡+
ss
ssss
ssss
ss
ssss
yx ii
LLLLLLL
. (4)
Назовём эту систему основной для R1. Произведение всех равенств даёт со-
отношение для разрешающего полинома в виде
( ) ( )2mod1,1 ≡YXF . (5)
Если найдётся такая пара векторов (X,Y), которая удовлетворяет (5), то тем
самым получим решение системы (4), что задаёт некоторую раскраску рёбер
области R1. Если в области R2 заштриховать треугольник, основой которого есть
ребро 9, то область R2 разобьётся на две части, которым соответствуют две по-
следовательности рёбер P = (6, 7, 5, 8, 4, 3) и Q = (11, 12, 13, 1, 10, 2). Так же,
как и для области R1, определим систему уравнений типа (4) и найдём для об-
ласти R2 разрешающий полином ( ) ( )2mod1,2 ≡YXF . Объединяя оба полинома и
подставляя xi вместо ( )1>kx
k
i , получим разрешающий полином для всего графа
( ) ( ) ( ) ( )2mod1,,, 21 ≡≡⋅ YXFYXFYXF . (6)
Выделим в этом полиноме слагаемые, которые не содержат переменные yi, и
обозначим их A1(G). Очевидно, что для области R1
( ) .1210421 ssssGA K= (7)
Используем свойство умножения ( ) ( )2mod1++≡ baaab . Тогда =1210ss
( ) ( )11 8710121010 ++=++= xxssss . Продолжая эту операцию и заменяя единицу
чертой отрицания, получим окончательно
( ) ( ) ( )( )( ) ( )( )87101165412131211 xxxxxxxxxxxxGA ++++++= . (8)
По аналогии для области R2 получим полином
( ) ( ) ( )( )( ) ( )( )21011312113485762 xxxxxxxxxxxxGA ++++++= . (9)
Если обозначить A(G) = A1(G) A2(G), то это и будет та часть полинома (6),
которая не содержит переменных yi. Запишем A1(G) и A2(G) в виде последова-
тельностей индексов переменных
B1 = ( ) ( )( )( )( )( )8,710,116,54,1213,32,1 ; B2 = ( ) ( ) ( ) ( ) ( ) ( )2,101,1312,113,48,57,6 .
Составим последовательности пар таким образом, чтобы конец предыдущей
пары совпадал с началом следующей, хотя при этом придётся некоторые пары
АЛГОРИТМЫ РАСКРАСКИ ПЛОСКИХ ГРАФОВ
Теорія оптимальних рішень. 2006, № 5 139
записывать в обратном порядке. При этом пары будут попеременно принадле-
жать B1 и B2.
1) ( ) ( )( )( ) ( )( )( )( )1,1313,33,44,1212,1111,1010,22,1 ; 2) ( )( ) ( )( )5,88,77,66,5 . (10)
Обе последовательности являются циклами, которым в выражении A(G) со-
ответствуют циклические произведения. Пользуясь вышеупомянутым свойством
умножения, нетрудно показать, что такое выражение тождественно равно
( )2mod0 .
Предположим теперь, что для любого числа двойственных переменных,
меньшего k, коэффициенты при наборе этих переменных в разложении полино-
ма (5) тождественно равны ( )2mod0 . Рассмотрим коэффициент при наборе k
переменных ( )
kiii yyyN ,,,
21
K . Не нарушая общности, будем полагать, что в по-
следовательности S этому набору соответствуют места с номерами ksss ,,, 21 K ,
расположенные в порядке возрастания. Аналогично, пусть в последовательно-
стях P и Q им соответствуют номера p1 < p2 . . . < pl; q1 < q2 < . . . < qm (l > 0,
m > 0; l + m = k ). В работе [5] доказана следующая
Теорема 1. Если для набора переменных
kiii yyy ,,,
21
K не выполняется хотя
бы одно условие
( ) ( )2mod1+≡≡≡ jqps jjj , (11)
то ( ) ( )2mod0,,,
21
≡
kiii yyyN K .
В зависимости от значений j будем называть вхождение переменной в
набор N четным или нечетным.
2. Каноническая система неравенств. Вернёмся к графу, у которого двой-
ственные графы в областях R1 и R2, на которые естественным образом разбива-
ется плоская триангуляция гамильтоновым циклом, являются цепями, или ли-
нейными графами (рис. 2).
РИС. 2. Граф для системы неравенств
Выделим в R1 треугольник, две стороны которого принадлежат гамильтоно-
ву циклу (опорный треугольник), и занумеруем их 1 и 2. После этого внутренние
ребра и треугольники можно упорядочить естественным путем. Продолжим ну-
3 4 6 7
2 10
1 9
5 8
a
7 10 9
6 8
4 5
3 2 1
б
Г.А. ДОНЕЦ
140 Теорія оптимальних рішень. 2006, № 5
мерацию ребер гамильтонова цикла в том же порядке. В результате получаем
нумерацию на рис.2, а. Затем перенесем эту нумерацию на область R2 (рис.2, б).
Любой правильной раскраске вершин графа G соответствует такая раскрас-
ка в три цвета его ребер, что в каждом треугольнике все три ребра имеют разные
цвета, которые обозначим 0, 1 и –1.
Пусть xi – цвет ребра под номером i гамильтонова цикла. Тогда для первых
двух ребер справедливо
x1 x2(mod 3). (12)
Пусть aj, (j = 1, 2,..., n – 2) – переменные, соответствующие цветам внутрен-
них ребер. Тогда для правильной раскраски
( ) ( )3mod211 xxa −−≡ .
В следующем треугольнике x3 a1(mod 3) и тогда
x1 + x2 + x3 0(mod 3).
Продолжая те же рассуждения, получаем систему неравенств, дополненную
одним равенством:
( )3mod
0
0
0
0
0
0
0
0
0
10987654321
987654321
87654321
7654321
654321
54321
4321
321
21
≡−−+−+−+−+
≡+−+−+−+
≡−−+−+−+
≡++−+−+
≡−−+−+
≡++−+
≡−−+
≡++
≡−
+
xxxxxxxxxx
xxxxxxxxx
xxxxxxxx
xxxxxxx
xxxxxx
xxxxx
xxxx
xxx
xx
. (13)
Для области R2 получается аналогичная система, которую назовем двойст-
венной к системе (13).
( )3mod
0
0
0
0
0
0
0
0
0
58912310764
8912310764
912310764
12310764
2310764
310764
10764
764
64
≡−−+−+−+−+
≡++−+−+−+
≡−−+−+−+
≡++−+−+
≡−−+−+
≡++−+
≡−−+
≡++
≡−
xxxxxxxxxx
xxxxxxxxx
xxxxxxxx
xxxxxxx
xxxxxx
xxxxx
xxxx
xxx
xx
. (14)
АЛГОРИТМЫ РАСКРАСКИ ПЛОСКИХ ГРАФОВ
Теорія оптимальних рішень. 2006, № 5 141
Обозначим ( ).
2
0 u
u
a
ii =α
= В работе [5] доказана
Теорема 2. Решением системы (13) является вектор X, у которого
( ) ( ) ( ) ( ) ( )n
ninin
i
in uxnixx 11,1,1,1,1 121 −−=−=α−α⋅−=α−= −−−− .
Итак, для любого 0 < u < 3·2n-2 – 1 эти формулы дают решение системы (13).
Аналогичные формулы с помощью вектора β можно получить и для системы
(14), полагая
=β
jj
v
2
. Решением системы (13–14) будет такая пара (и,v), для
которой справедливы соотношения:
.1.10,1.5
,.9,1.4
,.8,.3
,.7,.2
,.6,1.1
5645
121856
1124567
67233478
7834238
β−β=+−−=α+α−
β−β=+α−β−=α−α
+β−=α−αβ+β−=α+α−
β+β−=α+α−β−β=α−α
β−β=α−αβ+β−=α−
uv
u
v (15)
3. Алгоритмы раскраски графов. Здесь предлагаются два алгоритма рас-
краски плоских графов, идея которых изложена в [5]. Алгоритмы будут описаны
не в формальном, а в содержательном смысле. Они реализованы в виде про-
грамм и по ним проведены необходимые расчеты.
В качестве примера для описания первого алгоритма воспользуемся рис. 2.
Идея первого алгоритма состоит в том, чтобы найти такой набор
двойственных переменных N = { }
kiii yyy ,,,
21
K с наименьшим k, чтобы коэффи-
циент при нем C(N) 0(mod 2). В работе [5] доказана
Теорема 3. Если набор переменных N = { }
kiii yyy ,,,
21
K удовлетворяет
условиям теоремы 1, то коэффициент C(N) равен значению полинома (6),
построенного для графа, у которого ребра i1, i2,…, ik стянуты у вершину, а
вместо соответствующих переменных добавляется отрицательная черта в (8–9).
Пусть k = 0, т. е. ищется та часть полинома ( )YXF , , которая не содержит
двойственных переменных. Для этого случая уже выписаны соответствующие
формулы (10), где разбиение состоит из двух циклов. Как уже отмечалось, здесь
A(G) ≡ 0(mod 2).
Для k = 1 необходимо найти такую переменную y, чтобы ее номер
вхождения в систему был четным, и чтобы стягивание графа по соответ-
ствующему ребру не приводило к образованию полинома с нулевым значением.
В качестве yi для R1 можно брать переменную из множества (1, 2, 13, 4, 6,
10, 8) а для R2 из множества (6, 7, 8, 3, 11, 12, 1, 2). Общими для обеих областей
есть ребра 1, 2, 6, 8. Возьмем ребро 8. Получим разбиение
B1 = ( ) ( )( )( )( )( )9,710,116,54,1213,32,1 ; B2 = ( ) )4,5(7,6 3; ( ) ( )( )2,101,1312,11 .
Г.А. ДОНЕЦ
142 Теорія оптимальних рішень. 2006, № 5
В результате все переменные образуют цепь
( )( )( ) ( )( )( ) ( )( ) ( ) ( )9,7)7,6(6,55,44,1212,1111,1010,22,11,1313,3 .
В качестве решения можно взять значения: y8 = 1, yi = 0, x8 = 0; для множителей
с чертой xi = xj , а для множителей без черты – xi ≠ xj. Это дает x3 = x13 = x1 ≠ x2 =
= x10 = x11 ≠ x12 = x4 ≠ x5 = x6 = x7 = x9. Подставляя значения 0 или 1, получим два
решения, например, (x3 = x13 = x1 = 1) ≠ (x2 = x10 = x11 = 0) ≠ (x12 = x4 = 1) ≠ (x5 =
= x6 = x7 = x9 = 0).
Это решение приведено на рис.1, где цвета обозначены знаком "+", "–" и 0.
Нетрудно проверить, что это решение справедливо для R1 и для R2 .
Рассмотрим второй алгоритм, основанный на решении системы неравенств.
Для примера возьмем граф на рис. 2. В результате его работы находятся все
решения задачи. Хотя в качестве примера выбран линейный случай, общий
случай не намного сложнее, но для иллюстрации он почти ничего не добавляет.
Общее число решений для одной области равно 223 −⋅ n , или для нашего
примера 76823 8 =⋅ . Будем искать такие пары значений 0 ≤ u, v ≤ 767, которые
удовлетворяют системе уравнений (15). В области R1 зафиксируем первые два
значения x1 = 1, x2 = 0, что равносильно α8 = 0. Перейдем к пошаговому
изложению алгоритма, пользуясь формулой αi – αi+1 =
+
−
+12
2
i
i
u
.
x1 = 1 =
+
3
2
2
2v
. В области R1 [ ].127,0∈u
В области R2 x1 = 1 для v ∈ [4,12) + 24k, где максимальное значение
k = 31
24
12767
=
−
. Круглые скобки в дальнейшем означают, что переменная не
принимает правое значение. В итоге получаем
u ∈ [0,127], v ∈ [4,12) + 24k, (k = 0, 1, ..., 31).
x2 = 0 =
+
−
4
3
2
2v
. В области R1 границы u не меняются. В области R2
x2 = 0 для v ∈ [– 8,8) + 48k. Общий интервал с п. 1 равен [4, 8). Максимальное
k = 15
48
8767
=
−
. После двух шагов решение принадлежит множествам
u ∈ [0,127], v ∈ [4,8) + 48k, (k = 0, 1, ..., 15).
x3 = .
2
2
2
2
4
3
7
6
+
=
+ vu
АЛГОРИТМЫ РАСКРАСКИ ПЛОСКИХ ГРАФОВ
Теорія оптимальних рішень. 2006, № 5 143
[ )
[ ]
∈
∈
=
127,64,1
64,0,0
3
u
u
x ;
[ )
[ )
[ )
.96
.80,48,1
,48,16,1
,16,16,0
3 k
v
v
v
x +
∈−
∈
−∈
=
В R1 x3 = 0 для u ∈ [0,64), в R2 то же значение для интервала [ ){ }∩+ k488,4
[ ){ } [ ) kk 968,49616,16 +=+−∩ . Аналогично x3 = 1 для u ∈ [64,127], в области R2
для интервала [ ){ } [ ){ }=+−∩+∈ kkv 9616,16488,4 Ø. В результате множество
решений сужается до u ∈ [0,64), v ∈ [4,8) + 96k, (k = 0, 1, ..., 7).
x4 = .
2
1
2
2
86
5
−=
+
−
vu
[ )
[ ]
∈−
∈
=
63,32,1
32,0,0
4
u
u
x ;
[ )
[ )
[ ]
∈−
∈
∈
=
.767,512,1
,512,256,1
,256,0,0
4
v
v
v
x
u ∈ [0,32) ⇒ v ∈ {[4,8) + 96k} ∩ [256,512),
u ∈ [32,63] ⇒ v ∈ {[4,8) + 96k} ∩ [512,767].
Окончательное множество:
u ∈ [0,32), v ∈ [292,296) + 96k, (k = 0, 1, 2),
u ∈ [32,63], v ∈ [580,584) + 96k, (k = 0, 1).
u ∈ [8,12) ⇒ v = {[64,192) + 384l} ∩ {292,295] = Ø,
u ∈ [12,16) ⇒ v = {[192,320) + 384l} ∩ {292,295} = {292,295}.
Аналогично проверяя интервалы значений для x5, x6 и x7, получаем
u ∈ [16,20) ⇒ v = {[192,320) + 384l} ∩ {294 = {294},
u ∈ [20,24) ⇒ v = {[– 64,64) + 384l} ∩ {294 = Ø,
u ∈ [24,28) ⇒ v = {[– 64,64) + 384l} ∩ {390,486} = {390},
u ∈ [28,32) ⇒ v = {[64,192) + 384l} ∩ {390,486} = {486},
u ∈ [32,36) ⇒ v = {[64,192) + 384l} ∩ {582} = Ø,
u ∈ [36,40) ⇒ v = {[192,320) + 384l} ∩ {582} = {582},
u ∈ [40,44) ⇒ v = {[192,320) + 384l} ∩ {678} = {678},
u ∈ [44,48) ⇒ v = {[– 64,64) + 384l} ∩ {678} = Ø,
u ∈ [48,52) ⇒ v = {[– 64,64) + 384l} ∩ {677} = Ø,
u ∈ [52,56) ⇒ v = {[64,192) + 384l} ∩ {677} = Ø.
x8 = .
22
2
2
v
vu
+
−=
+
−
Для v осталось только семь точек, поэтому можно проверить это равенство
непосредственно. Сопоставим значения:
.0000011
678582486390294295292
8 −=
=
x
v
Г.А. ДОНЕЦ
144 Теорія оптимальних рішень. 2006, № 5
Аналогично для u:
.110110110
.4342,4138,3736,3130,2926,2524,1918,1714,1312
8 −−−=
−−−−−−−−−=
x
u
Сравнивая u и v, получим для проверки только три точки.
(14, 15) → 292, (24, 25) → 390, (36, 37) → 582.
x9 = .
2
2
2 2
+
−=
−
vu
u
Решая это уравнение, находим три решения (15, 292),(25, 390) и (37, 582).
Благодаря перестановке трех цветов можно получить еще пять решений для
переменной u: 15 → (240, 271, 496, 527, 752); 25 → (230, 281, 486, 537, 742);
37 → (218, 293, 474, 549, 730). Аналогичные решения получим для v: 292 →
(731, 548, 219, 36, 475); 390 → (633, 646, 121, 134, 377); 582 → (441, 70, 697, 326, 185).
Этим и исчерпываются все 18 решений данного примера. Если зафикси-
ровать только одно значение x1 = 1, то получим 6 решений. Это число
соответствует высказанной гипотезе, для которой при n = 10 получаем
4,2 < 6 < 10,5.
Г.П. Донець
АЛГОРИТМИ РОЗФАРБУВАННЯ ПЛОСКИХ ГРАФІВ
Пропонуються два алгоритми розфарбування максимальних плоских графів (плоских тріан-
гуляцій) чотирма кольорами. Перший алгоритм ґрунтується на розв’язанні системи лінійних
порівнянь за модулем 2 і знаходить один варіант розфарбування. Другий алгоритм грунтуєть-
ся на розв’язанні системи лінійних нерівностей за модулем 3 і знаходить всі варіанти розфар-
бувань.
G.A. Donets
ALGORITHMS FOR COLOURING PLANAR GRAPHS.
Two algorithms for colouring a maximal planar graphs (plane triangulation) with four colours
are proposed . The first algorithm is based on solving system of linear equations by the module 2,
which finds one variant of colorings. The second algorithm is based on solving system of linear
inequalities by the module 3, which finds all variants of colorings.
1. Зыков А.А. Теория конечных графов. – Новосибирск: Наука, 1969. – 543 с.
2. Sykow A.A., Kesselmen D.Ja., Neimark Ju.J., Podcorytov W.N. Ube rein verfahren zur far-
bung ebenen triangulationen // Math. Nachrichte, – 1969. – 40. – S. 51–59.
3. Донец Г.А., Шор Н.З. О задаче четырёх красок // Математика сегодня. – Киев: Вища
школа, 1983. – С. 34–55.
4. Tutte W.T. On hamilton circuits // J. London Math. Soc. – 1946, – 21. – P. 98–101.
5. Донец Г.А., Шор Н.З. Алгебраический подход к проблеме раскраски плоских графов.
– Киев: Наук. думка, 1981. – 143 с.
Получено 11.07..2006
|
| id | nasplib_isofts_kiev_ua-123456789-84965 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:24:52Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. 2015-07-17T17:11:55Z 2015-07-17T17:11:55Z 2006 Алгоритмы раскраски плоских графов / Г.А. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 136-144. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84965 519.1 Two algorithms for colouring a maximal planar graphs (plane triangulation) with four colours are proposed . The first algorithm is based on solving system of linear equations by the module 2, which finds one variant of colorings. The second algorithm is based on solving system of linear inequalities by the module 3, which finds all variants of colorings. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Алгоритмы раскраски плоских графов Algorithms for colouring planar graphs Article published earlier |
| spellingShingle | Алгоритмы раскраски плоских графов Донец, Г.А. |
| title | Алгоритмы раскраски плоских графов |
| title_alt | Algorithms for colouring planar graphs |
| title_full | Алгоритмы раскраски плоских графов |
| title_fullStr | Алгоритмы раскраски плоских графов |
| title_full_unstemmed | Алгоритмы раскраски плоских графов |
| title_short | Алгоритмы раскраски плоских графов |
| title_sort | алгоритмы раскраски плоских графов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84965 |
| work_keys_str_mv | AT donecga algoritmyraskraskiploskihgrafov AT donecga algorithmsforcolouringplanargraphs |