close

Вход

Забыли?

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

?

Задача аппроксимации линейной наследственной системы.

код для вставкиСкачать
МАТЕМАТИКА
Вестн. Ом. ун-та. 2011. № 2. С. 34–38.
УДК 519.8
А.А. Навроцкая
Омский государственный университет им. Ф.М. Достоевского
ЗАДАЧА АППРОКСИМАЦИИ ЛИНЕЙНОЙ
НАСЛЕДСТВЕННОЙ СИСТЕМЫ
Рассматривается новый вариант задачи матроидной аппроксимации, которая является обобщением известной задачи аппроксимации графа. Получена достижимая
верхняя оценка расстояния между произвольной линейной наследственной системой и ближайшим матроидом того же класса.
Ключевые слова: наследственная система, матроид, гиперграф, аппроксимация.
Введение
Пусть V – непустое конечное множество, A ⊆ 2V – непустое семейство его подмножеств, удовлетворяющее следующей аксиоме наследственности: A1 ∈ A, A2 ⊆ A1 ⇒ A2 ∈ A.
Множества семейства A называются независимыми, все остальные подмножества V – зависимыми. Семейство A обычно называют
системой независимости или наследственным семейством на V [1].
Семейство всех зависимых множеств обозначим D. Очевидно,
что семейство D обладает свойством наследственности «вверх»
D1 ∈ D, D1 ⊆ D2 ⇒ D2 ∈ D.
Каждое из семейств A , D однозначно определяет другое, поэтому
естественно рассматривать их как различные стороны одного и того
же объекта, который мы будем называть наследственной системой.
Итак, определим наследственную систему S на множестве V
как разбиение семейства 2V всех подмножеств V на два непересекающихся семейства A и D , где A – система независимости, а
D = 2V \ A [2]. Базами наследственной системы S называются максимальные по включению независимые, а циклами – минимальные по
включению зависимые множества. Семейства всех баз и всех циклов
системы S будем обозначать через B и C соответственно. Очевидно,
что каждое из семейств A , B , C , D однозначно определяет наследственную систему S , поэтому будем записывать S = (V , A) , S = (V , B ) ,
S = (V , C ) или S = (V , D ) в зависимости от того, какая сторона наследственной системы будет нас интересовать.
Далее будем рассматривать только такие наследственные системы, в которых любое одноэлементное множество независимо.
Наследственная система S называется линейной, если любые два
ее цикла имеют не более одного общего элемента [3].
Важным частным случаем наследственной системы является матроид. Понятие матроида было введено Уитни [4]. Известно довольно
много характеризаций матроидов [5], приведем наиболее подходящую.
© А.А. Навроцкая, 2011
Задача аппроксимации линейной наследственной системы
Наследственная система называется
матроидом, если для семейства ее циклов
выполнено условие:
C1 , C2 ∈ C , C1 ≠ C2 , c ∈ C1 ∩ C2
⇒ ∃ C ∈ C : C ⊆ ( C1 ∪ C2 ) \ {c}.
Рассмотрим
оптимизации
задачу
комбинаторной
max{ f ( X ) : X ∈ B},
(1)
где f : 2 → R+ – аддитивная неотрицательная функция, а B – семейство баз наследственной системы S = (V , A) . Как следует из теоремы Радо – Эдмондса (см.: [5]),
задача (1) разрешима жадным алгоритмом, если наследственная система S является матроидом. В связи с этим представляет интерес следующий вопрос: как
сильно данная наследственная система
отличается от матроида? Так мы приходим
к задаче матроидной аппроксимации, самая общая постановка которой такова.
Пусть K (V ) – некоторый класс матроидов на множестве V . Для заданной
наследственной системы S = (V , A) найти матроид M из класса K (V ) , который
в каком-то смысле является самым
близким к системе S . Мера близости
τ ( S ) наследственной системы S и матV
роидов класса K (V ) (аппроксимационная
сложность системы S ) может определяться по-разному в различных задачах.
В данной работе рассматривается задача аппроксимации линейной наследственной системы матроидами. Получена
оценка аппроксимационной сложности
произвольной линейной наследственной
системы в случае, когда расстояние между наследственными системами определяется как число несовпадающих циклов.
Линейные наследственные
системы и гиперграфы
Гиперграфом
называется
пара
H = (V , E ) , где V – непустое конечное
множество, а E – семейство подмножеств
V . Элементы множества V называются
вершинами, а элементы семейства E –
ребрами гиперграфа H .
Произвольной наследственной системе S = (V , C ) поставим в соответствие гиперграф H = (V , E ) , ребра которого взаимно однозначно соответствуют циклам
этой системы. Наоборот, любой гиперграф H порождает наследственную сис-
35
тему S H = (V , C H ) , циклами которой являются минимальные по включению ребра
гиперграфа H .
Поэтому
наследственную
систему
можно отождествлять с гиперграфом, никакое ребро которого не содержит другое
ребро в качестве подмножества. В дальнейшем будем рассматривать только такие гиперграфы и отождествлять наследственные системы и соответствующие им
гиперграфы. Тогда матроидом является
гиперграф M = (V , E ) , удовлетворяющий
условию
e1 , e2 ∈ E , e1 ≠ e2 , v ∈ ( e1 ∩ e2 ) ⇒
∃ e ∈ E : e ⊆ ( e1 ∪ e2 ) \ {v}.
Гиперграф H = (V , E ) называется линейным, если любые два ребра гиперграфа H имеют не более одной общей вершины [6]. Линейный гиперграф соответствует линейной наследственной системе.
Наглядным примером линейной наследственной системы может служить наследственная система графа. Дан граф
G = (V , E ) . Множество вершин A ⊆ V называется независимым, если uv ∉ E для
любых u, v Î A . Обозначим семейство
всех независимых множеств вершин графа G через AG . Тогда SG = (V , AG ) – наследственная система, она называется
наследственной системой графа G . Циклы этой системы взаимно однозначно соответствуют ребрам графа G .
Далее будем рассматривать только
обыкновенные графы, т. е. графы без петель и кратных ребер. Граф G = (V, E ) называется М-графом, если каждая его компонента связности представляет собой
клику, т. е. полный граф [7].
Наследственная
система
графа
G = (V, E ) является матроидом тогда и
только тогда, когда G–M-граф [8]. Такой
матроид называется матроидом разбиения. Имеется в виду разбиение множества вершин М-графа G = (V, E ) на подмножества V1 ,…,Vk , где Vi – множество
попарно смежных вершин i -й компоненты связности, i = 1,… , k .
Гиперграф H = (V , E ) будем называть
М-гиперграфом, если каждая его компонента связности либо состоит в точности
из одного ребра, либо является кликой.
А.А. Навроцкая
36
Следующее утверждение, обобщающее результат Бензакена и Хаммера, будет использовано в дальнейшем.
Теорема 1. Линейная наследственная система является матроидом тогда
и только тогда, когда соответствующий
ей гиперграф является М-гиперграфом.
Доказательство.
Необходим о с т ь . Пусть линейная наследственная
система является матроидом. Тогда соответствующий ей гиперграф H = (V , E ) обладает следующими свойствами:
10. e1 , e2 ∈ E , e1 ≠ e2 , v ∈ ( e1 ∩ e2 ) ⇒
∃ e ∈ E : e ⊆ ( e1 ∪ e2 ) \ {v};
2 . e1 , e2 ∈ E , e1 ≠ e2 ⇒ | e1 ∩ e2 |≤ 1.
Докажем, что в H нет двух ребер,
0
имеющих общую вершину, и таких, что
мощность хотя бы одного из них больше
2. Рассмотрим e1 , e2 ∈ E такие, что их пересечение не пусто.
Предположим, что | e1 |> 2 . Из 20 следует, что | e1 ∩ e2 |= 1 , пусть e1 ∩ e2 = {v} . По
10
существует
ребро
e3 ⊆ ( e1 ∪ e2 ) \ {v} . По свойству 20 | e3 |= 2,
e3 = {v1 , v2 } , где vi ∈ ei , vi ≠ v,
поэтому
i = 1,2, так как в гиперграфе H никакое
свойству
ребро не содержит другое ребро в качестве подмножества. Теперь рассмотрим
ребра e2 и e3 . Аналогично по свойству 10
существует ребро e4 ⊆ ( e2 ∪ e3 ) \ {v2 } . Если
| e2 |= 2 , то e3 = {v, v1} ⊂ e1 , противоречие.
Если же | e2 |> 2 , то e4 = {v1 , v3} , где v3 ∈ e2 ,
v3 ≠ v , v3 ≠ v2 . Но тогда, применяя свойство 10 к ребрам e3 и e4 , получим ребро
e = {v2 , v3} ⊂ e2 . Противоречие с тем, что
никакое ребро не содержит другое ребро
в качестве подмножества.
Следовательно, если два ребра лежат
в одной компоненте гиперграфа H и пересекаются, то их мощности равны 2. Отсюда легко видеть, что компоненты связности либо состоят из одного ребра, либо
содержат только ребра мощности 2.
Докажем, что все вершины, принадлежащие одной компоненте связности
гиперграфа H , попарно смежны. Допустим, существуют вершины v и u , принадлежащие одной компоненте связности, такие, что vu ∉ E . Рассмотрим кратчайшую цепь, соединяющую v и u . Если
эта цепь содержит больше одного ребра,
то найдутся вершины w1 и w2 этой цепи
такие, что vw1 ∈ E и w1w2 ∈ E
(возмож-
но w2 = u ). Тогда по свойству 1 существу0
ет ребро vw2 ∈ E . Таким образом, (v, u ) цепь может быть сокращена на одно ребро, а это невозможно, так как она кратчайшая. Следовательно, vu ∈ E .
Д о с т а т о ч н о с т ь. Пусть H является М-гиперграфом, т. е. каждая компонента связности гиперграфа H = (V , E )
либо состоит в точности из одного ребра,
либо является кликой. Тогда свойства 10 и
20 , очевидно, выполняются. Следовательно, соответствующая наследственная система является матроидом.
Теорема доказана.
Задачи матроидной аппроксимации
Если S1 = (V ,C 1 ) и S2 = (V ,C 2 ) – две наследственные системы на одном и том же
множестве V , то расстояние между ними
определяется как ρ ( S1 ,S 2 ) =| C 1 ΔC 2 | , т. е.
ρ ( S1 ,S 2 ) – число несовпадающих циклов
систем S1 и S2 .
Рассмотрим вариант задачи матроидной аппроксимации, в котором S = (V ,C )
– линейная наследственная система, а
аппроксимационная сложность τ ( S ) определяется следующим образом:
τ ( S ) = min ρ ( S ,M ),
(2)
M ∈L (V )
где L(V ) – класс всех матроидов на множестве V , являющихся линейными наследственными системами (по теореме 1
им взаимно однозначно соответствуют
М-гиперграфы). Другими словами, для
данного гиперграфа требуется найти ближайший M -гиперграф. Расстояние между гиперграфами понимается как число
несовпадающих ребер.
Частным случаем этой задачи является известная задача аппроксимации графа, в которой S = SG = (V , AG ) – наследственная система графа G = (V , E ) , вместо
класса L(V ) рассматривается класс M (V )
всех матроидов разбиений на множестве
V (им взаимно однозначно соответствуют
М-графы на множестве V ), а
τ ( SG ) = τ (G ) = min ρ (G,M ) ,
M ∈M (V )
где ρ (G , M ) – число несовпадающих ребер графа G и М-графа М.
Задача аппроксимации линейной наследственной системы
Обе задачи – аппроксимации графа и
матроидной аппроксимации – возникают
при анализе систем взаимосвязанных
объектов, в частности в задачах классификации, а также в социологии. Любой
М-гиперграф отражает разбиение множества взаимосвязанных объектов на группы, причем имеется два типа связей
внутри групп. В группах, соответствующих кликам М-гиперграфа, все объекты
взаимозаменяемы, и выбытие одного или
нескольких участников группы не влияет
на устойчивость оставшейся части. А в
группах, соответствующих компонентам
М-гиперграфа, состоящим из одного ребра мощности k ≥ 3 , все объекты уникальны (т. е. участники группы имеют узкую
специализацию), поэтому выход из группы любого члена ведет к ее распаду.
Постановки и различные интерпретации задач аппроксимации и классификации можно найти в [9–13].
В работе [13] показано, что задача
аппроксимации графа NP-трудна, а значит NP-трудной является и более общая
задача матроидной аппроксимации (2).
В [11; 12] показано, что для любого
n-вершинного графа G имеет место оценка
⎢ ( n − 1) 2 ⎥
⎥.
⎣ 4 ⎦
τ (G ) ≤ ⎢
(3)
Следующее утверждение будет использовано в дальнейшем.
Лемма 1. [14] Пусть G = (V , E ) –
⎢ n2 ⎥
n-вершинный граф. Если | E |≤ ⎢ ⎥ − m , где
⎣4⎦
m = 2, 3, … , то существует такой
M -граф M ∈ M (V ), что
⎢ ( n − 1) 2 ⎥ ⎡ m ⎤
⎥−⎢ ⎥.
⎣ 4 ⎦ ⎢2⎥
ρ (G , M ) ≤ ⎢
Получена верхняя оценка величины
τ ( S ), определяемой равенством (2).
Теорема 2. Пусть S = (V , C ) – линейная наследственная система, | V |= n. Тогда
⎢ ( n − 1) 2 ⎥
⎥.
⎣ 3 ⎦
τ (S ) ≤ ⎢
(4)
Доказательство. Пусть H = (V , R ) –
линейный гиперграф, ребра которого взаимно однозначно соответствуют циклам
системы S . Представим множество ребер
гиперграфа H в виде R = E ∪ D, где E –
37
множество всех ребер мощности 2, а D –
множество всех ребер мощности 3 и более.
⎢ ( n − 1)2 ⎥
⎥.
⎣ 12 ⎦
1. Пусть | D |≤ ⎢
Рассмотрим граф G = (V , E ). В силу (3)
существует такой M -граф M ∈ M (V ) , что
⎢ ( n − 1) 2 ⎥
⎥.
⎣ 4 ⎦
ρ (G , M ) ≤ ⎢
М-граф М является М-гиперграфом,
поэтому
τ ( H ) ≤ ρ ( H , M ) =| D | + ρ (G , M ) ≤
⎢ ( n − 1) 2 ⎥ ⎢ ( n − 1) 2 ⎥ ⎢ ( n − 1) 2 ⎥
≤⎢
⎥+⎢
⎥≤⎢
⎥.
⎣ 12 ⎦ ⎣ 4 ⎦ ⎣ 3 ⎦
⎢ ( n − 1)2 ⎥
т. е.
| D |> ⎢
2.
Пусть
⎥,
⎣ 12 ⎦
⎢ ( n − 1) 2 ⎥
| D |= ⎢
⎥ + k , k ≥ 1 . Тогда
⎣ 12 ⎦
| E |≤
⎢ n2 ⎥
n( n − 1)
− 3 | D |= ⎢ ⎥ − 3k , k ≥ 1 .
2
⎣4⎦
В силу леммы 1 найдется такой М-граф
⎢ ( n − 1) 2 ⎥ ⎡ 3k ⎤
M ∈ M (V ), что ρ (G , M ) ≤ ⎢
⎥−⎢ ⎥.
⎣ 4 ⎦ ⎢2⎥
Следовательно,
τ ( H ) ≤ ρ ( H , M ) ≤| D | + ρ (G , M ) ≤
⎢ ( n − 1) 2 ⎥
⎢ ( n − 1) 2 ⎥ ⎡ 3k ⎤
k
≤⎢
+
+
⎥
⎢ 4 ⎥−⎢ 2 ⎥<
⎣ 12 ⎦
⎣
⎦ ⎢ ⎥
2
2
⎢ ( n − 1) ⎥ ⎢ ( n − 1) ⎥ ⎢ ( n − 1) 2 ⎥
<⎢
⎥+⎢
⎥≤⎢
⎥.
⎣ 12 ⎦ ⎣ 4 ⎦ ⎣ 3 ⎦
Теорема доказана.
Замечание. Оценка (4) достижима.
Действительно, рассмотрим линейный
гиперграф H n = (V , R ), где n = 2(2 k − 1),
k = 2, 3,… , полученный из полного двудольного графа K n n
путем добавления
,
2 2
всевозможных ребер мощности 3 внутри
каждой доли так, чтобы любые два из них
пересекались не более чем по одной вершине.
Нетрудно видеть, что оптимально аппроксимирующим для гиперграфа H n будет М-граф М, представляющий собой совершенное паросочетание графа K n n .
,
2 2
Число ребер графа М равно
n
, поэтому
2
А.А. Навроцкая
38
n
⎢ ( n − 1)2 ⎥
⎥.
⎣ 3 ⎦
τ ( H n ) = ρ ( H n , M ) =| R | − = ⎢
2
Существуют также примеры, когда
оптимально аппроксимирующим является
М-гиперграф, отличный от М-графа, и
оценка (4) достижима. Самый простой
пример приведен на рис. 1. Дан гиперH
с
множеством
вершин
граф
V = {1,2,3,4} и ребрами {1,2,3}, {1,4},
{2,4}, {3,4} .
Тогда одним из оптимально аппроксимирующих М-гиперграфов для H будет
гиперграф, содержащий ровно одно ребро
{1,2,3} и изолированную вершину 4
(рис. 2).
1
1
2
4
2
4
3
3
Рис. 1
Рис. 2
ЛИТЕРАТУРА
[1] Grötschel M., Lovász L. Combinatorial optimization // Handbook of Combinatorics / Graham R.O.,
Grötschel M., Lovász L., eds. Amsterdam: Elsevier Science B.V. 1995. V. 2. P. 1341–1598.
[2] Il’ev V. Hereditary systems and greedy-type algorithms // Discrete Appl. Math. 2003. V. 132. № 1–
3. P. 137–148.
[3] Grama Y., Hammer P. L. Methods and Models of
Operations Research. 1989. V. 33. № 3. P. 149–
165.
[4] Whitney H. On the abstract properties of linear
dependence // Amer. J. Math. 1935. V. 57.
P. 509–533.
[5] Welsh D. J. A. Matroid theory. London: Academic
Press, 1976.
[6] Berge C. Hypergraphes. Paris: Gauthier – Villars.
1987; English transl.: Berge C. Hypergraphs:
Combinatorics of Finite Sets, Amsterdam: North –
Holland, 1989.
[7] Тышкевич Р. И. Матроидные разложения графа // Дискретная математика. 1989. Т. 1.
Вып. 3. С. 129–139.
[8] Benzaken C., Hammer P. L. Boolean techniques
for matroidal decomposition of independence systems and applications to graphs // Discrete Math.
1985. V. 56. P. 7–34.
[9] Zahn C. Approximating symmetric relations by
equivalence relations // J. of the Society for Industrial and Applied Mathematics. 1964. V. 12. № 4.
P. 840–847.
[10] Ляпунов А. А. О строении и эволюции управляющих систем в связи с теорией классификации // Проблемы кибернетики. М. : Наука,
1973. Вып. 27. С. 7–18.
[11] Фридман Г. Ш. Об одном неравенстве в задаче
аппроксимации графов // Кибернетика. 1974.
№ 3. С. 151.
[12] Фридман Г. Ш. Исследование одной задачи
классификации на графах // Методы моделирования и обработки информации. Новосибирск : Наука, 1976. С. 147–177.
[13] Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи
аппроксимации графов // Дискрет. анализ и
исслед. операций. Серия 1. 2006. Т. 13. № 1.
C. 3–15.
[14] Ильев В. П. Одна задача матроидной аппроксимации // Методы решения и анализа задач
дискретной оптимизации. Омск, 1992. C. 42–
51.
Документ
Категория
Без категории
Просмотров
4
Размер файла
442 Кб
Теги
линейной, система, наследственная, задачи, аппроксимация
1/--страниц
Пожаловаться на содержимое документа