Программная реализация метода решения систем уравнений в классах вычетов по модулю 3

Программная реализация метода решения систем уравнений в классах вычетов по модулю 3

Рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками.

Збережено в:
Бібліографічні деталі
Дата:2013
Автор: Павленко, В.Б.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Назва видання:Теорія оптимальних рішень
Онлайн доступ:http://dspace.nbuv.gov.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
id irk-123456789-85044
record_format dspace
spelling irk-123456789-850442015-07-19T03:02:30Z Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 Павленко, В.Б. Рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками. Розглядається підхід, який може бути корисним при вирішенні задачі про розфарбовування плоских графів чотирма фарбами. The article proposes an approach that can be useful in solving the problem of coloring planar graphs with four colors. 2013 Article Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 71-76. — Бібліогр.: 5 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85044 519.1 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками.
format Article
author Павленко, В.Б.
spellingShingle Павленко, В.Б.
Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
Теорія оптимальних рішень
author_facet Павленко, В.Б.
author_sort Павленко, В.Б.
title Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
title_short Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
title_full Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
title_fullStr Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
title_full_unstemmed Программная реализация метода решения систем уравнений в классах вычетов по модулю 3
title_sort программная реализация метода решения систем уравнений в классах вычетов по модулю 3
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2013
url http://dspace.nbuv.gov.ua/handle/123456789/85044
citation_txt Программная реализация метода решения систем уравнений в классах вычетов по модулю 3 / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 71-76. — Бібліогр.: 5 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT pavlenkovb programmnaârealizaciâmetodarešeniâsistemuravnenijvklassahvyčetovpomodulû3
first_indexed 2025-07-06T12:12:31Z
last_indexed 2025-07-06T12:12:31Z
_version_ 1836899580565782528
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

Схожі ресурси