Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
Рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками. Розглядається підхід, який може бути корисним при вирішенні задачі про розфарбовування плоских графів чотирма фарбами. The article proposes an approach that can be useful in solving t...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/85044 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 71-76. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860246500072751104 |
|---|---|
| author | Павленко, В.Б. |
| author_facet | Павленко, В.Б. |
| citation_txt | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 71-76. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками.
Розглядається підхід, який може бути корисним при вирішенні задачі про розфарбовування плоских графів чотирма фарбами.
The article proposes an approach that can be useful in solving the problem of coloring planar graphs with four colors.
|
| first_indexed | 2025-12-07T18:37:10Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2013 71
ÒÅÎÐIß
ÎÏÒÈÌÀËÜÍÈÕ
ÐIØÅÍÜ
Рассматривается подход, кото-
рый может быть полезным при
решении задачи о раскраске пло-
ских графов четырьмя красками.
_____________________________
В.Б. Павленко, 2013
ÓÄÊ 519.1
Â.Á. ÏÀÂËÅÍÊÎ
ÏÐÎÃÐÀÌÌÍÀß ÐÅÀËÈÇÀÖÈß
ÌÅÒÎÄÀ ÐÅØÅÍÈß
ÑÈÑÒÅÌ ÓÐÀÂÍÅÍÈÉ
 ÊËÀÑÑÀÕ ÂÛ×ÅÒΠÏÎ ÌÎÄÓËÞ 3
Введение. Рассматривается подход, который
может быть полезным при решении задачи о
раскраске плоских графов четырьмя красками.
Также в статье делается программная реализа-
ция, подтверждающая расчеты и демонстри-
рующая работу алгоритма.
Рассмотрим максимальный четырехсвяз-
ный планарный граф G. Если он правильно
раскрашен четырьмя цветами, то его ребра
можно так раскрасить тремя цветами, что в
каждой его треугольной грани все ребра бу-
дут окрашены по разному. Обозначим номе-
ра цветов цифрами 0, 1, 2, в двоичной записи
имеем: (00), (01), (10). Обозначим xi и
, 1, 2, 3
i
y i = соответственно первый и вто-
рой разряды. Тогда, раскраска ребер будет
эквивалентна решению системы уравнений
для каждого треугольника в кольце вычетов
по модулю 2 – Z2:
1 2 3
1 2 3
1 1 2 2 3 3
1(mod 2),
1(mod 2),
0(mod 2).
x x x
y y y
y x y x y x
+ + ≡
+ + ≡
≡ ≡ ≡
Назовем
i
y двойственными переменными
к
i
x [1]. По теореме Татта [2] рассматривае-
мый граф G будет гамильтоновым. Гамиль-
тонов цикл делит граф на две области 1R и
2.R Если для G построить двойственный
граф G’, то областям 1R и 2R будут соответ-
ствовать два произвольных дерева со степе-
нью ветвления 3, которые будут соединяться
друг с другом ребрами, двойственными к
ребрам гамильтонова цикла.
В.Б. ПАВЛЕНКО
72 Теорія оптимальних рішень. 2013
Пусть оба этих дерева являются простыми цепями [3]. Занумеруем ребра
гамильтонова цикла последовательно по часовой стрелке. Как видно из рис. 1,
внутренние ребра области R1 естественным образом упорядочиваются.
а б
РИС. 1. Пронумерованные области R1 и R2
Любой правильной раскраске вершин графа G соответствует такая раскрас-
ка в три цвета его ребер, что в каждом треугольнике все три ребра имеют разные
цвета, которые обозначим 0, 1, –1. Пусть xi – цвет ребра под номером i гамиль-
тонова цикла. Тогда, для первых двух ребер справедливо 1 2 (mod 3)x x≡ .
Пусть aj, (j=1,2,.., n – 2) – переменные, соответствующие цветам внутренних
ребер. Тогда, для правильной раскраски 1 1 2( )(mod 3)a x x≡ − − . В следующем
треугольнике 3 1/ (mod 3)x a≡ и тогда 1 2 3 / 0(mod 3)x x x+ + ≡ .
Продолжая те же рассуждения, получим систему неравенств, дополненную
одним равенством [4]:
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
/ 0
/ 0
/ 0
/ 0
/ 0 (mod3
/ 0
/ 0
/ 0
0
x x
x x x
x x x x
x x x x x
x x x x x x
x x x x x x x
x x x x x x x x
x x x x x x x x x
x x x x x x x x x x
− ≡
+ + ≡
+ − − ≡
+ − + + ≡
+ − + − − ≡
+ − + − + + ≡
+ − + − + − − ≡
+ − + − + − + + ≡
+ − + − + − + − − ≡
) . (1)
Для области R2 получается аналогичная система, которую назовем двойст-
венной к данной.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ…
Теорія оптимальних рішень. 2013 73
4 6
4 6 7
4 6 7 10
4 6 7 10 3
4 6 7 10 3 2
4 6 7 10 3 2 1
4 6 7 10 3 2 1 9
4 6 7 10 3 2 1 9 8
4 6 7 10 3 2 1 9 8 5
/ 0
/ 0
/ 0
/ 0
/ 0
/ 0
/ 0
/ 0
0
x x
x x x
x x x x
x x x x x
x x x x x x
x x x x x x x
x x x x x x x x
x x x x x x x x x
x x x x x x x x x x
− ≡
+ + ≡
+ − − ≡
+ − + + ≡
+ − + − − ≡
+ − + − + + ≡
+ − + − + − − ≡
+ − + − + − + + ≡
+ − + − + − + − − ≡
(mod3)
. (2)
Превратим данные неравенства в равенства и запишем их в виде матрицы А.
Пусть 7 6 0( , ( 1) , ( 1) ,..., ( 1) ,0)Tx
α α αα = − − − , 7 6 0( ,( 1) , ( 1) ,..., ( 1) ,0)Tx
β β ββ = − − − .
Перестановочная матрица Р соответствует перестановке:
1 2 3 4 5 6 7 8 9 10
4 6 7 10 3 2 1 9 8 5
S
=
или в циклическом виде (1, 4, 10, 5, 3, 7)(2, 6)(8, 9). Система (1 – 2) имеет вид:
;A X⋅ = α
1 .P A P X−⋅ ⋅ ⋅ = β (3)
Лемма. Для матрицы А системы (3) справедливо
1(mod3)A A−≡ .
Учитывая это систему (3) можно переписать в виде
;X A= ⋅ α
1 .P A P A−⋅ ⋅ ⋅ ⋅ α = β (4)
Если найдутся соответствующие значения , ,α β то можно найти решение
исходной системы (1 – 2) и соответствующую раскраску графа G. Рассмотрим
систему (1). Определитель матрицы А отличен от нуля, поэтому задавая различ-
ные значения вектора ,α всегда можно получить решения данной системы, ко-
торых будет 23 2n−⋅ в соответствии с размерностью вектора .α Поставим задачу
упорядочить решения системы (1) таким образом, чтобы параметру u пробе-
гающему значения от 0 до
23 2 1n−⋅ − , соответствовало только одно такое реше-
ние. Рассмотрим параметры вектора α в виде .
2
i i
u
α =
Теорема. Решением системы (1) является вектор Х, у которого 1 21
n
x −= − α ,
( ) ( )11
i
i n i n i
x − − −= − α − α , ( )1, 1i n= − .
В.Б. ПАВЛЕНКО
74 Теорія оптимальних рішень. 2013
Доказательство. Согласно (4) получаем решение
1x x= ;
7
2 ( 1)
а
x x= − − ;
7 6
3 ( 1) ( 1)
а а
x x= − − + − ;
…;
7 6 5 34 2 1
9 ( 1) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1)
а а а аа а а
x x= − − + − − − + − − − + − − − ; (5)
0
10 ( 1) .
а
x x= + −
Докажем равенство.
1( 1) (1 )(mod 3).iа
i i+− ≡ + α + α (6)
Если 2
i
pα = , то 1i
p+α = и тогда 2( 1) 1 (1 2 ) 1(mod3)p p p− = = + + ≡ . Ес-
ли 2 1
i
pα = + , то 1i
p+α = и тогда 2 1( 1) 1 (1 2 1 ) 1(mod3)p p p+− = − = + + + ≡ − .
Подставляя эти значения в (5) при 0 ,uα = получаем решение системы в виде:
1x x= , 2 81x x а= − + , 3 8 71x x а а= − + − , …,
9 8 7 6 5 4 3 2 11x x а а а а а а а а u= − + − + − + − + − + , 10 81 1x x а u= − + − + . (7)
Вместо х можно подставлять любое значение, которое для u равно 0, 1, – 1
с одинаковой частотой. Пусть 1 81x а= − , тогда: 2 8 7x а а= − , 3 7 6x а а= − + ,
4 6 5x а а= − , 5 5 4x а а= − + , 6 4 3x а а= − , 7 3 2x а а= − + , 8 2 1x а а= − ,
9 1x а u= − + , 10 1x u= − + .
Что и требовалось доказать.
Аналогичные формулы с помощью вектора β можно получить и для систе-
мы (2), полагая
2
j j
υ
β =
. Решением системы (1) – (2) будет такая пара ( ),u υ ,
для которой справедливы соотношения: 8 3 21 ,а− + = −β + β 8 7 4 3,а а− = β − β
7 6 5 4 ,а а− + = −β + β 6 5 81 ,а а− = − β 5 4 1 ,а а− + = − υ 4 3 8 7 ,а а− = β − β
3 2 7 6,а а− + = −β + β 2 1 1 .а а− = −β + υ
Докажем формулу 1 1
2
.
2
i
i i i
u
+ +
+
α − α =
Для этого представим
12i
u k l
+= ⋅ + .
Если 2i
l ≤ , то 1 2 .
i i
k k k+α − α = − = Если 2i
l ≥ , то 1i i+α − α =
2 1 1k k k= + − = + . И в том, и в другом случае это равно выражению в правой
части. Первое уравнение преобразуется в
2
8 3
2
1 .
2 2
u u +
− =
(8)
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ…
Теорія оптимальних рішень. 2013 75
Рассмотрим плоскую систему координат ( ),u υ и отметим на ней цело-
численные точки, удовлетворяющие этому уравнению. Для левой части равен-
ства 8 9 8 9 80 [2 , 2 ); 1 [0, 2 ); 1 [2 , 3 2 )∈ ∈ − ∈ ⋅ . Для правой части равенства:
0 [ 4, 4); 1 [4, 12); 1 [12, 20).∈ − − ∈ − ∈ Концы данных интервалов повторяются
с периодом t = 24, при этом круглые скобки означают, что правые границы не
включаются в область определения. Областям, где левые и правые части урав-
нения равны 0, соответствуют прямоугольники, левая нижняя вершина которых
имеет координаты
8 8 8(2 , 4), (2 , 20), (2 ,44)− и т. д. Рассмотрим теперь второе
уравнение (7):
7 3
8 4
2 2
.
2 2
u u + +
− =
(9)
Для левой части равенства имеем:
7 7 7 7 7 70 [ 2 ,2 ); 1 [2 ,3 2 ); 1 [3 2 ,5 2 )∈ − ∈ ⋅ − ∈ ⋅ ⋅ .
Для правой части равенства:
0 [ 8,8); 1 [8, 24); 1 [24, 40)∈ − ∈ − ∈ .
Здесь границы интервалов повторяются с периодом t = 48. Для этого урав-
нения будут свои прямоугольники, где совпадают значения правой и левой час-
тей уравнения. Решение системы необходимо искать на пересечении прямо-
угольников, построенных для первого уравнения и соответствующих прямо-
угольников второго уравнения.
В результате этих операций получим прямоугольники пересечений с осно-
ванием, равным 2
7
и разной высотой, но все с периодом t = 48. Имеем
7(0, 2 ) ( 4,4)× − ;
7 8(2 ,2 ) (20,24)× ;
8 7(2 ,3 2 ) (8,12)⋅ × ;
7 9(3 2 ,2 ) (28,36)⋅ × ;
9 7(2 ,5 2 ) (36, 40)⋅ × ;
7 8(5 2 ,3 2 ) (40, 44)⋅ ⋅ × . Вычисляя последовательно прямо-
угольники пересечений решений для последующих уравнений, получим в конце
решение системы (1) – (2).
Поставим задачу программной реализации данного алгоритма. Пусть дан
граф G, для которого построен двоистый, аналогично риc. 1. Для реализации по-
ставленной задачи воспользуемся средой программирования Visual Basic 2010
Express [5]. В верхней части программы для удобства восприятия выведены обе
области R1 и R2. В нижнем поле выводятся результаты расчетов и пояснения
программы по ним. Нажав на кнопку «Провести расчеты», в директории с про-
граммой создается файл «Record.txt», в котором хранятся расчеты программы,
которые могут быть использованы в других расчетах. При последующих выпол-
нениях программы, файл будет перезаписываться (рис. 2).
В.Б. ПАВЛЕНКО
76 Теорія оптимальних рішень. 2013
РИС. 2. Рабочая область программы
Заключение. Обработка данных, которые получаются в результате решения
очередного уравнения, с каждым шагом по объему увеличивается относительно
переменной u, но еще быстрее уменьшается относительно переменной ,υ так
как часть прямоугольников по высоте пропадает. Разработанная программа дает
решение лишь для частного случая и в дальнейшем следовало бы расширить
функционал программы и добавить возможность изменения параметров.
В.Б. Павленко
ПРОГРАМНА РЕАЛІЗАЦІЯ МЕТОДУ РІШЕННЯ СИСТЕМ РІВНЯНЬ
У КЛАСАХ ВІДРАХУВАНЬ ЗА МОДУЛЕМ 3
Розглядається підхід, який може бути корисним при вирішенні задачі про розфарбовування
плоских графів чотирма фарбами.
V.B. Pavlenko
SOFTWARE IMPLEMENTATION FOR SYSTEMS OF EQUATIONS IN THE CLASS OF
RESIDUES MODULO 3
The article proposes an approach that can be useful in solving the problem of coloring planar graphs
with four colors.
1. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.
2. Tutte W.T., Whitney H. Kempe chains and the four color problem. – Studies in Graph Theory,
Studies in Math., Math. Assoc. Amer., 1976. – С. 241 – 281.
3. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
4. Донец А.П. Теоретико-числовой подход к решению некоторых задач теории графов.
Дис. ... д-ра физ.-мат. наук. – К., 1997. – 162 с.
5. Зиборов В.В. Visual Basic 2010 на примерах. – БХВ-Петербург, 2010. – 336 с.
Получено 11.03.2013
|
| id | nasplib_isofts_kiev_ua-123456789-85044 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:37:10Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Павленко, В.Б. 2015-07-18T16:43:42Z 2015-07-18T16:43:42Z 2013 Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 71-76. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85044 519.1 Рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками. Розглядається підхід, який може бути корисним при вирішенні задачі про розфарбовування плоских графів чотирма фарбами. The article proposes an approach that can be useful in solving the problem of coloring planar graphs with four colors. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 Програмна реалізація методу рішення систем рівнянь у класах відрахувань за модулем 3 Software implementation for systems of equations in the class of residues modulo 3 Article published earlier |
| spellingShingle | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 Павленко, В.Б. |
| title | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 |
| title_alt | Програмна реалізація методу рішення систем рівнянь у класах відрахувань за модулем 3 Software implementation for systems of equations in the class of residues modulo 3 |
| title_full | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 |
| title_fullStr | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 |
| title_full_unstemmed | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 |
| title_short | Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 |
| title_sort | программная реализация метода решения систем уравнений в классах вычетов по модулю 3 |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85044 |
| work_keys_str_mv | AT pavlenkovb programmnaârealizaciâmetodarešeniâsistemuravneniivklassahvyčetovpomodulû3 AT pavlenkovb programnarealízacíâmetoduríšennâsistemrívnânʹuklasahvídrahuvanʹzamodulem3 AT pavlenkovb softwareimplementationforsystemsofequationsintheclassofresiduesmodulo3 |