close

Вход

Забыли?

вход по аккаунту

?

Градиентный алгоритм для задачи о раскраске графа.

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2008. № 1. С. 10–13.
УДК 519.8
К.Н. Пахомова
Омский государственный университет им. Ф. М. Достоевского
ГРАДИЕНТНЫЙ АЛГОРИТМ
ДЛЯ ЗАДАЧИ О РАСКРАСКЕ ГРАФА
Hereditary system H=(U,D), where D is family of all colorings of graph G=(V,E), is studied. Performance guarantees of а greedy algorithm are obtained.
Введение
В настоящей работе рассматривается задача о минимальной вершинной раскраске графа. Граф G=(V, E) k-раскрашиваем, если каждой
его вершине можно приписать один из k цветов таким образом, что
любые две смежные вершины окрашены в разные цвета. Если граф G
k-раскрашиваем, но не является (k–1)-раскрашиваемым, то он называется k-хроматическим, а число k − хроматическим числом графа G,
обозначается χ (G ) . Раскраской неориентированного n-вершинного
графа G=(V, E) называется разбиение P =
(V1 ,V2 ,...,Vk )
множества V на
попарно непересекающиеся подмножества V1 ,V2 ,...,Vk , где Vi − независимое множество вершин графа, i = 1,… , k . Число k = P называется
мощностью раскраски. Задача о минимальной раскраске графа состоит в отыскании раскраски минимальной мощности.
Задача о минимальной раскраске графа может быть сформулирована как задача о минимальном зависимом множестве наследственной
системы [1]. Для приближенного решения задачи о минимальной раскраске графа рассмотрен градиентный алгоритм. Получены гарантированные оценки погрешности алгоритма.
1. Наследственная система всех раскрасок
Пусть U − конечное множество. Наследственная система H на
множестве U определяется как пара (U, D), где D ⊆ 2U – семейство подмножеств множества U, удовлетворяющее следующей аксиоме наследственности: ( D ∈ D , D ⊆ D′) ⇒ D′ ∈ D . Множества семейства D называются зависимыми.
Пусть H=(U, D) − произвольная наследственная система, W ⊆ U .
Циклом множества W называется любое минимальное по включению
зависимое множество, содержащее W . Цикл пустого множества называется циклом системы H.
Кривизной наследственной системы H называется величина, численно равная
© К.Н. Пахомова, 2008
11
Градиентный алгоритм для задачи о раскраске графа
c D = c D ( H ) = max
W ⊆U
W ∉D
g u (W ) − W
g l (W ) − W
,
где g u (W ) = max{ C : C − цикл множества W },
g l (W ) = min{ C : C − цикл множества W }. Величины g u (φ ) и g l (φ ) называются соответственно верхним и нижним обхватом
наследственной системы H.
Рассмотрим задачу о минимальном
зависимом множестве. Пусть дана наследственная система H на множестве U
и неотрицательная аддитивная функция
f : U → R+ . Необходимо найти такое мно-
D0 ∈ D ,
жество
что
f ( D0 ) = min{ f ( D ) : D ∈ D } , где D − семейство всех зависимых множеств наследственной системы H.
Градиентный алгоритм GR1 [1].
Шаг 0. Упорядочить U = {u1 ,u 2 ,…, u n }
по невозрастанию значений функции f ,
D ← U ; перейти на Шаг 1.
Шаг i (i = 1,…, n ) . Если D \ {u i } ∈ D , то
D ← D \ {u i } . Если i < n , то перейти на
Шаг (i + 1) , иначе DGR1 ← D .
Теорема 1 [1]. Пусть H=(U,D) − произвольная наследственная система. Тогда
для любой аддитивной целевой функции
задачи о минимальном зависимом множестве имеет место достижимая оценка
f ( DGR1 )
≤ cD ,
f ( D0 )
где с D − кривизна системы H, D0 −
оптимальное решение задачи о минимальном зависимом множестве, а DGR1 −
решение, найденное градиентным алгоритмом GR1.
Для невзвешенного варианта задачи
эта оценка может быть уточнена [1].
Следствие 1. Пусть H=(U,D) − произвольная наследственная система. Тогда
DGR1
D0
≤
g u (φ )
,
g l (φ )
(1)
где D0 − оптимальное решение задачи о
минимальном зависимом множестве, а
DGR1 − решение, найденное алгоритмом
GR1.
Задача о минимальной раскраске
графа может быть сформулирована как
задача о минимальном зависимом множестве следующим образом. Пусть P1 и P2 −
две раскраски графа G=(V,E). P1 − подраскраска раскраски P2 , если P1 получена
из P2 заменой некоторого множества V j
объединением Vi ∪ V j , где i ≠ j , с последующим удалением Vi . Это означает перекраску всех вершин множества Vi в
цвет вершин множества V j . Для заданного n-вершинного графа G=(V,E) рассмотрена наследственная система H=(U,D), где
U = 2V , а D − семейство всех раскрасок
графа G.
Для приближенного решения задачи о
минимальной раскраске графа рассмотрим следующий алгоритм, который является вариантом градиентного алгоритма
GR1 для невзвешенной задачи о минимальном зависимом множестве.
Алгоритм GR2 [2].
Шаг 0. Начать с тривиальной расP = (V1 ,V2 ,...,Vn ) , где Vi = {vi } ,
краски
i = 1,… , n ; перейти на Шаг 1.
Шаг i (i = 1,…, n ) . Текущая раскраска
P содержит множество Vi . Выбрать наименьший номер j ∈ {i + 1,..., n}, такой, что
Vi ∪ V j
независимо
в
графе
G,
V j ← Vi ∪ V j и удалить Vi из P. Если i < n ,
то
перейти
на
Шаг
(i + 1) ,
иначе
PGR 2 ← P .
Заметим, что трудоемкость алгоритма
GR2 равна O( n 2 ).
2. Верхняя оценка мощности раскраски, найденной алгоритмом GR2
Лемма 1. Пусть G=(V,E) − nвершинный граф с хроматическим числом χ = χ (G ) , H=(U,D) − наследственная
система, где D − семейство всех раскрасок графа G.
Пусть P − такая раскраска графа G,
что P = g u (φ ) , где g u (φ ) − верхний обхват
наследственной системы H=(U,D).
К.Н. Пахомова
12
Если P содержит ровно χ тривиальных множеств, то либо граф G является
полным, либо G содержит полный подграф K χ с χ вершинами и d (v) ≥ χ для
Заметим, если число тривиальных
множеств в P1 равно χ , то по лемме 1
либо граф G является полным, либо G содержит полный подграф K χ с χ верши-
любой вершины v ∈ V ( K χ ) , где d (v) − сте-
нами и
пень вершины v в графе G.
Доказательство. 1) Пусть
v ∈ V ( K χ ) . Получаем противоречие с усло-
P =χ и
все χ множеств в P тривиальные, тогда
χ = n и граф G является полным.
2) Пусть раскраска P имеет вид
P = (V1 ,V2 ,…,Vχ ,Vχ +1 ,…,Vl ) , где
Vi = {vi }
для любого i = 1,…, χ , а V j не являются
j = χ + 1,…, l .
Очевидно, в графе G вершины v1 , v 2 ,…, v χ
тривиальными для любого
попарно смежны, и поэтому G ⊃ K χ . Поскольку
Vi ∪ V j не являются независи-
мым множествами для любых i = 1,…, χ ,
j = χ + 1,…, l ,
то
любая
вершина
vi ∈ V ( K χ ) смежна хотя бы с одной вер-
V j , j = χ + 1,…, l . Получаем, что
d (vi ) ≥ l − 1 ≥ ( χ + 1) − 1 = χ
для
любого
i = 1,…, χ .
шиной из
Лемма 2. Пусть G=(V,E) − nвершинный граф,
удовлетворяющий
следующим условиям:
1. G не является полным графом;
2. G не содержит полного подграфа
K χ с χ вершинами, такого, что d (v) ≥ χ
для
любой
вершины
v ∈V ( K χ ) ,
где
χ = χ (G ) − хроматическое число графа G,
d (v) − степень вершины v. Тогда алгоритм GR2 находит раскраску PGR 2 мощности
⎢ n + χ − 1⎥
PGR 2 ≤ ⎢
⎥.
2
⎣
⎦
(2)
Доказательство. Пусть H=(U,D) − наследственная система, где D − семейство
всех раскрасок графа G=(V,E). Рассмотрим раскраски P0 , P1 , такие, что
| P0 |= g l (φ ) = χ , P1 = g u (φ ) . Если P1 содержит множества Vi = {vi } и V j = {v j } , то
вершины vi и v j смежны в графе G.
d (v) ≥ χ
для любой вершины
вием леммы 2. Если число тривиальных
множеств в P1 больше χ , то P0 > χ . Поэтому
число
тривиальных
множеств
Vi = {vi } в P1 не превосходит χ − 1 .
Тогда, g u (φ ) ≤ ( χ − 1) + ⎣(n − ( χ − 1)) / 2⎦ =
= ⎣(n + χ − 1) / 2⎦ . Следовательно, получаем
g u (φ ) g l (φ ) ≤ ⎣(n + χ − 1) / 2⎦ χ . В силу (1),
PGR 2 ≤ P0 ⎣(n + χ − 1) / 2⎦ χ = ⎣(n + χ − 1) / 2⎦ .
3. Оценки погрешности алгоритма
GR2
Максимальное число попарно несмежных вершин в графе G=(V,E) называется числом независимости графа G и
обозначается α (G ) .
Введем также следующие обозначения: Δ(G ) − максимальная степень, а
δ (G ) − минимальная степень вершин
графа G.
В [3] приведены доказательства следующих теорем.
Теорема 2. 1) Для произвольного nвершинного графа G=(V,E)
α (G ) ≥ n (Δ(G ) + 1) ;
(3)
2) Если G=(V,E) − связный nвершинный граф, не являющийся полным,
и Δ (G ) ≥ 3 , то
α (G ) ≥ n Δ(G ) .
(4)
Теорема 3. 1) Для произвольного nвершинного графа G=(V,E)
χ (G ) ≤ Δ (G ) + 1 .
(5)
Теорема 4 (Брукс). Если G=(V,E) −
связный n-вершинный граф, не являющийся полным, и Δ(G ) ≥ 3 , то
χ (G ) ≤ Δ (G ) .
(6)
С помощью неравенств (3)-(6) докажем следующие гарантированные оценки
погрешности алгоритма GR2.
Утверждение 1. 1) Пусть G=(V,E) −
произвольный n-вершинный граф, удовлетворяющий условиям леммы 2. Тогда
PGR 2
P0
≤
⎞
1⎛
1
⎜⎜ n − δ (G ) + 1 −
⎟;
2⎝
Δ(G ) + 1 ⎟⎠
(7)
13
Градиентный алгоритм для задачи о раскраске графа
2) Пусть G=(V,E) − связный nвершинный граф с максимальной степенью Δ(G ) ≥ 3 , удовлетворяющий условиям
леммы 2. Тогда
PGR 2
≤
P0
где
P0
1⎛
1 ⎞
⎜⎜ n − δ (G ) + 1 −
⎟,
2⎝
Δ (G ) ⎟⎠
(8)
− минимальная раскраска
графа G.
Доказательство.
Очевидно,
что
χ (G ) ≥ α (G ) , где α (G ) − число независи-
граф G связен и G удовлетворяет условию 2 леммы 2. Тогда
PGR 2
P0
P0
=
⎢ n + χ (G ) − 1⎥
⎢
⎥ n + χ (G ) − 1
2
⎦≤
=
≤⎣
χ (G )
2 χ (G )
1⎛ n
1 ⎞ 1⎛ n
1 ⎞
⎟.
⎟⎟ ≤ ⎜⎜
⎜⎜
+1−
+1−
χ (G ) ⎠ 2 ⎝ α (G )
χ (G ) ⎟⎠
2 ⎝ χ (G )
Воспользуемся неравенствами (3) и
⎞
1⎛
1
⎟;
⎜⎜ n − δ (G ) −
2⎝
Δ (G ) + 1 ⎟⎠
2) Пусть G=(V,E) − связный nвершинный граф, n ≥ 4 , минимальная
степень δ (G ) ≤ n − 4 , максимальная степень Δ(G ) ≥ 3 , дополнительный граф G
связен и G удовлетворяет условию 2
леммы 2. Тогда
PGR 2
мости графа G . Тогда в силу (2),
PGR 2
≤
P0
≤
1⎛
1 ⎞
⎟.
⎜⎜ n − δ (G ) −
2⎝
Δ(G ) ⎟⎠
Доказательство аналогично доказательству утверждения 1, только вместо
неравенства (3) используется неравенство
(4).
ЛИТЕРАТУРА
(5):
PGR 2
P0
≤
⎞
1⎛
1
⎜⎜ Δ (G ) + 2 −
⎟.
2⎝
Δ(G ) + 1 ⎟⎠
Учитываем
Δ(G ) = n − δ (G ) − 1 ,
равенство
получаем
требуемую
оценку (7).
Если в доказательстве использовать
неравенство (6) вместо (5), то получим
оценку (8).
Утверждение 2. 1) Пусть G=(V,E) −
n-вершинный граф, n ≥ 4 , минимальная
степень δ (G ) ≤ n − 4 , дополнительный
[1] Il'ev V. Hereditary systems and greedy–type algorithms // Discrete Appl. Math. 2004. V. 132. P.
137–148.
[2] Ильев В.П. Оценки погрешности приближенного алгоритма для задачи о раскраске графа //
XIII Байкальская международная школасеминар “Методы оптимизации и их приложения”: труды школы-семинара. Иркутск, 2005. Т.
1. С. 491-495.
[3] Емеличев В.А., Мельников О.И., Сарванов В.И.,
Тышкевич Р.И. Лекции по теории графов. М.:
Наука, 1990. 384 с.
Документ
Категория
Без категории
Просмотров
7
Размер файла
533 Кб
Теги
алгоритм, раскраска, граф, градиентных, задачи
1/--страниц
Пожаловаться на содержимое документа