Раскрашивание плоских триангуляций
В статье рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками.
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/85021 |
| 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: | Раскрашивание плоских триангуляций / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 87-91. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85021 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-850212015-07-19T03:02:20Z Раскрашивание плоских триангуляций Павленко, В.Б. В статье рассматривается подход, который может быть полезным при решении задачи о раскраске плоских графов четырьмя красками. У статті розглядається підхід, який може бути корисним при вирішенні задачі про розфарбовування плоских графів чотирма фарбами. The article proposes an approach that can be useful in solving the problem of coloring planar graphs with four colors. 2012 Article Раскрашивание плоских триангуляций / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 87-91. — Бібліогр.: 5 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85021 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 |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85021 |
| citation_txt |
Раскрашивание плоских триангуляций / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 87-91. — Бібліогр.: 5 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT pavlenkovb raskrašivanieploskihtriangulâcij |
| first_indexed |
2025-07-06T12:11:03Z |
| last_indexed |
2025-07-06T12:11:03Z |
| _version_ |
1836899492096376832 |
| fulltext |
Теорія оптимальних рішень. 2012 87
ÒÅÎÐIß
ÎÏÒÈÌÀËÜÍÈÕ
ÐIØÅÍÜ
В статье рассматривается под-
ход, который может быть по-
лезным при решении задачи о рас-
краске плоских графов четырьмя
красками.
___________________________
В.Б. Павленко, 2012
ÓÄÊ 519.1
Â.Á. ÏÀÂËÅÍÊÎ
РАСКРАШИВАНИЕ ПЛОСКИХ
ТРИАНГУЛЯЦИЙ
Введение. В статье рассматривается подход,
который может быть полезным при решении
задачи о раскраске плоских графов четырьмя
красками.
Пусть G - связный плоский граф. Любая
грань графа, ограниченная треугольником
будет называться треугольником
Определение 1. Плоский связный граф,
каждая грань которого является треугольни-
ком, называется плоской триангуляцией.
Определение 2. Граф называется макси-
мально-плоским, если после добавления про-
извольного ребра он перестает быть пло-
ским.
Лемма 1. Если число вершин некоторой
плоской триангуляции не менее 4, то степень
каждой вершины не менее 3.
Доказательство. Пусть v - произвольная
вершина плоской триангуляции G, и u - пло-
ская ей вершина. Ребро (u,v) в плоской три-
ангуляции разделяет 2 грани, следовательно,
существует x1 принадлежащий одной грани и
x2 принадлежащий другой грани. Таким об-
разом, все вершины графа G имеют степень
не менее трех.
Лемма 2. Всякий планарный граф с чис-
лом вершин не менее 4 (n >= 4) имеет по
крайней мере 4 вершины, степень которых
не превосходит 5.
Доказательство аналогично предыдуще-
му.
Теорема 1. Для того чтобы граф являлся
максимально-плоским необходимо и доста-
точно, чтобы он представлял собой плоскую
триангуляцию.
В. Б. ПАВЛЕНКО
88 Теорія оптимальних рішень. 2012
Доказательство. Необходимость. Пусть G - максимально-плоский граф, то-
гда каждая его грань ограничена либо треугольником либо циклом длины не
менее 4.
Рассмотрим грань Г ("гамма большая"), ограниченную циклом длины 5. В
графе G одновременно не могут существовать и ребро (v1,v3) и ребро (v2,v3). Т.к.
оба ребра должны быть вне грани Г, то они обязательно будут пересекаться, что
противоречит факту, что G - плоский.
Пусть в G существует ребро (v2,v3). Добавим в граф ребро (v1,v3), проходящее
внутри грани Г и разбивающее ее на 2 грани, и полученный граф останется пло-
ским. Но тогда G не максимально-плоский граф, следовательно все грани графа
G - треугольники, а G - плоская триангуляция.
Достаточность. Пусть G - плоская триангуляция. Соединим любые 2 вер-
шины грани Г ребром, разбивающим эту грань на 2 грани. В этом случае, когда
грани являются треугольниками это невозможно, следовательно граф G - мак-
симально-плоский.
Следствие 1. Всякий плоский граф является некоторым подграфом плоской
триангуляции.
Следствие 2. Для любого максимально-плоского графа верно неравенство: m
= 3n - 6.
Свойства раскрашенных плоских триангуляций. Рассмотрим плоскую
триангуляцию, вершины которой правильно раскрашены 4 красками (никакие 2
смежные вершины не окрашены одинаково). Пусть { , , , }Z α β γ δ= - множество
цветов. Подграф, образованный на множестве вершин цвета s и t ( ,s Z∈ s t≠ )
будем называть бихроматическим графом Gst, где p(Gst) – число компонент
связности, ( )
st
Gλ – цикломатическое число графа.
Рассмотрим граф на рисунке. Как видим, граф раскрашен 4-мя красками та-
ким образом, что вершины по краям треугольной грани принадлежат бихрома-
тическому подграфу и только одна грань его не треугольна. Назовет такой граф
мозаикой с внешними цветами s и t и обозначим M(s,t).
РИСУНОК. Мозаика M(s,t)
Лемма 3. Для всякой мозаики имеет место:
1) ( ) ( )
st uv
G p Gλ = , (1)
ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПОСТРОЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА
Теорія оптимальних рішень. 2012 89
2) ( ) ( ) 1
st uv
p G Gλ= + , (2)
где { , } { , }s t u v Z∪ = .
Первое равенство очевидно для ( ) 1
st
Gλ = . Допустим, что оно справедливо
для некоего 1r ≥ : ( )
st
G rλ = . Рассмотрим ( ) 1
st
G rλ = + . В подграфе Gs,t выде-
лим мозаику M’(s,t), полученную путем склеивания одинаково окрашенных
вершин бихроматического цикла данного подграфа, для которой имеет место
'( ) '( )
st uv
G r p Gλ = = . Однако '( ) ( ) 1
uv uv
p G p G= − , откуда следует равенство
(1). Добавим к мозаике M’(s,t) внешний цикл с цветами u и v. Тогда для M(u,v)
имеем: '( ) '( ) ( )
st st st
G p G p Gλ = = . Но '( ) ( ) 1
uv uv
G Gλ λ= + , что дает соотноше-
ние (2).
Следствие. Для раскрашенной плоской триангуляции справедливо
( ) '( ) 1
st uv
p G Gλ= + , где { } { } { } { }s t u v Z∪ ∪ ∪ = . Это равенство следует из то-
го, что любую плоскую триангуляцию можно разбить на две мозаики, имеющие
лишь общий бихроматический цикл.
Лемма 4. Для раскрашенной плоской триангуляции имеют место:
1) ( ) ( ) 2
st uv
m G m G n+ = − , (3)
2) [ ( ) ( )] [ ( ) ( )] 2
st st uv uv
p G G p G Gλ λ− + − = , (4)
где { } { } { } { }s t u v Z∪ ∪ ∪ = .
Раскраска плоской триангуляции четырьмя красками сводится к решению
следующей системы уравнений:
0(mod 3),
y
i
i M
x
∈
≡∑ ,y K∈ (5)
1,
j
x = ± 1, 2,..., 2 4,j n= − (6)
где – множество треугольных граней, инцидентных вершине у, К – множество
вершин. Каждому решению системы (5-6) соответствует одна и только одна
раскраска графа (с точностью до фиксации одного треугольника) и наоборот.
Допустим, получена какая-либо раскраска. Тогда система уравнений решается
как:
1) присваиваем произвольной грани (хі) значение +1;
2) выбираем неотмеченную грань, имеющую общее ребро с отмеченной. Ес-
ли вершины противолежащие этому ребру, окрашены общим цветом, при-
своим выбранной грани знак, противоположный знаку соседней грани, в про-
тивном случае ставим тот же знак.
Продолжаем этот процесс до тех пор, пока не будут отмечены все грани. По-
лучим следующее выражение:
2 4
1
( 1)
n
i
i
g x
ε
−
=
= − = ∏ . (7)
В. Б. ПАВЛЕНКО
90 Теорія оптимальних рішень. 2012
В зависимости от того, какое значение принимает g, эпсилом может быть
четным или нечетным (при этом имеем четную или нечетную раскраску). Пусть
e=[0, 1], тогда в соответствующих случаях раскраска будет равна 0 или 1. Выбе-
рем компоненту подграфа Gst, в которой цвет s не равен цвету t и поменяем эти
цвета местами. Назовем эту операцию элементарной перекраской графа.
Лемма 5. Элементарная перекраска не меняет четности раскраски графа.
Это утверждение легко доказывается, если рассмотреть мозаику M(s,t) на ри-
сунке. Число граней любой мозаики равно: N=2n-k-2 ≡ 0(mod 2), так как k-четное
число, то и исходный граф имеет четное число граней. Элементарная перекраска
приводит к замене всех знаков в графе на противоположные, поэтому:
'' ( 1) '( 1) ,Ng g gε= − = − = ' (mod 2)ε ε= ,
что доказывает лемму.
Теорема 2. Четность раскраски плоской триангуляции постоянна и сравнима
с числом ее вершин.
Выделим в раскрашенной плоской триангуляции одну компоненту подграфа
Gst и рассмотрим подграф, образованной вершинами этой компоненты и смеж-
ными с ними вершинами цвета u и v. Легко убедиться, что множество граней
этого подграфа можно разбить на несколько циклических непересекающихся
последовательностей, в которых каждая следующая грань смежна с предыдущей
через ребро, один конец которого окрашен в цвет s и t. Рассмотрим такую по-
следовательность.
Пусть число граней всей равно N, а каждая грань имеет основанным ребро
либо из подграфа Gst либо из подграфа Guv. Обозначим их число соответственно
через N(s,t) и N(u,v). Из леммы 5 следует: N(s,t) ≡ N(u,v)(mod 2) ≡ 0(mod 2).
Сделаем разметку граней знаками +1 и -1 в соответсвии с системой (1.6)-(1.7).
Пусть число граней со знаком +1 равно x, а число граней со знаком y, тогда
сумма всех знаков для граней входящих в N(s,t) равна N(s,t)-2х. Рассмотрим по-
следовательность знаков, соответствующую последовательности всех граней и
выделим в ней отрезок, соответствующий отрезку последовательности между
двумя ближайшими гранями, имеющих основанием ребро из подграфа Gst. Не-
трудно заметить, что если знаки этих граней совпадают, что сума отрезка равна
соответствующему значению этих граней, если знаки граней различны, то сумма
отрезка равна нулю. То есть: N(u, v) – 2y = N(s, t) – 2x. Сумма всей последова-
тельности знаков равна тогда: S=2N(s, t) – 4x. Однако N(s, t) =2l, где l – нату-
ральное число, и поэтому имеем S=4(l-x).
Таким образом, сумма всех знаков для раскрашенной плоской триангуляции
равна 4r, где r – целое число. Пусть число граней, имеющих знак -1 равно k1, а
число граней со знаком +1 равно k2. Тогда эти числа удовлетворяют системе
уравнений:
k1+k2=2n-4,
k2-k1=4r.
ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПОСТРОЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА
Теорія оптимальних рішень. 2012 91
Четность раскраски плоской триангуляции определяется из соотношения
1( 2)k modε = . Но из выведенной выше системы находим: k1=n-2(r+1), откуда
( 2)n modε = , что и требовалось доказать.
Может показаться, что все раскраски плоской триангуляции можно получить
путем элементарных перекрасок, однако легко убедиться, что это не так.
Заключение. Система уравнений для плоской триангуляции адекватно отра-
жает проблему раскрашивания плоского графа четырьмя красками. Существен-
ную роль тут играет использование в качестве переменных ребра гамильтонова
цикла плоского графа. Дальнейшие исследования следует направить в углубле-
ние данной проблемы и построение полинома, способного разрешить проблему
четырех красок.
В.Б. Павленко
РОЗФАРБОВУВАННЯ ПЛОСКИХ ТРІАНГУЛЯЦІЙ
У статті розглядається підхід, який може бути корисним при вирішенні задачі
про розфарбовування плоских графів чотирма фарбами.
V.B. Pavlenko
PAINTING PLANE TRIANGULATIONS
The article proposes an approach that can be useful in solving the problem of coloring
planar graphs with four colors.
1. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
– 432 с.
2. http://grafy.do.am/index/0-27. Плоские триангуляции (интернет-ресурс)
3. Донец А.П. Теоретико-числовой подход к решению некоторых задач теории
графов. Диссертационная работа. – К., 1997. – 162 с.
4. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптими-
зация. – М.: Наука, 1981. – 341 с.
5. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.
Получено 14.05.2012
|