Разбирая старые бумаги наткнулся на изрядно потрёпанную тетрадь, в которой обнаружил наброски алгоритма поиска покрытия. Автор алгоритма Виктор Анатольевич Щербанов — мой учитель, под руководством которого я работал в девяностые годы прошлого столетия. Моё скромное участие в основном заключалось в том, что я предлагал в большинстве случаев неверные (а порой и просто бредовые) варианты. Что в общем-то не помешало Шефу (так мы его называли между собой) таки довести работу над алгоритмом до логического завершения. Где-то в двухтысячных годах алгоритм был опубликован в одном из институтских изданий Томска. Но думаю, что не лишним будет вспомнить его ещё раз. Собственно в память о Шефе я и решил написать этот пост. Может быть алгоритм покажется кому-то интересным или подтолкнёт на какие-то новые идеи по реализации алгоритма.


Сам алгоритм зиждется на двух утверждениях и двух теоремах, доказательства которых здесь не приводятся, из-за их довольно большого объёма.

Для начала определимся с тем, что мы, собственно, ищем.

Пусть задано конечное множество image и семейство его подмножеств .
Найти подсемейство (если оно существует) такое, что и мощность подсемейства S* (покрытия множества V) наименьшая из всех возможных.

Следующие утверждения определяют понятия минимального и наименьшего покрытия.

Утверждение 1.
Для того чтобы подсемейство , было покрытием множества image, необходимо и достаточно, чтобы выполнялось условие


Покрытие S' называется минимальным, если не существует покрытия S'' такого, что .
Покрытие S* называется наименьшим, если для любого минимального покрытия S' выполняется условие


Утверждение 2.
Покрытие минимально тогда и только тогда, когда для любого , выполняется условие




И, самое основное.

Пусть задано конечное множество image и семейство его подмножеств .
Построим полный нагруженный граф , в котором множеству вершин графа взаимно однозначно сопоставлено семейство подмножеств ,
а каждому ребру — подмножество .

Обозначим множество всех рёбер инцидентных вершине , а — множество всех вершин, инцидентных рёбрам из множества .

Теорема 1.
Минимальное по мощности подмножество ребер, инцидентных произвольной вершине в графе G, при выполнении условий

определяет минимальное покрытие , однозначно соответствующее множеству вершин, если , или множеству вершин, если .

Теорема 2.
Минимальное по мощности подмножество ребер, инцидентных произвольной вершине ребра в графе G, при выполнении условий

для всех
определяет наименьшее покрытие , однозначно соответствующее множеству вершин, если , или множеству вершин, если .


На основании теорем предлагается следующий алгоритм поиска наименьшего покрытия.

1. Множеству image и семейству его подмножеств , сопоставить семейство подмножеств . Если для некоторого окажется , то существует тривиальное покрытие . Конец алгоритма.
Иначе перейти на п.2.

2. Построить полный нагруженный граф , где .
Вершину нагрузить множеством
Ребро нагрузить множеством .

3. Проверить существование покрытия: для произвольной вершины определить подмножество
,
где — множество рёбер, инцидентных вершине в графе .
Если , то покрытия не существует. Конец алгоритма.
Если , то покрытие существует. Перейти к процедуре поиска наименьшего покрытия (п. 4).

4. Положить t:=0.
5. В полном нагруженном графе найти ребро для которого выполняется условие .
Если , то перейти на п. 6,
иначе — на процедуру построения множества D вершин, определяющих наименьшее покрытие (п. 7).

6. Построить полный нагруженный граф , полагая , — множество рёбер, инцидентных вершине в графе .
Положить для всех .
Положить t:=t+1 и перейти на п. 5.

7. Начало построения множества D вершин, определяющих наименьшее покрытие .
Положить .

8. Если t=0, то перейти на п. 11, иначе — положить t:=t-1.

9. В графе определить подмножество

10. Если в графе выполняется условие , то положить , иначе — D:=D. Перейти на п. 8.

11. Семейство подмножеств определяет наименьшее покрытие множеств .
Конец алгоритма.


Попробуем оценить сложность алгоритма.
Вся, так сказать, суть алгоритма (с точки зрения оценки сложности) заключена в фразе «построим полный нагруженный граф».
Нам требуется выполнить n действий для вычисления нагрузки в n вершинах графа и (n-1)n/2 вычислений (по количеству рёбер полного графа) для нагрузки рёбер графа. И всё это, если рассматривать наихудший случай, когда подмножества взаимно не пересекаются, выполняется n-2 раза. Таким образом грубая оценка O(n) = n3 + n2.

И в заключение. Не уверен, что пост заслуживает инвайта, потому как моя причастность к алгоритму более чем сомнительная. Но опубликования, как мне кажется, стоит. Надеюсь модераторы разберутся.
Как там греки говорили? — Fais se que dois adviegne que peut (делай, что должно, и будь, что будет).
(или это были римляне?)