3-приближенный алгоритм для одного варианта задачи аппроксимации графа

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

МАТЕМАТИКА
Вестн. Ом. ун-та. 2009. № 4. С. 77−79.
УДК 519. 8
В. П. Ильев, С.Д. Ильева
Омский государственный университет им. Ф. М. Достоевского
3-ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ ОДНОГО ВАРИАНТА ЗАДАЧИ АППРОКСИМАЦИИ ГРАФА
Рассматривается КР-трудная задача аппроксимации графами с одной или двумя компонентами связности. Для данной задачи предложен 3-приближенный алгоритм.
Ключевые слова: задача аппроксимации графа, приближенный алгоритм.
Задачи аппроксимации графов возникают при анализе систем взаимосвязанных объектов, в частности, в задачах классификации. При этом минимизируется число связей между классами и число недостающих связей внутри классов.
Будем рассматривать только обыкновенные графы, т. е. графы без петель и кратных рёбер.
Следуя Р. И. Тышкевич [1], обыкновенный граф будем называть М -графом, если каждая его компонента связности является полным
графом. Обозначим через М'-2 (V) класс всех М -графов на множестве вершин V, имеющих не более двух компонент связности.
Если Ох = (V, Е1) и G2 = (V, Е2) — графы на одном и том же множестве вершин V, то расстояние р (Сг, G2) между ними определяется как р (Сг, G2) =| Е1АЕ2 |, т. е. р (Сг, G2) — число несовпадающих рёбер
в графах G1 и G2.
Рассмотрим следующий вариант задачи аппроксимации графа. Задача А2. Дан граф G = (V, Е). Требуется найти такой граф
М є М1 ^), что Р (С, Мо) = тп Р (С, М).
о Ь і'А2 V)' МєМ2 (V)
В работе [2] доказано, что задача А2 является ЫР-трудной.
Пусть G1 = (V, Е1) и G2 = (V, Е2) — помеченные графы. Через, G2) будем обозначать граф на множестве вершин V с множеством ребер Е1АЕ2. Очевидно, р1, G2) равно числу ребер графа В (С1,G2), откуда вытекает следующее.
Лемма 1. Пусть В = В1, G2), dmm — минимум степеней вершин в графе В. Тогда
р (Сх, G2) & gt- ^•
© В. П. Ильев, С. Д. Ильева, 2009
78
В. П. Ильев, С.Д. Ильева
Пусть дан п -вершинный граф G = (V, Е) — вход задачи А2. Для
V1, У2 — V таких, что V1 Пі V2 = 0 и
V1 и V2 = V введем следующее обозначение: М V V- М -граф из класса
М (У), в котором все вершины множества V1 лежат в одной компоненте связности, а все вершины множества V2 — в другой.
Легко видеть, что при переносе любой вершины некоторого М -графа М є є М2 (V) в противоположную компоненту связности расстояние от данного графа G до полученного М -графа увеличится не более, чем на п — 1. Поэтому имеет место следующее утверждение.
Лемма 2. Пусть М = М (^1,^2) — произвольное допустимое решение задачи
А2. Тогда для любых и —1, и —2 та-
| и л | + | и2 |= к /1 & lt- к & lt- п ких, что 1 11 1 21 справедливо следующее утверждение: если
М'-= М (V'-1, V'-2), где V'-1 = (К и,) и и2,
V '-2 = (К и2) и и, то
р (0,М'-) & lt- р^, М) + к (п — 1).
Далее через ~Ы (Э (^ будем обозначать
dmin = тІП d0(и) = d 0(У)
uєV
окрестность вершины
V єV
в графе G, а
Ыг (V) v
через 1 '- - все несмежные с к верши-
ны.
Мо є м2(к)
Пусть о 2 — - оптимально аппроксимирующий М -граф для графа G ,
Во = D (G'М°). Через ^(^ обозначим
степень вершины v в графе В& lt-о.
Лемма 3. Пусть V єV — вершина
минимальной степени в графе Во. Рассмотрим М -граф М = М (У1,У: 2), где
V = {V} и ^ (V), V2 = V V = NG (V). Тогда
р^, М) & lt- 3 — 2
р (^, Мо) п
Доказательство. Пусть
Положим, Мо = М V0 ^2). Покажем, что М -граф М может быть получен из
графа Мо путем переноса dmm вершин в противоположную компоненту. Без ограничения общности считаем, что V єУ1 и
V єУх°
Очевидно, в графе Во смежны те и только те вершины, которые либо смежны в графе G и находятся в разных компонентах графа Мо, либо несмежны в графе G и находятся в одной компоненте
графа Мо. Следовательно, для любой вершины и є V {V} справедливо слеи є К0
дующее утверждение: 1 тогда и
только тогда, когда либо
и є NG (У) Ыв0 (У), либо
и є NG (v) п Ыво (v) (значит, и є, если и
только если и є NG (У) ^ ЫВо (У) или
и є NG (^Ыво (у)).
Положим, и1 = ^ Ыэо ^) ,
и2 = NG (г0 П ЫЭо ^). Легко видеть, что
и1 — V0 и2 — V" V = (V0и1) и и 2 & gt- & gt- & gt-
V2 = (К0 и 2) и и1 т
2 2 2 1. Так как
1 и 1 М и2 | = | ^ (У) П ЫВо 00 | +
+ 1 NG 00 ^ ЫВ0 (У) Н ЫВ0 00 |= dmin, то в силу леммы 2 получаем: р^ М) & lt- р (С, Мо) + dmin (п — 1). При
dmm =0 отсюда вытекает равенство
= 1. Если dmm & gt- 0, то оценим от-
р (ОМ) 1
ношение рг,, с учетом леммы 1:
р (0 Мо)
р (0, М)
d ¦ (п — 1)
р (а, Мо) р (р, Мо)
& lt- 1 + dтп (п — 1) = 1 + 2(п — 1) = 3 — 2
п
п
Лемма 3 доказана.
Рассмотрим следующий алгоритм.
З-приближенный алгоритм для одного варианта задачи аппроксимации графа
79
Алгоритм Ы.
1. Для каждой вершины V єV определим М -граф Му є М2 (V) следующим
образом: вершина v и все смежные с ней вершины графа G принадлежат одной
компоненте связности графа Му, а все несмежные с v вершины графа G — другой компоненте.
2. Среди всех графов Му выберем такой граф МЫ, что
р^, Мы) = mm р^, Му)
vєV
Очевидно, среди всех вершин будет
выбрана и такая V єV, что do = dmin.
Отсюда с учетом леммы 3 получаем оценку погрешности алгоритма Ы.
Теорема 1. Для любого п -вершинного графа G = (У, Е)
р (в, МЫ) «2
^ & lt- 3---. (1)
р (^, Мо) п
Замечание 1. Существует бесконечное семейство графов {Gn} (п — число вершин графа Gn, п = 2к, к = 2, 3, …) такое, что
р (^п, Мы) = 3 — 6
р^п, М о) п
т. е. оценка (1) достижима в асимптотическом смысле.
При любом п & gt- 4 граф Gn устроен
следующим образом: вершина v1 степени
1 в нем смежна с вершиной V2 степени п — 1- остальные п — 2 вершины порождают подграф, полученный из полного
(п — 2)-вершинного графа Кп-2 удалением наибольшего паросочетания мощности
п- о
2. Пример такого графа для п = 8 приведен на рисунке.
Нетрудно видеть, что оптимально аппроксимирующим графом для графа Gn
является M -граф M O = {v1} ^ Kn-1, в котором вершина v1 принадлежит одной компоненте связности, а все остальные вершины — другой компоненте, и p (Gn, MO) = n. Для каждого M -графа
Mv, построенного на шаге 1 алгоритма
N, выполнено равенство p (Gn, Mv) =
= 3 т — 3. В качестве графа MN алгоритм может выбрать, например, полный граф MV2 = Kn.
Замечание 2. Предложена также модификация алгоритма N для задачи аппроксимации M -графами с числом компонент связности, равным двум. Показано, что гарантированная оценка погрешности модифицированного алгоритма не превосходит 5.
ЛИТЕРАТУРА
[1] Тышкевич Р. И. Матроидные разложения графа // Дискрет. математика. 1989. Т. 1. Вып. 3.
С. 129−139.
[2] Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С.
Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 1. С. 3−15.

ПоказатьСвернуть
Заполнить форму текущей работой