Задача о наименьшем покрытии графа

Привет, Вы узнаете о том , что такое задача о наименьшем покрытии графа, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое задача о наименьшем покрытии графа, покрытие графа , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Основные определения

Рассмотрим неориентированный граф G = (V, E).

Независимое множество вершин (внутренне устойчивое множество) — это множество вершин графа G такое, что любые две вершины в нем не смежны, то есть никакая пара вершин не соединена ребром. Множество S ⊂ V, удовлетворяющее условию

называется независимым множеством вершин. Для графа, изображенного на рисунке 1, независимыми являются {x₇, x₈, x₂}, {x₃, x₁} множества вершин.

Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Если множество удовлетворяет условию (1) и условию

является максимальным независимым множеством. Например, множества {x₁, x₃, x₇} и {x₄, x₆} максимальные независимые, а {x₇, x₈, x₂} — нет. В графе может быть более одного независимого множества.

Если Q является семейством всех независимых множеств графа G, то

называется числом независимости графа G, а множество S*, на котором достигается этот максимум, называется наибольшим независимым множеством.

Пример: выбор проекта

Имеется n проектов, которые должны быть выполнены. Для выполнения проекта x_i требуется некоторое подмножетсво R_i наличных ресурсов из множества {1, …, p}. Пусть каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Построим граф G, каждая вершина которого соответствует некоторому проекту, а ребро (x_i, x_j) наличию общих средств обеспечения у проектов x_i и x_j. Максимальное независимое множество графа G представляет максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени.

В динамической системе происходит постоянное обновление проектов через определенный промежуток времени, так что каждый раз нужно заново повторять процедуру построения максимального независимого множества в соответствующем графе G. На практике не всегда можно выполнить работы, соответствующие максимальному независимому множеству. Тогда можно каждой работе (вершине x_i) сопоставить некоторый штраф p_i, который будет увеличиваться с увеличением срока исполнения работы. В каждый момент времени нужно выбирать из семейства максимальных независимых множеств такое множество, которое максимизирует некоторую функцию штрафов на вершинах, содержащихся в выбранном множестве.

Максимальный полный подграф (клика) графа G это порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин H, содержащем S, не является полным. То есть, в отличие от максимального независимого множества, в клике все вершины попарно смежны.

Аналогично тому, как было определено число независимости графа, с помощью соотношения (3) мы можем определить кликовое число графа (известное также как густота илиплотность). Это — максимальное число вершин в кликах данного графа. Тогда, образно говоря, у "плотного" графа кликовое число будет, вероятно, больше, а число независимости меньше, в то время как у "разреженного" графа, по всей вероятности, будет иметь место противоположное соотношение между этими числами.

Построение всех максимальных независимых множеств

Если граф небольшой (например, с числом вершин, не превосходящим 20), то построить максимальное независимое множество можно последовательным перебором независимых множеств с одновременной проверкой каждого множества на максимальность. Если же вершин много, то этот процесс становится сложным технически. Число максимальных независимых множеств возрастает, но во время поиска большое число независимых множеств формируется, а затем вычеркивается, так как обнаруживается, что они содержатся в других, ранее полученных множествах и поэтому не являются максимальными.

Обоснование алгоритма

Этот алгоритм является существенно упрощенным перебором, использующим дерево поиска. В процессе поиска — на некотором этапе k — независимое множество вершин S_k расширяется путем добавления к нему подходящим образом выбранной вершины (чтобы получилось новое независимое множество S_k+1) на этапе k+1, и так поступают до тех пор, пока добавление вершин станет невозможным, а порождаемое множество не станет максимальным независимым множеством. Пусть Q_k будет на этапе k наибольшим множеством вершин, для которогоS_k ∩ Q_k = Ø, то есть после добавления любой вершины из Q_k к S_k получается независимое множество S_k+1. В некоторый произвольный момент работы алгоритма множество Q_k состоит из вершин двух типов: подмножества Q_k^- тех вершин, которые уже использовались в процессе поиска для расширения множеств S_k, и подмножества Q_k⁺ таких вершин, которые еще не использовались. Тогда дальнейшее ветвление в дереве поиска включает процедуру выбора вершины x_ik ∈ Q_k⁺, добавление ее к S_k для построения множества

и порождение новых множеств:

и

Шаг возвращения алгоритма состоит в удалении вершины x_ik из S_k+1, чтобы вернуться к S_k, изъятии x_ik из старого множества Q_k⁺ и добавлении x_ik к старому множеству Q_k^- для формирования новых множеств Q_k⁺ и Q_k^-.

Множество S_k является максимальный независимым множеством только тогда, когда невозможно его дальнейшее расширение, т. е. когда Q_k⁺ = Ø. Если Q_k⁺ ≠ Ø, то текущее множество S_kбыло расширено на некотором предшествующем этапе работы алгоритма путем добавления вершины из Q_k^-, и поэтому оно не является максимальным независимым множеством. Таким образом, необходимым и достаточным условием того, что S_k — максимальное независимое множество, является выполнение равенств

Если очередной этап работы алгоритма наступает тогда, когда существует некоторая вершина х ∈ Q_k^-, для которой E(x) ∩ Q_k⁺ = Ø, то безразлично, какая из вершин, принадлежащих Q_k⁺, используется для расширения S_k, и это справедливо при любом числе дальнейших ветвлений; вершина х не может быть удалена из Q_p^- на любом следующем шаге р > k. Об этом говорит сайт https://intellect.icu . Таким образом, условие

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

Как и во всяком методе, использующем дерево поиска, здесь выгодно стремиться начать шаги возвращения как можно раньше, поскольку это ограничит "размеры" "ненужной" части дерева поиска. Следовательно, целесообразно сосредоточить усилия на том, чтобы возможно раньше добиться выполнения условия (8) с помощью подходящего выбора вершин, используемых при расширении множеств S_k. На каждом следующем шаге процедуры можно выбирать для добавления к S_k любую вершину x_ik ∈ Q_k⁺ на шаге возвращения x_ik будет удалена из Q_k⁺ и включена в Q_k^-. Если вершину x_k выбрать так, чтобы она принадлежала множеству E(х) при некоторой вершине х из Q_k^-, то на соответствующем шаге возвращения величина

уменьшится на единицу (по сравнению с тем значением, которое было до выполнения прямого шага в шага возвращения), так что условие (8) теперь станет выполняться раньше.

Таким образом, один из возможных способов выбора вершины x_ik для расширения множества S_k состоит, во-первых, в нахождении вершины x^* ∈ Q_k^- с возможно меньшим значением величины Δ(х^*) и, кроме того, в выборе вершины x_i из множества E(x^*) ∩ Q_k⁺. Такой выбор вершины x_ik будет приводить на шаге возвращения к уменьшению величины Δ(x^*) — каждый раз на единицу — до тех пор, пока вершина x^* не станет удовлетворять условию (8) при выполнении шага возвращения.

Следует отметить, что поскольку на шаге возвращения вершина x_ik попадает в Q_k^-, то может оказаться, что при этом новом входе значение величины Δ меньше, чем для ранее фиксированной вершины x^*. Значит, надо проверить, не ускорит ли эта новая вершина выполнение условия (8). Это особенно важно в начале ветвления, когда Q_k^- = Ø.

Описание алгоритма

1. Пусть S₀ = Q_k^- = Ø, Q₀⁺, Q_k^- = V, k = 0.
2. Выбрать вершину x_ik ∈ Q_k⁺, как упоминалось ранее, и сформировать S_k, Q_k+1^- и Q_k+1⁺, оставляя Q_k^- и Q_k⁺ нетронутыми. Положить k = k + 1.
3. Если удовлетворяется условие (8), то перейти к шагу 5, иначе к шагу 4.
4. Если Q_k⁺ = Q_k^- = Ø, то напечатать максимальное независимое множество S_k и перейти к шагу 5. Если Q_k⁺ = Ø, a Q_k^- ≠ Ø, то перейти к шагу 5. Иначе перейти к шагу 2.
5. Положить k = k − 1. Удалить x_ik из S_k + 1, чтобы получить S_k. Исправить Q_k^- и Q_k⁺, удалив вершину x_ik из Q_k⁺ и добавив ее к Q_k^-. Если k = 0 и Q_k⁺ = Ø, то остановиться. (К этому моменту будут уже напечатаны все максимальные независимые множества.) Иначе перейти к шагу 3.

Доминирующие множества

Для графа G = (V, E) доминирующее множество вершин (называемое также внешне устойчивым множеством) есть множество вершин S ⊆ E, выбранное так, что для каждой вершины x_j, не входящей в S, существует дуга, идущая из некоторой вершины множества S в вершину x_j.

Таким образом, S есть доминирующее множество вершин, если

Для графа, приведенного на рис. 2, множества вершин {x₁, x₄, x₆}, {x₁, x₄}, {x₃, x₅, x₆} являются доминирующими множествами.

Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем.

Множество S является минимальным доминирующим множеством, если оно удовлетворяет соотношению (10) и нет собственного подмножества в S, которое удовлетворяет условию, аналогичному (10). Так, например, для графа, приведенного на рис. 2, множество {x₁, x₄} — минимальное, а {x₁, x₄, x₆} нет. Минимальным доминирующим множеством является также множество {x₃, x₅, x₆}, и еще существует несколько таких множеств в этом графе. Следовательно, как и в случае максимальных независимых множеств, в графе может быть несколько минимальных доминирующих множеств, и они не обязательно содержат одинаковое число вершин.

Если Р — семейство всех минимальных доминирующих множеств графа, то число

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

Для графа, приведенного на рис. 2, наименьшим доминирующим множеством является множество {x₁, x₄} и, следовательно, β[G] = 2.

Задача о наименьшем покрытии

Пусть A^t — транспонированная матрица смежности графа G с единичными диагональными элементами. Задача определения наименьшего доминирующего множества графа Gэквивалентна задаче нахождения такого наименьшего множества столбцов в матрице A^t, что каждая строка матрицы содержит единицу хотя бы в одном из выбранных столбцов. Эта последняя задача о поиске наименьшего множества столбцов, «покрывающих» все строки, изучалась довольно интенсивно под названием задачи о наименьшем покрытии (ЗНП).

В общей ЗНП матрица, состоящая из 0 и 1, не обязательно является квадратной. Кроме того, каждому столбцу j (в нашем случае каждой вершине x_j) сопоставляется некоторая стоимость c_j и требуется выбрать покрытие (или, в другой терминологии — для случая графов — доминирующее множество вершин) с наименьшей общей стоимостью). Поскольку задача построения наименьшего доминирующего множества вершин является весьма частной задачей о покрытии с c_j = 1 для всех j = 1, …, n, то на первый взгляд кажется, что нахождение такого множества осуществляется на деле значительно проще, чем решение общей ЗНП.

Постановка задачи

ЗНП своим названием обязана следующей теоретико-множественной интерпретации. Даны множество R = {r₁, …, r_M} и семейство I = {S₁, …, S_N} множеств S_j ⊂ R. Любое подсемейство I′ = {S_j¹, S_j², …, S_j^k} семейства I, такое, что

называется покрытием множества R, а множества S_jⁱ называются покрывающими множествами. Если вместе с соотношением (12) I′ удовлетворяет условию

т. е. множества S_jⁱ {i = 1, …, k} попарно не пересекаются, то называется разбиением множества R.

Если каждому S_j ∈ I поставлена в соответствие положительная стоимость c_j, то ЗНП формулируется так: найти покрытие множества R, имеющее наименьшую стоимость, причем стоимость семейства I′ = {S_j¹, …, S_j^k} определяется как ∑_i = 1^k c_jⁱ. Аналогично формулируется и задача о наименьшем разбиении (ЗНР).

Упрощение задачи

Вследствие особой природы ЗНП часто удается сделать при ее исследовании определенные, хорошо известные заранее выводы и упрощения. Например:

1. если для некоторого элемента r_i из R справедливы соотно шения r_i ∉ S_j ∀ j = 1, …, N, то r_i покрыть нельзя и, следова тельно, задача не имеет решения;
2. если ∃r_i ∈ R такое, что r_i ∈ S_k и r_i ∉ S_j, то S_k должно присутствовать во всех решениях и задачу можно свести к меньшей, положив R = R − {r_i} и I = I − {S_k}
3. пусть V_i = {j | r_i, ∈ S_j}; тогда если ∃p, q ∈ {1, …, M} такие, что V_p ⊆ V_q, то r_q можно удалить из R, поскольку любое множество, которое покрывает r_p, должно также покрывать r_q, т. е.r_p доминирует над r_q;
4. если для некоторого семейства множеств I′ ⊂ I справедливы соотношения ∪_Sj∈I′S_j ⊇ S_k и ∑_Sj∈I′ c_j ≤ S_k для любых S_k ∈ I − I′, то S_k может быть вычеркнуто из I поскольку ∪_Sj∈I′S_jдоминирует над S_k.

Предположим, что все эти упрощения выполнены (если они возможны) и что исходная ЗНП уже переформулирована в соответствующей неприводимой форме.

Алгоритм решения ЗНР, использующий дерево поиска

ЗНР тесно связана с ЗНП, являясь по существу ЗНП с дополнительным ограничением (неперекрываемость). Это ограничение выгодно, если решать задачу с помощью некоторого метода, использующего дерево поиска: при таком ограничений может рано выясниться, что некоторые возможные ветвления дерева рассматривать не надо,

Простые методы решения ЗНР, использующие дерево поиска, были предложены Пирсом, Гарфинкелем и Немхаузеро.

Сущность этих методов такова. Вначале строятся "блоки" столбцов, по одному на каждый элемент r_k из R, т. е. всего М блоков, k-й блок состоит из таких множеств семейства I(представленных столбцами), в которых содержится элемент r_i, но отсутствуют элементы с меньшими индексами — r₁, …, r_k−1. Следовательно, каждое множество (столбец) появляется точно в одном определенном блоке и совокупность блоков может быть представлена в виде таблицы. В конкретных задачах некоторые из блоков могут отсутствовать.

В процессе работы алгоритма блоки отыскиваются последовательно и формирование k-гo блока начинается после того, как каждый элемент r_i 1 ≤ i ≤ k − 1, будет покрыт частным решением. Таким образом, если какое-то множество в блоке k содержит элементы с индексами, меньшими k, то оно должно быть отброшено (на этом этапе) в соответствии с требованием неперекрываемости. Множества в пределах каждого блока размещаются в порядке возрастания их стоимостей и перенумеровываются так, что S_k теперь уже обозначает множество, соответствующее j-му столбцу таблицы.

Текущее "наилучшее" решение B′ сo стоимостью z′ известно на любом этапе поиска (B′ обозначает семейство соответствующих покрывающих множеств). Если В и z — соответствующие семейство и стоимость на данной стадий поиска, а Е — множество, представляющее те элементы (т. е. строки) r_i, которые покрываются множествами из В, то одна из простых алгоритмов, использующих дерево поиска, можно вписать следующим образом.

1. Построить исходную таблицу и начать с частного решения: B = Ø, E = Ø, z = 0, z′ = ∞.
2. Найти р = min[i |r_i ∉ E]. Над блоком р поставить метку (над его первым множеством, которое, как следует из построения таблицы, имеет наименьшую стоимость).
3. Начиная с отмеченной позиции в блоке р, перебирать его множества S_j^p скажем, в порядке возрастания индекса j.
   (i) Если найдено множество S_j^p, такое, что S_j^p ∩ E = Ø и z + c_j^p < z′ (где c_j^p — стоимость множества S_j^p), то перейти к шагу 5.
4. В не может привести к лучшему решению. Если B = Ø (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является B′. В противном случае удалить последнее множество, скажем, S_n^l добавить его в В, положить р = I, поставить метку над множеством S_k+1^l, удалить предшествующую метку в блоке I и перейти к шагу 3.
5. Обновить данные: B = B ∪ {S_j^p}, E = E ∪ S_j^p, z = z + c_j^p. Если найдено лучшее решение Е = R, то положить B′ = B, z′ = z и перейти к шагу 4. Иначе перейти к шагу 2.

Если поиск оканчивается с исчерпыванием блока 1 (см. шаг 4), то целесообразно переставить блоки в порядке возрастания числа столбцов (множеств) в каждом блоке. Это может быть осуществлено (перед построением исходной таблицы) перенумерацией элементов (строк) r₁ … r_M в порядке увеличения числа множеств из S, содержащих соответствующие элементы.

Применение задачи о покрытии

Выбор переводчиков

Предположим, что организации нужно нанять переводчиков французского, немецкого, греческого, итальянского, испанского, русского и китайского языков на английский и что имеется пять кандидатур А, В, С, D и Е. Каждая кандидатура владеет только некоторым собственным подмножеством из указанного выше множества языков и требует вполне определенную зарплату. Необходимо решить, каких переводчиков (с указанных выше языков на английский) надо нанять, чтобы затраты на зарплату были наименьшими. Это задача о наименьшем покрытии.
Если, например, требования на оплату труда у всех претендентов одинаковые и группы языков, на которых они говорят, указаны ниже в матрице Т, то решение задачи будет таким: нужно нанять переводчиков В, С, D.

Информационный поиск

Предположим, что некоторое количество единиц информации хранится в N массивах длины c_j, j = 1, 2, …, N, причем на каждую единицу информации отводится по меньшей мере один массив. В некоторый момент делается запрос о М единицах информации. Они могут быть получены различными способами при помощи поиска в массиве. Для того чтобы получить все Mединиц информации и при этом произвести просмотр массивов наименьшей длины, надо решить ЗНП, вкоторой элемент t_i j матрицы T равен 1, если информация i находится в массиве, и 0 в противном случае.

Маршруты полетов самолетов

Пусть вершины неориентированного графе G представляют аэропорты, а дуги графа G — этапы полетов (беспосадочные перелеты), которые осуществляются в заданное время. Любой маршрут в этом графе (удовлетворяющий ряду условий, которые могут встретиться на практике) соответствует некоторому реально выполнимому маршруту полета. Пусть имеется N таких возможных маршрутов и для каждого из них каким-то способом подсчитана его стоимость (например, стоимость j-го маршрута равна c_j). Задача нахождения множества маршрутов, имеющего наименьшую суммарную стоимость и такого, что каждый этап полета содержится хотя бы в одном выбранном маршруте, является задачей о наименьшем покрытии с матрицейТ = [t_i j] в которой элемент t_i j равен 1, если i-й этап содержится в j-м маршруте, и равен 0 в противном случае.

Выводы из данной статьи про задача о наименьшем покрытии графа указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое задача о наименьшем покрытии графа, покрытие графа и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов