Двудольные графы и парасочетания

Определение: Граф G = (V,E) называется двудольным графом (биграфом), если множество V его вершин допускает разбиение на 2 непересекающихся подмножества V1 и V2 (две доли). Причем каждое ребро графа соединяет вершины из различных долей. Обозначается через G = (V1,V2,E) – двудольный граф с долями V1 и V2. Будем считать, что |V1| ≤ |V2|.

Определение: Двудольный граф G = (V1,V2,E) есть полный двудольный граф, если каждая вершина из V1 соединена ребром с каждой вершиной из V2. Обозначается через Km,n – полный двудольный граф G = (V1,V2,E), у которого n= |V1|, m = |V2|. Звезда – полный двудольный граф K1,p.

Теорема: граф G – двудолен ⇔ все простые циклы в G имеют четную длину(четное число ребер).

Необходимость⇒: пусть граф G = (V,E) = (V1,V2,E) двудолен. И пусть C = v1e1v2e2v3e3v4…vn-1en-1vn (v1 = vn) есть простой цикл в G длины n-1. Тогда v1, v3, v5, v7 ∈ V1, а v2, v4, v6, v81 ∈ V2, т.е. вершины с нечетными номерами лежат в V1, а с четными в V2. Т.к. vn=v1, то vn – нечетен. Тогда длина цикла n-1 есть четное число.

⇐Достаточность: Пусть G = (V,E) есть граф, в котором все простые циклы имеют четную длину. Можно считать, что граф G связен, ибо каждая компонента связности графа G может рассматриваться по отдельности. Пусть v1 ∈ V есть произвольная вершина в связном графе G и пусть множество вершин V1 = {v∈V: расстояние между v и v1 — четно}, тогда V2 = V– V1 есть множество вершин находящихся от v1 на нечетном расстоянии. Покажем, что всякие две вершины в V2 не могут быть соединены в G ребром. Допустим противное: пусть пара вершин u,v ∈ V2 соединена в G ребром e=(u,v). Пусть [v1, u] и [v1, v] – есть две геодезические (нечетной длины) линии. Тогда [v1, u] ∪ {e} ∪ {v, v1} – есть простой цикл в G нечетной длины. А это есть противоречие с условием.

Следовательно любые две вершины в V2 несмежны. Аналогично можно показать, что любые две вершины в V1 также несмежны. Поэтому ребра в графе G соединяют вершины из разных множеств V1,V2, => граф G двудолен. Доказано.

Паросочетания

Определение: Паросочетание есть двудольный граф, в котором всякие два ребра не являются смежными.

Паросочетание P для графа G=(V,E) есть всякое множество попарно несмежных ребер в G. P есть наибольшее паросочетание для G, если число ребер в Р наибольшее среди всех паросочетаний для G и P есть максимальное (тупиковое) паросочетание для G, если всякое добавление ребра к Р делает Р не паросочетанием.

P – есть совершенное паросочетание для G, если P имеет мощность |V| вершин (покрывает все вершины из V).

Замечание: Наибольшее паросочетание – максимально. Совершенное паросочетание является наибольшим и максимальным.

Простая цепь С ненулевой длины в G, ребра которой попеременно лежат и не лежат в P, называется чередующейся цепью (относительно паросочетания P). Эта цепь С называется P-увеличителем, если первое и последнее ребра цепи лежат вне Р. С помощью Р-увеличителя С паросочетание Р может быть переделано в другое паросочетание P’ для G с числом ребер в Р’ на единицу больше, чем в Р. Для этого достаточно все ребра в С, лежащие вне Р, добавить в Р, а ребра в С, лежащие в Р, удалить из Р. Для получившегося паросочетания Р’ можно снова искать увеличитель и т.д., последовательно расширяя полученное паросочетание, пока это возможно.

Теорема: если паросочетание Р для графа G не является наибольшим, то граф G имеет Р – увеличитель.

Доказательство: Если паросочетание Р, которое задается множеством его ребер для G, то G имеет другое паросочетание Р’ с большим числом ребер, чем в Р. В подграфе графа G, образованном множеством вершин (Р-Р’)U(P’-P) степень каждой вершины не больше 2. Следовательно, каждая компонента связности этого подграфа есть простая цепь ( простой цикл) с чередующимися ребрами из Р и из Р’.

Среди этих компонент можно найти простую цепь нечетной длины, начинающуюся и заканчивающуюся ребрами из Р’, иначе |P’|<|P|. Противоречие. Поэтому эта цепь - Р-увеличитель в G. Следствие: если граф G не имеет Р-увеличителя, то паросочетание Р для графа G является наибольшим.

Теорема: Граф G=(V,E) имеет совершенное паросочетание <=> для ∀v’⊆V , где n(G-v’)≤|V| есть число таких компонент связности подграфа G-v’ графа G, которые имеют нечетное число вершин.

Алгоритм построения совершенного паросочетания для двудольного графа
Пусть G = (U,V,E) – двудольный граф. Выберем исходное паросочетание P1 (наПример одно ребро графа G). Допустим, что паросочетание Pi = (Ui,Vi,Ei) для G построено.

Построим паросочетание Pi+1 для G следующим образом.
1) Выберем u из U но не из Pi. Если такой вершины u нет, то Pi – совершенное паросочетание. Строим в G чередующуюся цепь μi = (u1v1u2v2,….. upvp) c u1 = u в которой всякое ребро (ui,vi) не принадлежит Ei. А всякое ребро (vi,ui+1)∈ Ei, Если такой цепи нет, то совершенного паросочетания граф G не имеет, а паросочетание Pi является для графа G максимальным. Цепь μi есть Рi-увелечитель.
2) Выбрасываем из Pi все ребра (vi, ui+1) и добавляем все ребра (ui,vi) цепи ui. Получившееся паросочетание Pi+1 на одно ребро длиннее паросочетания Pi.
3) GOTO 1.


Оставить комментарий





Статистика

Рейтинг@Mail.ru