Matchings and b-matchings

Максимално двойкосъчетание


страницата се нуждае от дописване/преглеждане


Въведение в задачата

Задачата остава същата - да се намери max-matching в неориентиран граф G = (V, E), с максимална големина (припомнете си защо търсим max max-matching). съществуват много задачи, които се свеждат до този проблем:

  1. Има n работи и p работника, всеки работник ще иска дадена сума да изпълни дадена работа, намери двойкосъчетанието работник-работа с минимална цена.
  2. Имаш N на брой нощни пазачи, като не всеки се търпи с всеки. Шефа ти е наредил така да ги групираш по двойки, та да има максимален брой различни двойки (задачата в самия край на темата).

Дефиниция: Нека е даден граф G = (V, E) и matching K в G. Алтерниращ път M в G по отношение на K ще наричаме верига, в който ребрата се редуват - едно е от K, друго не е в K.

Дефиниция: Нарастваща алтернираща верига - верига, която е алтернираща и в двата си края свързва 2 изолирани върха. Изолиран връх ще казваме на връх не засегнат от matchinga.

Последното понятие е от огромна важност при решаване на max-matching проблема. Ето пример как от нарастваща верига на matching с големина 2 лесно се стига до matching с големина 3 (+1). Просто променяме принадлежността на ребрата по веригата (ако е било от matchinga, вече не е и обратно).

narastaltputnx7.png
(с пунктир са маркирани ребрата, които са извън matchinga)

Лема1: Нека G = (V, E) е неориентиран граф, и в него са дадени два различни matching-а K и K`. Тогава свързаните компоненти в частичния граф H = (V, U), където U = K Δ K` = (K - K`)⋃(K` - K) са от 3 типа:

  1. изолирани върхове;
  2. елементарен четен цикъл, в който ребрата се редуват по принадлежност в K и K`;
  3. елементарна верига, в която пак ребрата се редуват по принадлежност;

Теорема: Matching K е максимален (отсега нататък под такава формулировка, разбирайте max max-matching) ⟺ не съществува нарастваща алтернираща верига по K.

Следствие 1: Matching K с неповече от един непокрит връх (връх, който не е инцидентен с нито едно ребро от matching-a) е максимален.

Следствие 2: Нека K е максимален matching в G = (V, E). Тогава всеки друг максимален matching K` в G може да бъде променен до K, чрез серия от трансфери или по четните вериги (компонента тип 3 от лемата), или по четните цикли (компонента тип 2) в графа H = (V, U), също от лемата.

Малко по малко горните открития формират алгоритъм, за намиране на максимален matching в граф. Остава да се справим само с някои по-деликатни моменти. Засега се говори само за вериги и четни цикли, това не е случайно. За целта на алгоритъма ще разгледаме специална техника за "свиване" на цикли с нечетна дължина.

Дефиниция: кондензиран граф G/Y ще наричаме граф, индуциран от G = (V, E), след свиване на група върхове Y ⊂ V и заменянето им с единствен връх y. Тоест - G/Y = (V`, E`), където:

(1)
\begin{align} E` = \begin{cases} (i,j) & \mbox{i } \in V - Y, \mbox{ and } j \in V - Y} \\ (i,y) & \mbox{i } \in V - Y, \mbox{ and } j \in Y} \\ \end{cases}\\ \end{align}

V` = V - Y + {y}.

Лема 2: Ако Y ⊂ V е множество от върхове, формиращо нечетен елементарен цикъл μ в G, като |Y| = 2k + 1. Ако К1 e matching в G/Y, тогава съществува максимален matching Кμ на μ, такъв че K = K1 ⋃ Kμ е matching в G.

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

Алгоритъм за намиране на максимален matching по брой ребра в него

Както и преди, първоначално разглеждаме проблема в граф с еднакво тегло на всички дъги, константата единица. Алгоритъмът за максимален matching се води като един от най-сложните за имплементация в информатиката (поне от по-популярните алгоритми). Имайки в предвид сложността на алгоритъма, първо ще скицирам по-общо(какво). Ако искате само да разберете, за какво става дума, или просто да можете да решавате matching проблеми на лист, това ще е достатъчно. Честно казано и за изпита, предполагам, ще е достатъчно, стига теорията да е разбрана и идеята да е напълно ясна. По-надолу ще приложа C++ код с подробни коментари (как).
Идеята е да се разглежда графът по компоненти, които наричаме "Унгарски дървета" или "Flower trees". Ето и самият алгоритъм.

Инициализация:
Както казах сега само обяснявам, какво се прави, няма да се спирам на помощни масиви и т.н. Само ще спомена един много важен факт - алгоритъмът започва с готов произволен matching. Както видяхме, в действие на алгоритъмът от един matching може да се премине във всеки друг, затова няма грешен избор. Няма и теорема, която да ни казва кой е верния избор, освен може би теоремата на Мечо Пух (Winnie the Pooh) : "Колкото повече, толкова повече". Добър начин за начален избор е грийди алгоритъм.
Пример е това, да се подбират ребра за базовия matching M, като им се прави оценка на базата на степента на двата върха, които свързват (оценка на (i, j) = di + dj). Избира се реброто с най-ниска оценка, нека е (i0,j0), и се слага в M, правят се нови оценки на останалите извън М ребра, като се игнорират ребра инцидентни с i0 и j0 (за да е matching все пак), игнорираните ребра не се броят в степените на непокритите от M върхове.

Action:

Строене на алтерниращо дърво с корен υ

Начало :
Започваме с дърво от един връх - корена - T = (Y, U) : U = ∅, Y = {υ}. υ е маркиран четен.
С L(v) ще бележим веригата от v до υ в T.
m е брояч, който ни казва колко цикли с нечетна дължина сме свили.
бележим с D(A) , A ⊂ V, множеството от ребрата инцидентни с върховете от А.

Стъпки:
На всяка стъпка, T ни е текущото алтерниращо дърво. Опитваме да го разширим, като прибавяме ребра и върхове. Възможни са 4 варианта:

  1. съществува четен връх i и ребро u = (i, j), такова че j е изолиран и немаркиран. Тогава веригата L` = L(i) + {u} e нарастваща алтернираща верига. Увеличаваме matching-a ни M и край (трябва да започнем ново алтерниращо дърво с нов корен).
  2. съществува четен връх i и ребро u = (i, j), такова че j е от matching-a и е немаркиран. Нека u`= (j, k) е реброто от matching-a М съответстващо на j. Разширяваме T = (Y ∪ {j, k}, U ∪ {u, u`}). Маркираме j нечетно, k четно. Продължаваме.
  3. съществува ребро, свързващо два четни върха. Тогава сме открили нечетен цикъл μ. Заместваме всички върхове от μ с нов псевдо-връх μm маркираме μm четен, m++. Променяме T до кондензирания T/μ, G до G/μ. Продължаваме.
  4. щом като никой от горните варианти не се е случил, то сме открили максимално алтерниращо дърво за υ. Трием в G върховете от Т (G = (V/Y, E/D(Y))). край.

Алгоритъм за max matching

  1. Започваме с произволен matching М (може и празен).
  2. Ако има по-малко от 2 изолирани върха във V, край, M е максимален. Иначе строим алтерниращо дърво за произволен изолиран i0, υ = i0.
  3. Ако сме открили нарастваща верига в дървото от 2., реконструираме M върху G и премахваме всякаква маркировка на ребрата, влезли в последното алтерниращо дърво. goto 2.

Сложност: При правилна имплементация, нормалната сложност е O(N3). Казвам нормална, понеже все ще се намери някоя шваба или някой с име на луксозна прахосмукачка, който да се е трудил активно 10 години за да подобри трудност от порядъка на O(N2) до O(N*sqrt(N + logα(min{β(N8), M1.5}), където α е n-тото мерсеново просто число, а β е изключително бавно растяща функция, съответстваща на обратната функция на едноаргументната функция на Акерман; съответно кода за имплементация нараства от 350 на 1800 реда. Сега сериозно - този алгоритъм е най-правилния пример, за това как избора за представяне на граф е ключов за определяне на сложността на алгоритъма.

Ето пример на работата на алгоритъма над граф с 8 върха:

72000302vy1.png
Първоначалният ни matching е с големина 3 : M = {(2,3), (4,5), (6,7)}. Започваме да строим алтерниращо дърво от връх 1.
30034206fd6.png
Намерили сме и сме откъснали цвят μ0 = {1, 2, 3}.
68827351ow1.png
Намерили сме и сме откъснали цвят μ1 = {μ0, 4, 5}.
29622784kd1.png
Намерили сме и сме откъснали цвят μ2 = {μ1, 6, 7}. Не получаваме алтерниращо дърво с корен μ2 , понеже листо е нечетно ⟹ имаме нарастваща алтернираща верига. Слагаме реброто (μ2, 8) в M. Matching-a е с максимална стойност (⎣|V| / 2⎦), започваме стъпка v) - реконструкция.
13075571jq6.png
Ето първата крачка от реконструкцията върви по свитите цветове и ги разтваря в ред обратен на този, в който са били създадени. Причината за обратния ред е ясна - псевдо връх съответстващ на цвят може да участва в друг цвят, по-късно създаден. Точно такъв случай имаме и тук:
57368074fm5.png
13077649hl6.png

Примерна задача: http://acm.timus.ru/problem.aspx?space=1&num=1099.

Алгоритъм за намиране на максимален matching по тегло на ребрата в него

( C++ code for non-weighted version, може би никога (sun) …)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License