4.1: Flows and Transportation Networks Part 1

Потоци в графи

Дефиниции и свойства

Темата за потоци в графи е първата по-сериозна тема, на която ще се спрем в предмета и една от най-сложните в теория на графите като цяло, затова изисква особено внимание. Първо да кажем, какво е поток в граф:

**Дефиниция (Закон на Кирхоф): ** Нека е даден граф G = (V, A), с дъги u = 1, 2… M и вход и изход на връх i $\omega^+(i) = \{u \in V \| a_{iu} = 1\}$ , $\omega^-(i) = \{u \in V \| a_{iu} = -1\}$, където АM = $\|a_{iu}\|, i = 1...N; u = 1...M,$ - матрица на инцидентност на G. Нека е даден векторът $\phi , \phi = (\phi_1, \phi_2, ... \phi_M ) \in \mathbb R ^M$ от някакви стойности, съответно за всяко ребро от графа. Векторът е поток, само ако е изпълнено: $\underset{u \in \omega^+(i)}{\sum} \phi_u = \underset{u \in \omega^-(i)}{\sum} \phi_u$, за всяко i от V. Или другояче казано, за всеки връх i от G е в сила правилото - колкото единици поток влизат в i по всевъзможните дъги (k, i), за k от V, то точно толкова и излизат по всевъзможните дъги (i, j) за j от V. Това правило е известно като първи закон на Kirchhoff.

Алгебрична форма на закона на Кирхоф Нека АM = $\|a_{iu}\|, i = 1...N; u = 1...M,$ е матрица на инцидентност на граф G = (V, A). Тогава от горната дефиниция-закон следва, че за произволен поток $\phi$ е в сила $A\phi = 0$.

Забележка: Законите на Кирхов всъщност първоначално не са били формулирани за графи. Те са закони за електрически схеми и се отнасят до запазване на електричен поток. Та, ето откъде идва нуждата за дефиниране на поток в граф и какво е едно примерно приложение.

Свойство: Ако $\phi$ е поток в дърво Т, то $\phi$ е нулев.
Доказателство:

Дефиниция Support на вектор (не съм сигурен в най-подходящия превод, затова ще карам на англо-български) $\phi = (\phi_1, ... , \phi_M)$ са всички ненулеви компоненти $\phi_u$ на $\phi$, ще го бележим с supp($\phi$). Вектор $\phi$ ще наричаме елементарен т.с.т.к. support-а му е минимален, т.е. не съществува $\phi`$, такъв че $supp(\phi`) \subset supp(\phi)$.

Твърдение: Елементарните потоци на граф G имат като support елементарните цикли на G.

Доказателство:

Теорема: В произволен граф G, всеки поток е линейна комбинация на елементарни, независими потоци по цикли, т.е. за: $\phi = (\phi_1, ... , \phi_M) \Rightarrow \phi = \Sigma \phi_i * \overset{\rightarrow}{\mu}_i$, където $\overset{\rightarrow}{\mu}_i$ е характеристичен вектор на цикъл в G.

Доказателство:

Следва една супер странна лема, наречена "Painting Lemma", с дооста широко приложение в потоци в графи, но първо малко думи за автора й. Автор на лемата е Минти, който , въпреки дебилното си име, е автор на велики идеи, като например алгоритъм за намиране на най-къс път в граф за константно време. Не, това не е шега, пичът се е сетил, че ако представиш граф с копчета и конци (съответно за върхове и ребра), като дължината на конците между дадени 2 копчета е пропорционална на дължината на реброто между тях, то най-късият път между дадени 2 копчета се намира просто като ги хванеш и ги опънеш във въздуха.

Лема (Painting Lemma):

Нека G = (V, A) е произволен граф, в който сме оцветили ребрата по следния начин: черно(B), червено(R), зелено(G) или даденото ребро е неоцветено(N), като поне едно ребро е с черен цвят. Избираме ребро u0, такова, че u0 е черно на цвят. За u0 има 2 възможности:
а) съществува елементарен цикъл, в който u0 участва, в който
- черните дъги са с посоката на u0;
- зелените дъги са с посока обратна на посоката на u0;
- червените дъги са с произволна посока;
- неоцветени дъги няма.
б) съществува елементарен коцикъл, към който u0 принадлежи, за който:
- черните дъги са с посоката на u0;
- зелените дъги са с посока обратна на посоката на u0;
- червени дъги няма.
- неоцветените дъги са с произволна посока;

Доказателство:

Следствие: В произволен граф G, за произволна дъга u, има 2 варианта : или е част от ориентиран цикъл, или е част от ориентиран коцикъл.
Доказателство:

Теорема: В граф G = (V, A), $\phi \ge 0$ т.с.т.к. $\phi = \Sigma \lambda_i * \overset{\rightarrow}{\mu}_i, \lambda_i > 0$. Т.е. $\phi$ е поток в G с ненулеви компоненти т.с.т.к. $\phi$ може да се представи като линейна комбинация с положителни коефициенти на елементарни цикли.
Доказателство:

Задачи : Max Flow в мрежа

Когато отсега нататък става дума за Max Flow в мрежа, ще разглеждаме по-особени графи от вида: G = (V, A, s, t, c), където s е връх източник, t е връх консуматор, а c е вектор с М компонента, където М е броя на дъгите в G, където ci е максималния капацитет на i-та дъга.

bipartiteyf4.jpg
$0 \le \phi_u \le c_u \forall u | \mbox{ u = 1... M }$, целта ни е да открием $\phi_0 \rightarrow \max$.
Това е главната, изходна задача за максимален поток в мрежа. Има множество проблеми, сведими до тази задача, като например:

bipartite non-capacitated Match problem:

Имаме множество от машини А и множество задачи Б, като всяка машина може да изпълнява определено подмножество от задачите. Търси се максималния брой задачи, които може да бъдат извършвани с дадените машини. Задачата се решава, като представите А и Б като двете множества от върхове на двуделен граф, слагате 2 нови върха s и t - източник и консуматор, сложите капацитет на дъгите от s към А с големина 1, и капацитет на дъгите между Б и t 1-ца. След това сложите всички възможни дъги от А към Б, и то с безкраен капацитет. Големината на потока по дъгата от t към s е решението на задачата.

matchch5.jpg

Min-cut problem

Даден е граф G = (V, A) и 2 върха от V, нека са p и q, да се намери минималната обща цена на дъги, които трябва да се премахнат от А, за да няма път от p до q.
Тук трябва да споменем какво е cut. Cut е разрез, ако имаме 2 множества от върхове, нека са Х и Х-, където Х- = V / X, то големината на разреза $\omega^+(X)$ между тях е сбора на теглата на дъгите, чието начало е в Х, а край в Х-. Аналогично за $\omega^-(X)$ - сбора на теглата на дъгите от Х- към Х.

А сега малко теореми:

Теорема: (за големината на потока $\phi_0$) $\phi_0 \le \underset{u \in \omega^+(X)}{\sum} c_u \mbox{, \forall X}$.

Доказателство:

Твърдение: Max-Flow е разрешим т.с.т.к. не съществува път от s към t с безкрайни капацитети на дъгите. Доказателството следва от метода, по който решаваме задачата за Max-Flow, който за момента все още не сме разглеждали. Затова само интуитивно ще докажа твърдението с това, че задача за търсене на максимум на дадена функция, която клони към безкрайност е задача без решение.

Теорема на Форд - Фулкерсон: Ето и може би най-важната теорема от темата: $\underset{(s,t)}{Max-Flow} = \underset{(s,t)}{Min-Cut}$

Доказателство:

Алгоритъм на Форд-Фулкерсон за решаване на Max-Flow problem

Първо малко дефиниции:

Дефиниция за Инкрементален Граф: Нека ни е даден граф G = (V, A) и допустим поток по него $\phi$. Оцветяваме (вече да не сте отишли на Теория на графите без пастели или цветни моливи!!!):

  1. дъги с нулеви потоци по тях в черно;
  2. дъги u, за които $0 < \phi_u < c_u$, в червено;
  3. останалите в зелено.

Построяваме G- по следния начин:

  1. черните дъги слагаме в u+;
  2. всяка червена дъга (i, j) в G разделяме на 2 дъги в G- по следния начин : дъга (i, j) слагаме в u+ с нов максимален капацитет $c`_u = c_u - \phi_u$ , дъга (j, i) в u- с капацитет $\phi_u$;
  3. всяка зелена дъга (i, j), влиза в u- като (j, i) с нов капацитет $\phi_u$;
  4. няма други xD.

Дефиниция - Остатъчен капацитет (residual capacity) : Нека е даден характеристичен вектор на верига $\overset{\rightarrow}{\mu}$, остатъчния капацитет на пътя, който съответства на вектора $\overset{\rightarrow}{\mu}$ ще бележим с $\epsilon$, където $\epsilon = \min(\underset{\overset{\rightarrow}{\mu}_u = -1 }{\min(\phi_u)}, \underset{\overset{\rightarrow}{\mu}_u = +1 }{min(c_u - \phi_u)}) \ge 0$.

Дефиниция: Инкрементален път в граф (augmenting path) е път от s до t в инкременталния граф G- с ненулев остатъчен капацитет.

Тясно място (infsection) Представете си графът като мрежа от тръби, потокът е течност пусната по дадена главна тръба на източника, съществува и тръба към консуматора. Интуитивно ясно е, че големината на потока течност от източника към консуматора за даден път от тръби, е капацитета на най-тясната тръба, това е и нашето $\epsilon$, e тази най-тясна тръба по пътя наричаме тясно място.

Алгоритъм за Max-Flow:

Инициализация :
k = 0;
$\phi = (0, 0...0)$;

Стъпка к:
$\phi(k)$ - текущ поток.
Търсим Пk - ориентиран път от s към t в $\overset{-}{G}_{\phi(k)}$;

  1. ако не съяествува Пk - край, $\phi(k)$ е максималния поток;
  2. иначе намираме остатъчния капацитет на Пk : $\epsilon^k$;
  3. намирираме:
(1)
\begin{align} \phi^{k + 1}_u = \begin{cases} \phi^k_u + \epsilon^k & \mbox{ if } u^+ \in \Pi^k\\ \phi^k_u - \epsilon^k & \mbox{ if } u^- \in \Pi^k\\ \end{cases}\\ \end{align}

k = k + 1;
continue;

Има много варианти на алгоритъма, в зависимост, по какъв начин търсим Пk. Ще се спра накратко върху варианта с BFS(припомнете си го от Тема 2, част 2). Всеки връх има текущ статус, като статусите са няколко (ако щете вярвайте, повече от 2!) :

  1. с етикет - върха е маркиран за по-нататъчно обхождане (в опашката е);
  2. прегледан е - бил е маркиран, изкарали сме го от опашката и сме маркирали всички негови непосредствени съседи, ребрата към които са с поток по тях под максималния им капацитет (все пак търсим инкрементален път);
  3. непрегледан - връх който не е минал през нито една от горните фази.

Видимо това е алгоритъмът, с който доказахме конструктивно лемата на Минти. За пресъздаване на инкременталния път се ползва BFS по списък на бащите. Защо BFS? Ами освен че е лесно и широко-употребяван метод за намиране на път в граф (и какво ли още не), съществува теорема, която гласи, че е по-оптимално да избираме винаги инкременталния път с най-малък брой върхове в себе си [Наков стр. 293].

Твърдение, че алгоритъмът работи: $\phi$ е максимален т.с.т.к. не съществува ориентиран път в $\overset{-}{G}_\phi$ от s към t.

Трудност: Търсим път в граф - това вече се знае - O(N2) трудност. Въпросът е колко пъти го търсим този път. За да си отговорим, трябва да си отговорим, колко пъти една дъга може да въде infsection - само веднъж в първоначалната си посока (след това я обръщаме, но тогава не е толкова интересна). Така получаваме крайната трудност от O(N2M) ~ O(N4). Съществуват и по-бързи алгоритми за намиране на Max-Flow като http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm например.

Сходимост: Колкото и да е странно, трябва да поясним и кога горният алгоритъм е сходим, т.е. при какви обстоятелства прекратява дейността си в гореспоменатите М стъпки. Както сигурно се досещате, сходимостта е пряко свързана с максималните капацитети на дъгите, по-точно с типът им. За цели числа всичко е ток и жица, проблем са числата с плаваща запетая. Отсега нататък, задачите които ще разглеждаме към уроците от потоци в мрежа, ще са само върху множеството от целите числа (освен ако изрично не е споменато обратното).

Примерен проблем : http://acm.timus.ru/problem.aspx?space=1&num=1421.

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