Поиск минимального контролирующего множества вершин в двудольном графе

Определение и постановка задачи.

Пусть имеется граф G = (V, E). Множество вершин V', содержащееся в V, называется контролирующим, если каждое ребро графа инцидентно хотя бы одной вершине из V'. Тривиальным примером контролирующего множества является множество всех вершин V. Задача состоит в том, чтобы в данном двудольном графе найти какое-либо контролирующее множество вершин минимальной мощности.

Связь с задачей о наибольшем паросочетании.

Начиная с этого момента речь будет идти о двудольном графе G = (V, E), где V = L + R, L и R — доли графа.

Утверждение. Каковы бы ни были паросочетание E' и контролирующее множество вершин V' в графе G, |E'| <= |V'|. Это утверждение немедленно следует из того, что каждое ребро паросочетания E' должно быть инцидентно какой-то вершине из V', и все концы этих ребер различны.

Из этого утверждения следует, в частности, что количество вершин в наименьшем контролирующем множестве V* не меньше количества ребер в наибольшем паросочетании E*. Оказывается, эти количества обязательно совпадают. Для доказательства этого факта приведем алгоритм, который найдет по заданному наибольшему паросочетанию E* контролирующее множество мощности |E*|.

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

Рассмотрим в качестве примера двудольный граф, показанный на рисунке.

Рисунок 1. Построение контролирующего множества

Максимальное паросочетание состоит из 4 ребер, отмеченных на рисунке красным цветом. Ориентируем ребра паросочетания влево, а все остальные ребра - вправо. Инициализируем наше множество V' множеством левых концов ребер, входящих в паросочетание. Элементы множества V' на рисунке отмечеты серым. Такое множество V' вероятнее всего не является контролирующим в графе G, но оно является таковым в его подграфе, индуцированном левыми концами ребер паросочетания и всеми вершинами правой доли (на рисунке эти вершины показаны серым и коричневым цветами).

Алгоритм состоит в том, чтобы модифицировать множество V', при этом увеличивая подграф, в котором множество V' является контролирующим. Будем добавлять к нашему подграфу свободные вершины из левой доли по одной. На рисунке показаны ситуации после добавления свободной вершины a5 и затем свободной вершины a6.

Множество V' (назовем его вершины отмеченными) на каждом шаге будет удовлетворять тому свойству, что ровно один конец каждого ребра паросочетания является отмеченным. Ребро паросочетания будем называть левым, если отмечен его левый конец, и правым, если отмечен его правый конец. Изначально все ребра левые. В ходе работы алгоритма некоторые из них станут правыми.

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

Итак, из свободной вершины v в левой доле достижимы только несвободные вершины. Все они инцидентны левым реберам паросочетания (так как при построении W вершины всех правых ребер мы удалили). При этом очевидно, что оба конца ребра паросочетания в W либо одновременно входят, либо одновременно не входят. Теперь те ребра, чьи концы вошли в W, сделаем правыми. Например, при добавлении свободной вершины a5 (см.рисунок) множество W оказалось состоящим из вершин a2 и b2. В соответствии с этим при добавлении вершины a5 ребро (a2, b2) было сделано правым. Простой разбор возможных случаев показывает, что в результате такой модификации множество V' станет контролирующим множеством в увеличенном подграфе (с добавленной вершиной v). Проделав такие модификации V' для каждой свободной вершины в левой доле, получим контролирующее множество всего графа. При этом оно содержит ровно |E*| вершин, а значит является минимальным. Тем самым мы привели алгоритм построения минимального контролирующего множества по заданному наибольшему паросочетанию за время O(E) и доказали, что оценка |V*| >= |E*| на самом деле обращается в равенство.

Ссылки

• Реализация на C++
• Поиск наибольшего паросочетания

-- DanielShved - 23 Mar 2008

---