Простой алгоритм решения системы неравенств для плоской триангуляции
Рассматривается простой алгоритм решения системы неравенств, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками.
Збережено в:
| Дата: | 2014 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/111511 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Простой алгоритм решения системы неравенств для плоской триангуляции / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 63-67. — Бібліогр.: 1 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-111511 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1115112017-01-11T03:03:32Z Простой алгоритм решения системы неравенств для плоской триангуляции Павленко, В.Б. Рассматривается простой алгоритм решения системы неравенств, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками. Розглядається простий алгоритм розв’язання системи нерівностей, який може бути корисним при вирішенні задачі про розфарбовування плоских графів чотирма фарбами. The article proposes a simple algorithm for solving a system of equations that can be useful in solving the problem of coloring planar graphs in four colors. 2014 Article Простой алгоритм решения системы неравенств для плоской триангуляции / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 63-67. — Бібліогр.: 1 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/111511 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 |
Павленко, В.Б. Простой алгоритм решения системы неравенств для плоской триангуляции Теорія оптимальних рішень |
| author_facet |
Павленко, В.Б. |
| author_sort |
Павленко, В.Б. |
| title |
Простой алгоритм решения системы неравенств для плоской триангуляции |
| title_short |
Простой алгоритм решения системы неравенств для плоской триангуляции |
| title_full |
Простой алгоритм решения системы неравенств для плоской триангуляции |
| title_fullStr |
Простой алгоритм решения системы неравенств для плоской триангуляции |
| title_full_unstemmed |
Простой алгоритм решения системы неравенств для плоской триангуляции |
| title_sort |
простой алгоритм решения системы неравенств для плоской триангуляции |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/111511 |
| citation_txt |
Простой алгоритм решения системы неравенств для плоской триангуляции / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 63-67. — Бібліогр.: 1 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT pavlenkovb prostojalgoritmrešeniâsistemyneravenstvdlâploskojtriangulâcii |
| first_indexed |
2025-07-08T02:16:09Z |
| last_indexed |
2025-07-08T02:16:09Z |
| _version_ |
1837043254575497216 |
| fulltext |
Теорія оптимальних рішень. 2014 63
ТЕОРIЯ
ОПТИМАЛЬНИХ
РIШЕНЬ
Рассматривается простой
алгоритм решения системы
неравенств, который может
быть полезным при решении
задачи о раскраске плоских
графов четырьмя красками.
В.Б. Павленко, 2014
УДК 519.1
В.Б. ПАВЛЕНКО
ПРОСТОЙ АЛГОРИТМ
РЕШЕНИЯ СИСТЕМЫ НЕРАВЕНСТВ
ДЛЯ ПЛОСКОЙ ТРИАНГУЛЯЦИИ
Введение. Для плоской триангуляции с не
очень большим количеством вершин
существует возможность быстрого
отыскания решения системы уравнений. Из
минусов можно назвать ограничение в виде
небольшого размера исследуемого графа.
Двойственный граф G’ к планарному
графу G – это граф, в котором вершины
соответствуют граням графа G; эти вершины
соединены ребром, только если
соответствующие им грани графа G имеют
общее ребро. Например, двойственны друг к
другу графы куб и октаэдр. Двойственный
граф G’ является псевдографом: в нем могут
быть петли и кратные ребра. В зависимости
от укладки, к одному и тому же графу могут
существовать несколько двойственных [1].
Рассмотрим максимальный
четырехсвязный планарный граф G. Если он
правильно раскрашен четырьмя цветами, то
его ребра можно так раскрасить тремя
цветами, что в каждой его треугольной грани
все ребра будут окрашены по разному.
Обозначим номера цветов цифрами 0, 1, 2.
Их двоичная запись будет иметь вид: (00),
(01), (10).
Обозначим xi и yi, i=1,2,3 соответственно
первый и второй разряды двоичной записи
номеров цветов для любого треугольника.
Тогда, раскраска ребер будет эквивалентна
решению системы уравнений для каждого
треугольника в кольце вычетов по модулю
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
В.Б. ПАВЛЕНКО
64 Теорія оптимальних рішень. 2014
Назовем yi двойственными переменными к xi. По теореме Татта [2]
рассматриваемый граф G будет гамильтоновым. Гамильтонов цикл делит граф
на две области R1 и R2. Если для G построить двойственный граф G’, то
областям R1
и R2 будут соответствовать два произвольных дерева со степенью ветвления 3,
которые будут соединяться друг с другом ребрами, двойственными к ребрам
гамильтонова цикла.
Рассмотрим случай, когда оба этих дерева являются простыми цепями.
Занумеруем ребра гамильтонова цикла последовательно по часовой стрелке. Как
видно из рис. 1, внутренние ребра области R1 естественным образом
упорядочиваются. Выделим в R1 треугольник, две стороны которого
принадлежат гамильтонову циклу (опорный треугольник) и занумеруем их 1 и 2.
Продолжим нумерацию ребер гамильтонова цикла в том же порядке и в
результате получим нумерацию на рис. 1, а, которую перенесем на область R2
(рис. 1, б).
а б
РИС. 1. Пронумерованные области R1 и R2
Любой правильно раскраске вершин графа G соответствует такая раскраска
в три цвета его ребер, что в каждом треугольнике все три ребра имеют разные
цвета, которые обозначим 0, 1, –1. Пусть xi – цвет ребра под номером i
гамильтонова цикла, где i находится в пределах [1, k], где x1 – первое
пронумерованное ребро, а xk – последнее [3].
Тогда, для первых двух ребер справедливо
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
ПРОСТОЙ АЛГОРИТМ РЕШЕНИЯ СИСТЕМЫ НЕРАВЕНСТВ ДЛЯ ПЛОСКОЙ ТРИАНГУЛЯЦИИ
Теорія оптимальних рішень. 2014 65
Продолжая те же рассуждения, получим систему неравенств, дополненную
одним равенством [1]:
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 получается аналогичная система, которую назовем
двойственной к данной [4]:
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)
Для графов с не очень большим количеством вершин существует
возможность быстрого отыскания решения задачи. Выведем простое правило,
относительно которого будем искать закономерности.
Правило: если два ребра опорных треугольников на области R2 имеют вид xk
и xk + 1, то такие ребра являются ненулевыми.
Само собой это далеко не все возможные варианты, а частный случай. Это
простое правило позволяет отыскивать решение задачи, не прибегая к решению
системы (1 – 2), т. е. фактически «на глазок» лишь по внешнему виду графа и
соотношениям ребер в нем, причем такое решение должно быть только одно.
Попробуем решить вышеприведенный на рис. 1 пример.
В.Б. ПАВЛЕНКО
66 Теорія оптимальних рішень. 2014
Рассмотрим двойственные графы на рис. 1. Исходя из первого неравенства
нашей системы (1) для R1 справедливо:
x1 = 1, x2 = 0.
Это опорный треугольник и потому также справедливо:
x9 = 1, x10 = 0.
Пусть x1 = 1, тогда xk = +1 для 1(mod2).k На R2 легко увидеть что x5 = +1
и значит x6 0. Как же определить значение ребра более точно?
Легко заметить, что значение ребра зависит от удаленности от опорных
треугольников. Если перебирать ребра графа от первой ненулевой компоненты
(в данном случае x1 или x9) в направлении предполагаемой ненулевой (в данном
случае x6) расположенной не на опорном треугольнике, то можно обнаружить
закономерность: если предполагаемый элемент расположен под четным
номером, то он имеет противоположное значение к x1, если нечетное, то такое
же,
как у x1.
Тогда, перебрав ребра в R1 в порядке (9, 10, 8, 7, 6), видим, что x6
расположена под нечетным пятым номером, а значит x6 = +1. Это легко
проверить по области R2: переберем ребра (6, 4, 7, 10, 3, 2, 1) видим, что x1
расположена под нечетным седьмым номером, а значит x1 = +1 (рис. 2).
Тоже справедливо и x9: для R2 (5, 8, 9, 1), для x9 = x1 = +1.
Имеем в итоге:
x1 = x5 = x6 = x9 = +1,
Х = (1, 0, 0, 0, 1, 1, 0, 0, 1, 0).
Рассмотрим другой пример. Попробуем переделить искомый граф G иначе,
получив другое разбитие G’.
а б
РИС. 2. Заново пронумерованные области R1 и R2
Здесь опорные треугольники R2 также имеют ребра вида xk и xk + 1, где k = 4,
k + 1 = 5.
Пусть x1 = +1, тогда xk = +1 для 1(mod2).х Тогда имеем, что x4 = – 1,
x5 = – 1. Считая с обратной стороны, если x9 = +1, то (9, 10, 8, 7, 6, 5)
x5 расположен под четным шестым номером и значит имеет противоположное
к x9 значение.
Имеем:
x1 = x9 = +1,
ПРОСТОЙ АЛГОРИТМ РЕШЕНИЯ СИСТЕМЫ НЕРАВЕНСТВ ДЛЯ ПЛОСКОЙ ТРИАНГУЛЯЦИИ
Теорія оптимальних рішень. 2014 67
x4 = x5 = –1,
Х = (1, 0, 0, –1, –1, 0, 0, 0, 1, 0).
Попробуем рассмотреть другой пример, где количество наших ребер будет
нечетным.
Рассмотрим пример на рис. 3. Пусть x1 = +1, тогда xk = + 1 для 1(mod2).х
Тогда имеем (6, 9, 5, 1) x6 = –1, отсюда x7 = –1. Считая с обратной стороны, если
x10 = +1, то (6, 9, 10) видим, что x7 расположен под нечетным третьим номером
и значит имеет противоположное значение.
а б
РИС. 3. Заново пронумерованные области R1 и R2
В итоге имеем:
x1= x10 = +1,
x6 = x7 = –1,
Х = (1, 0, 0, 0, 0, –1, –1, 0, 0, – 1, 0).
Правильность решения легко проверить по системе (1 – 2), просто
подставляя значения в неравенства.
Заключение. Предложенный метод позволяет относительно быстро
отыскать решение системы уравнений для плоской триангуляции причем в
заданных границах. Из минусов можно назвать ограничение в виде небольшого
размера исследуемого графа. Дальнейшие исследования следует направить в
углубление данной проблемы и построение более широкого алгоритма,
способного разрешить проблему четырех красок.
В.Б. Павленко
ПРОСТИЙ АЛГОРИТМ РІШЕННЯ СИСТЕМИ НЕРІВНОСТЕЙ ДЛЯ ПЛОСКОЇ
ТРІАНГУЛЯЦІЇ
Розглядається простий алгоритм розв’язання системи нерівностей, який може бути корисним
при вирішенні задачі про розфарбовування плоских графів чотирма фарбами.
V.B. Pavlenko
SIMPLE ALGORITHM FOR INEQUALITY FOR PLANAR TRIANGULATION
The article proposes a simple algorithm for solving a system of equations that can be useful in solv-
ing the problem of coloring planar graphs in four colors.
1. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
В.Б. ПАВЛЕНКО
68 Теорія оптимальних рішень. 2014
2. http://pco.iis.nsk.su/grapp/WIN/sl_t.html. Информационное множество (интернет-ресурс)
3. Донец Г.П. Теоретико-числовой подход к решению некоторых задач теории графов.
Диссертационная работа. – К., 1997. – 162 с.
4. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.
Получено 31.03.2014
|