Задача определения паросочетаний в графе

1. Задача определения паросочетаний в графе

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

Рассмотрим подробнее паросочетание в двудольном графе.

G = (X, Y), где X = A B, A? B = .

Можно также записать.

G = (A B, U) или G = (A, B; U).

Подмножество ребер C U двудольного графа.

G = (A, B; U).

называется паросочетанием (ПС), если никакие два ребра из C не имеют общей вершины. Другими словами, ребра в С не являются идентичными друг другу. Тогда по аналогии с вышесказанным паросочетание С в двудольном графе.

G = (A, B; U).

называется максимальным (C U), если никакое другое паросочетание в G не содержит ребер больше чем С. Паросочетание C U в двудольном графе.

G = (A, B; U).

называется полным, если (x A, y B)((x, y) C). Другими словами, для любого x из, А существует y из B, что обязательно существует ребро (x, y) из С.

Пример 17.17. Пусть задан граф.

G = (A, B; U), |A| = 4, |B| = 4, |U| = 12, A = {1, 2, 3, 4}, B = {5, 6, 7, 8} (рис.).

Рис. 1 Двудольный граф G = (A, B; U)

Полное паросочетание имеет вид Cn = {(1, 5), (2, 6), (3, 7), (4, 8)}. Соответственно одно из возможных паросочетаний может иметь вид: C = {(1, 6), (3, 8)}. Максимальных паросочетаний может быть несколько. В нашем примере они совпадают по мощности с полным паросочетанием. Приведем МПС для двудольного графа (рис. 1).

МПС1 = {(1, 6), (2, 7), (3, 8), (4, 5)}.

МПС2 = {(2, 5), (3, 6), (4, 7), (1, 8)}.

Приведем определение. В двудольном графе G = (A, B; U) при C A, вводится подмножество.

R© = {y | y B b смежная с вершиной xi C}.

Существование полных паросочетаний можно определять на основе теоремы Холла.

Теорема 1. Двудольный граф G = (A, B; U) имеет полное паросочетание тогда и только тогда, когда для каждого подмножества C A справедливо |C| |R (C)|.

Доказательство теоремы следует из определения и способа построения R©.

Пусть в.

G = (A, B; U) C A и C B.

— подмножество вершин из С. Предположим, что |C| > |(C)|. Тогда очевидно, что не существует полного паросочетания и справедливо выражение.

|ПС| |A| - (|C| - |(C)|).

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

Здесь G = (A, B; U), А = {1, 2, 3, 4}, |А| = 4, В = {5, 6, 7}, |В| = 3, U = {(1,7), (2,7), (3,7), (3,5), (3,6), (4,7)}, |U| = 6. Имеем произвольное паросочетание ПС {(3,6), (4,7)}, |ПС| = 2.

Рис. 2 Двудольный граф

Пусть C A, С = {1, 2}. Тогда Г© = {7} и |С| = 2, |Г (С)| = 1. |ПС| 4 — (2 — 1), |ПС| 3. Пусть С = {1, 2, 4}, тогда Г© = {7} и |С| = 2, |Г (С)| = 1, тогда |ПС| 4 — (3 — 1), |ПС| 2 совпадает с |ПС| = 2.

Дефицитом © подмножества С множества, А называется выражение.

© = |C| - |(C)|.

Дефицит © графа G = (A, B; U) определяется следующим образом:

© = (|C| - |(C)|).

Тогда справедливо выражение.

|ПС| |А| - (G).

На этой формуле базируется теорема Кэнига.

Теорема 2. Число ребер в максимальном паросочетании двудольного графа G = (A, B; U) равно Из теоремы 2 следует, что минимальное число вершин двудольного графа, покрывающих все ребра, равно числу ребер в любом максимальном паросочетании этого графа.

|МПС| |A| - (G).

Опишем модифицированную эвристику построения максимального паросочетания в двудольном графе. Исходными данными являются двудольный граф, представленный в виде двух частей G = (A, B; U) и произвольное построение. Оно может состоять в частности из одного ребра.

Произведем разбиение подмножества, А на две части. В первую включаются вершины, в которые не входят ребра паросочетания. Во вторую часть включаются вершины, в которые входят ребра паросочетания. Если первая часть пуста, то исходное паросочетание является максимальным. Это следует из приведенных выше теорем.

Далее среди вершин второй части выбирается вершина xi с наименьшей локальной степенью. Если таких вершин несколько, то выбирается любая. Для выбранной вершины ищем ребро (xi, xj), которое не является ребром паросочетания, такое, что (xi, xj) (xj B). Затем продолжаем строить цепь назад по ребру паросочетания. Получаем цепь (xi, xj) (xj, xk), далее продолжаем аналогично. Работа заканчивается, когда нет возврата по ребру паросочетания. Далее из исходного паросочетания удаляются ребра, имеющиеся в цепи, и добавляются ребра, которые в нем отсутствуют.

Пример 17.19. Имеем двудольный граф.

G = (A, B; U),.

представленный на рис. 3. Задано исходное паросочетание ПС = {(1, 7), (2, 6)}. Разобьем подмножество, А = {1, 2, 3, 4, 5} на две части: A1 = {1, 2}, A2 = {3, 4, 5}. Начинаем с вершины 4, имеющей наименьшую локальную степень. Строим цепь 4 6 2 10. В этой цепи нет ребер, которые можно добавить в паросочетание. Оставшиеся вершины имеют одинаковую локальную степень, поэтому можем выбрать любую. Выбираем вершину 5 и строим цепь: 5 7 1 8 5. После анализа в паросочетание добавляем ребро (5, 8). Строим новую цепь 3 10. После анализа получаем, что ребро (3, 10) можно добавить к ПС. В результате построено МПС = {(1, 7), (2, 6), (5, 8), (3, 10)}, показанное жирными линиями на рис. 3.

Рис. 3 Максимальное паросочетание в двудольном графе G = (A, B; U)

Рассмотрим эвристику построения МПС на основе анализа специальной матрицы смежности и построение в ней «параллельных диагоналей».

Пример 17.20. Пусть задан граф G = (A, B; U) (рис. 4).

Рис. 4. Пример графа G = (A, B; U)

специальная матрица смежности этого графа запишется:

В матрице можно выделить семь «параллельных диагоналей»:

ПС1 = {(1, 7)} ПС5 = {(2, 9), (3, 10)}.

ПС2 ={(1, 9)} ПС6 = {(2, 11)}.

ПС3 ={(1, 11)} ПС7 = {(4, 8), (6, 10)}.

ПС4 ={(2, 7), (3, 8), (5, 10)}.

Каждая из таких диагоналей является паросочетанием исследуемого графа. Очевидно, при наличии всех единиц по главной диагонали матрицы мы получим максимальное паросочетание. Полученные диагонали можно представить в виде амплитуды (рис. 5).

Для дальнейших исследований выберем амплитуду ПС4 и на основе суперпозиции с другими диагоналями (ПСi), будет построено максимальное паросочетание.

паросочетание двудольный граф множество ПС1 ПС2 ПС3 ПС4 ПС5 ПС6 ПС7.

Рис. 5 Амплитуда паросочетаний

Для получения большего числа диагоналей с максимальным числом элементов произведем расширение матрицы:

Как видно, получено новое паросочетание ПС8 = ПС7 ПС3 = {(1, 11), (2, 7), (3, 8), (5, 10)},.

которое является максимальным.

Заметим, что матрицу можно расширить справа, слева, сверху и снизу. Например, для графа G, заданного матрицей.

построим расширенные матрицы сверху и снизу. Это дает возможность получить две новые диагонали с максимальным количеством элементов.

Такое расширение соответствует следующим операциям суперпозиции ПС1 = {(2, 5), (3,6), (4, 7)} {(1, 8)}, |ПС1| = 4;

ПС2 = {(1, 6), (2, 7), (3, 8)} {(4, 5)}, |ПС2| = 4.

Это позволяет получить два новых максимальных паросочетания ПС1 и ПС2.

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

Исходные данные: двудольный граф G = (A, B; U), |А|, |В|, матрица смежности.

• 1. Строится специальная матрица смежности.
• 2. Определяются диагонали матрицы, соответствующие паросочетаниям графа.
• 3. Строится амплитуда и из нее выбирается элемент с максимальным значением.
• 4. Производится суперпозиция максимальной диагонали с другими, путем расширения матрицы справа, слева, сверху и снизу.
• 5. Определяются максимальные паросочетания.
• 6. Конец работы алгоритма.

Время работы алгоритма зависит от размера анализируемой матрицы: чем больше размер матрицы, тем больше может потребоваться времени. В задачах на графах размер входа часто измеряется не одним числом, а двумя (число вершин n и число ребер m графа). Для задачи определения паросочетания в двудольном графе необходимо определить время работы алгоритма в худшем случае, среднее время работы алгоритма и и время работы алгоритма в лучшем случае.