Алгоритм раскраски плоских графов

Алгоритм раскраски плоских графов

Рассматривается подход к решению проблемы раскрашивания плоских графов составлением функции решения для каждой из областей путем отображения одной области на другую. Розглядається підхід до розв’язання проблеми розфарбовування плоских графів складанням функції рішення для кожної області шляхом відоб...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Теорія оптимальних рішень
Datum:2015
1. Verfasser: Павленко, В.Б.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/112398
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Алгоритм раскраски плоских графов / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 58-62. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-112398
record_format dspace
spelling Павленко, В.Б.
2017-01-20T21:28:03Z
2017-01-20T21:28:03Z
2015
Алгоритм раскраски плоских графов / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 58-62. — Бібліогр.: 3 назв. — рос.
XXXX-0013
https://nasplib.isofts.kiev.ua/handle/123456789/112398
519.1
Рассматривается подход к решению проблемы раскрашивания плоских графов составлением функции решения для каждой из областей путем отображения одной области на другую.
Розглядається підхід до розв’язання проблеми розфарбовування плоских графів складанням функції рішення для кожної області шляхом відображення однієї з областей на іншу.
The article discusses the approach to the problem coloring of planar graphs, which consists in making the decision function for each of the areas by mapping one area to another.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Теорія оптимальних рішень
Алгоритм раскраски плоских графов
Алгоритм розфарбовування плоских графів
Algorithm colorings of plane graphs
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Алгоритм раскраски плоских графов
spellingShingle Алгоритм раскраски плоских графов
Павленко, В.Б.
title_short Алгоритм раскраски плоских графов
title_full Алгоритм раскраски плоских графов
title_fullStr Алгоритм раскраски плоских графов
title_full_unstemmed Алгоритм раскраски плоских графов
title_sort алгоритм раскраски плоских графов
author Павленко, В.Б.
author_facet Павленко, В.Б.
publishDate 2015
language Russian
container_title Теорія оптимальних рішень
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Алгоритм розфарбовування плоских графів
Algorithm colorings of plane graphs
description Рассматривается подход к решению проблемы раскрашивания плоских графов составлением функции решения для каждой из областей путем отображения одной области на другую. Розглядається підхід до розв’язання проблеми розфарбовування плоских графів складанням функції рішення для кожної області шляхом відображення однієї з областей на іншу. The article discusses the approach to the problem coloring of planar graphs, which consists in making the decision function for each of the areas by mapping one area to another.
issn XXXX-0013
url https://nasplib.isofts.kiev.ua/handle/123456789/112398
citation_txt Алгоритм раскраски плоских графов / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 58-62. — Бібліогр.: 3 назв. — рос.
work_keys_str_mv AT pavlenkovb algoritmraskraskiploskihgrafov
AT pavlenkovb algoritmrozfarbovuvannâploskihgrafív
AT pavlenkovb algorithmcoloringsofplanegraphs
first_indexed 2025-11-24T16:02:38Z
last_indexed 2025-11-24T16:02:38Z
_version_ 1850850533637619712
fulltext 58 Теорія оптимальних рішень. 2015 ТЕОРIЯ ОПТИМАЛЬНИХ РIШЕНЬ Рассматривается подход к реше- нию проблемы раскрашивания плоских графов составлением функции решения для каждой из областей путем отображения одной области на другую. _____________________________  В.Б. Павленко, 2015 УДК 519.1 В.Б. ПАВЛЕНКО АЛГОРИТМ РАСКРАСКИ ПЛОСКИХ ГРАФОВ Введение. Задача о нахождении хроматиче- ского числа графов [1] является NP-полной. При этом проблема четырех красок сводится к раскраске в 3 цвета плоских графов, у ко- торых степени всех вершин равны 4. Это до- стигается путем замены в плоской триангу- ляции ребер вершинами с сохранением их смежности. Знаменитая задача о четырех красках сво- дится к решению системы уравнений в клас- сах вычетов по модулю 3. Сначала строится система для простого линейного случая, ко- гда двойственные графы в областях R1 и R2 являются цепями. Решения для каждой такой области можно упорядочить таким образом, что каждое решение (вектор Х) является функцией от номера этого решения в преде- лах от 0 до 23 2 1n  . Аналогичная система строится и для общего случая, когда двой- ственные графы к областям R1 и R2 являются деревьями со степенью ветвления 3. В этом случае также удается найти функцию, кото- рая любому числу в тех же пределах ставит в соответствие решение системы неравенств, однако эта функция может иметь достаточно много слагаемых. Задача четырех красок бу- дет решена тогда, когда будет доказано, что для областей R1 и R2 всегда найдутся два та- ких числа 20 , 3 2 1nu     , что их функ- ция решения – векторы ( )X u и ( )Y  полу- чаются один из другого путем перестановки соответствующей отображению R1 на R2. Рассмотрим максимальный четырехсвяз- ный планарный граф G на рис. 1. Если он правильно раскрашен четырьмя цветами, то его ребра можно так раскрасить тремя цве- тами, что в каждой его треугольной грани все ребра будут окрашены по разному. АЛГОРИТМ РАСКРАСКИ ПЛОСКИХ ГРАФОВ Теорія оптимальних рішень. 2015 59 а б РИС. 1. Пронумерованные области R1 и R2 Любой правильной раскраске вершин графа G соответствует такая раскрас- ка в три цвета его ребер, что в каждом треугольнике все три ребра имеют разные цвета, которые обозначим 0, 1, –1. Пусть xi – цвет ребра под номером i гамиль- тонова цикла. Тогда, для первых двух ребер справедливо 1 2(mod 3)x x . Пусть , ( 1,2, ..., 2)jа j n  – переменные, соответствующие цветам внут- ренних ребер. Как известно [2] общее число решений для одной области равно 23 2 ,n что в нашем случае 83 2 768.  Будем искать такие пары значений: 0 , 767,u   для которых справедливы соотношения: 8 3 2 8 7 4 3 7 6 5 4 6 5 8 5 4 4 3 8 7 3 2 7 6 2 1 1 1 2 1 6 5 1 , , , 1 , 1 , , , , , 1 . а а а а а а а а а а а а а а а а u u                                               (1) Если найдутся соответствующие значения ,  , то можно найти соответ- ствующую раскраску графа G [3]. В области R1 зафиксируем первые два значе- ния 1 21, 0,x x  что равносильно 8 0a  и  0,127 .u Пошагово рассмотрим дальнейшие действия. 1. 2 1 5 2 1 . 2 x          В области  1 0,127 .R  В.Б. ПАВЛЕНКО 60 Теорія оптимальних рішень. 2015 В R2 для , где максимальное значение . Тут и далее следует понимать, что круглые скобки обозначают, что переменные не принимают правое значение. Имеем: . 2. . В области R1 границы u не меняются. В области R2 для . Общий интервал с равен [4,8). Максимальное . После двух шагов решение принадлежит множествам: . 3. . . В R1 для , а в R2 тоже значение для интервала: . В результате множество решений сужается до: 4. . Окончательно имеем: 5. . Окончательно имеем: АЛГОРИТМ РАСКРАСКИ ПЛОСКИХ ГРАФОВ Теорія оптимальних рішень. 2015 61 6. . 7. 8. Для v осталось только семь точек, поэтому проверим это равенство непо- средственно, сопоставив значения: 292 295 294 390 486 582 678 = –1 1 0 0 0 0 0 Аналогично для u: u = 12 – 13 14 – 17 18 – 19 24 – 25 26 – 29 30 – 31 36 – 37 38 – 41 42 – 43 = 0 –1 1 0 –1 1 0 –1 1. В.Б. ПАВЛЕНКО 62 Теорія оптимальних рішень. 2015 Сравнивая u и v получим для проверки только три точки: 9. Решая это уравнение, находим три решения: (15,292), (25,390) и (37,582). Благодаря перестановке трех цветов можно получить еще пять решений для u: и для v: Заключение. Этим исчерпываются все 18 решений для данного примера. Если зафиксировать только одно значение 1 1,x  то получим 6 решений. Это соот- ветствует высказанной гипотезе, для которой при n = 10 получаем 4,2 < 6 < 10,5. В.Б. Павленко АЛГОРИТМ РОЗФАРБОВУВАННЯ ПЛОСКИХ ГРАФІВ Розглядається підхід до розв’язання проблеми розфарбовування плоских графів складанням функції рішення для кожної області шляхом відображення однієї з областей на іншу. V.B. Pavlenko ALGORITHM COLORINGS OF PLANE GRAPHS The article discusses the approach to the problem coloring of planar graphs, which consists in mak- ing the decision function for each of the areas by mapping one area to another. 1. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с. 2. Донец Г.А., Шор Н.З. Алгебраический подход к исследованию задачи о четырех красках // Теорія оптимальних рішень. – К.: Інститут кібернетики. – 1967. – С. 23 – 29. 3. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с. Получено 27.01.2015

Ähnliche Einträge