4.2: Flows and Transportation Networks Part 2

Теореми и Задачи върху Потоци в мрежа.

Min-Cover и Max-Matching

Matching: Множество от дъги на графа G, никои две от които не са съседни наричаме matching в графа. Maximal-Matching е matching, който не може да бъде разширен повече с дъги над G. Maximum-Matching за G e най-големия Maximal-Matching върху G. От сега нататък ще бележа Maximum-Matching с Max-Matching. Задачата за намиране на Max-Matching е полиномиално разрешима (P).

Cover: Множество от върхове, които срещат всички дъги в графа, наричаме cover (покритие) на графа. Задачата за намиране на минимално покритие (Min-Cover) e NP в общия случай, изключение правят някои специални графи.

Задача: Дадена е произволна правоъгълна таблица MxN с нули в някои от позициите й. Дефинираме понятието независимо подмножество от нули като подмножество от нули в таблицата, такова че не съществуват две нули в един ред или стълб. Да се намери максимално по големина независимо подмножество по дадена таблица.
Двойнствената на горната задача, е задачата за триене на нули по редове и стълбове. По точно казано, по дадена таблица идентична с таблицата от първата задача, колко минимум реда и стълбове трябва да бъдат избрани от нея, за да попаднат всички нули в тях. Нека наречем тази задача, задачата за минимално триене на нули (МТН).

Защо се спираме на последната задача? Ами за пореден път двуделните графи се проявяват като по-специални и за тях NP пълния в общия случай проблем Min-Cover е еквивалентен на задачата за МТН и естествено двата проблема се решават с Max-Flow (удобно, а?). Да разгледаме примерна таблица 5x6 и граф по нея $G = (X\bigcup Y, A)$.

0
0
0 0
0
0

Построяваме граф за таблицата по метод, подобен на метода, с който построихме граф за bipartite non-capacitated Match problem.
grafi4bf9.jpggrafi5ob5.jpg
Първоначално всички дъги са черни и са с посока от s към t. С червено на картинка I е отбелязан потокът по G, след като е завършил алгоритъмът за Max-Flow. След намиране на оптималния поток $\phi$, в компонентата $\phi_0$ се крие решението за Min-Cover и МТН за нашия двуделен граф. Време е да видим, за кои върхове / редове и стълбове се постига това оптимално решение. Затова са квадратчетата около някои от върховете на картинка II - това са етикети. А именно, след като е приключил алгоритъма, като резултат е останал инкрементален граф $G_\phi$, в който няма ориентиран път от s към t (Защо?). В $G_\phi$ прилагаме процедурата с етикети и маркиране на върхове за последен път. Нека със Z означим множеството от върхове, които след края на процедурата са получили етикети, т.е. съществува инкрементален път от s до тях (на картинка II този инкрементален път е отбелязан в синьо).

Теорема: $(\overset{-}{Z}\bigcap X) \bigcup (Z\bigcap Y)$ е cover Т на графа G.

Теорема на Konig-Egeway: За произволен двуделен граф $G = (X\bigcup Y, A)$ Max Matching = Min cover.

**Теорема на Konig-Hall: ** Даден е граф $G = (X \bigcup Y, A)$ и множество z : $z \subset X$. Нека с N(z) отбележим множеството от върхове : $N(z) \subset Y | \{\exists (i, j) \in A | i \in z \mbox{ and } j \in N(z) \}$, т.е. има дъгa до всеки връх в N(z) от някой връх от z. Toгава Max-Matching = |X| т.с.т.к. $\forall z \subset X, |N(z)| \ge |z|$.

Втори вариант на Теорема на Konig-Hall: Дадени са k на брой множества, S1, S2, … Sk, с елементи числата от 1 до n. Кога можем да кажем, че при какъвто и да е подбор на m на брой множества, ще се намерят не по-малко от m на брой различни елементи в тези множества.

Хроматично число на граф - дефиниция и намиране

Дефиниция: Хроматично число на граф е минималният брой цветове нужен, за да може да бъдат оцветени ребрата на графа, така че да няма две съседни ребра оцветени в един и същи цвят.

Втора Теорема на Konig: Ако G е двуделен мултиграф, то хроматичното му число е D, където $D = \underset{i \in V}{\max d_i}$, с di бележим степента на разклонение на върха i.
Доказателството е конструктивно и представлява алгоритъм за намиране на D. Ето и нагледен пример - двуделен граф $G = (X \bigcup Y, A)$, върху който прилагаме алгоритъма. Отляво - първоначалния вид на G, отдясно ще се разбере по-надолу какво точно е направено на G.
chromaticqa5.jpg
i) Конструираме G`, двуделен мултиграф, по следния начин:

  1. : в G` сме дублирали всеки връх от G по веднъж. Нека X` и Y`са дубликатите съответно на X и Y. Тогава дефинираме двете непресичащи се множества от върхове в G` по следния начин: $\overset{-}{X} = X \bigcup Y`, \overset{-}{Y} = Y \bigcup X`$, като всички ребра между X` и Y`са запазени, т.е. ако в A има ребро от i до j, където $i \in X, j \in Y$, то в А` има ребро от i` до j`, където $i` \in X`, j` \in Y`$.
  2. в G`, всички върхове са със степени равни на DG. За да постигнем това, на всеки връх i от X, чиято степен di е по-малка от DG, ще поставим DG - di на брой ребра до i` от X` , аналогично за върховете от Y.

G` в крайния си вид е показан на картинката в дясно. Зелените ребра са ребрата споменати в 2.
ii) Намираме Max-Matching = М в G`.
iii) Махаме ребрата от G, които участват в М.
Ако в G няма повече ребра, спираме.
Иначе прилагаме теоремата отново.
Всяка итерация от алгоритъма, съответства на един уникален цвят, в който сме оцветили някаква част от ребрата в G. Ясно е, че точно след D на брой итерации, алгоритъмът ще приключи.

Наредени и независими множества (вериги и антивериги)

Дефиниция: Множество от краен брой точки с бинарна операция е частично наредено, ако тя е антирефлексивна, антисиметрична и транзитивна. Наредените множества наричаме също вериги.

Дефиниция: Независимо множество (антиверига) наричаме подмножество от върховете на граф, в което никои два върха не са в релация.

Задача: Да се намери разбиване на графа $G = (X\bigcup Y, A)$ на минимален брой наредени множества.

Преди да видим как се намира минимално разбиване на наредени множества, първо да поясним един алгоритъм, как от произволен граф G да получим Gдв - двуделен граф построен по G. Нека G = (V, A), тогава Gдв = $(V\bigcup V`, A`)$, където дъгите от А` се дефинират така: ako $\exists (i,j) \in A \Rightarrow \exists (i, j`) \in A`$. Ето и конкретен пример:
nezavisimimnvsc7.jpggdvdk6.jpg
Твърдение - Лема 1: На всеки matching с n - k (n е броя на върховете в G) ребра в Gдв, съответства разбиване на k наредени множества в G.

Лема 2: Нека T- произволно минимално покритие в Gдв, то в G съществува независимо множество D: |D| = n - |T|.

Теорема на Dilworth: За произволен граф G, минималното разбиване на наредени подмножества = максималното независимо множество.

Бистохастични и пермутационни матрици

Дефиниция: Квадратна матрица, елементите на която са от интервала [0,1] и такава, че сумата на елементите от всеки ред и стълб е равна на 1 се нарича Бистохастична матрица.

Дефиниция: Бистохастична матрица с елементи {0,1} се нарича пермутационна (просто умножете вектор по нея и ще видите, че резултата е вектор, пермутация на първия).

Теорема: Произволна бистохастична матрица А може да се представи като изпъкнала комбинация на краен брой пермутационни матрици.
Т.е. $A = \overset{k}{ \underset{i = 1} {\sum} }\lambda_i P_i \mbox{ , } 0 \le \lambda_i \le 1 \mbox{ , } \sum \lambda_i = 1$

Да разгледаме твърдението с пример:

0.15 0.37 0 0.48
0.02 0.15 0.67 0.16
0.46 0.02 0.16 0.36
0.37 0.46 0.17 0

Както вече се досещате, строим двуделен граф $G = (X \bigcup Y, A, s, t, c)$, по таблицата - X - редове, Y - стълбове. Всяка дъга (i,j) от А e с капацитет стойността на клетката в ред i, стълб j. Ето как би изглеждал графа за горната таблица (не са сложени всички капацитети, че ще стане мазало).
stohastikack3.jpg
Процесът по намирането на $\lambda_i$ и Pi, е прост - намираме Max-Flow $\phi$ за G, в резултат ненулевите компоненти на $\phi$ са именно местата където в Pi има единица. $\lambda_i$ е равна на стойността на най-малкия ненулев компонент на $\phi$. След като сме намерили $\lambda_i$ и Pi, смятаме нашата нова матрица $A_{i + 1} = A_i - \lambda_i P_i$. Ако Аi + 1 e нулевата матрица край. Иначе прилагаме същите действия и за нея.
След краен брой пъти прилагане на горният алгоритъм ще стигнем до нулевата матрица.

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