Минимален срез

Задачата за минимален срез може да бъде формулирана, както за претеглени графи, така и за непретеглени. Понеже въпросът за непретеглени става еквивалентен, ако на всяко ребро сложим фиктивно тегло 1, то ще говорим само за претеглени графи. Стандартно се говори за неориентирани графи, затова и ние ще подходим така. Нека имаме неориентиран претеглен граф $G(V,E,f_w)$. Това, което трябва да намерим, е ребра с минимална сума от теглата, така че като ги махнем, да разделим графът на две несвързани части. Казано формално, срез е разбиване на върховете на графа на две непразни множества $S$ и $T$, като $S \cup T=V$ и $S \cap T= \emptyset$. Капацитет на един срез ще означаваме със $c(S,T)$ и е равен на $\sum_{x \in S} {\sum_{y \in T} f_w((x,y))}$ (теглата на ребра, които не са в графа, приемаме за 0). Тогава задачата за минималния срез е да намерим такъв срез $(S,T)$, така че капацитетът му да е минимален. Лесно се вижда, че всъщност капацитетът на срез е точно равен на сумата от теглата на ребра, чието премахване разделя двете части една от друга, защото ако оставим поне едно ребро между връх от $S$ и връх от $T$, то двете части ще са свързани една с друга.

Ние обаче ще разглеждаме един частен случай на тази задача - минимален срез с терминални върхове. Имаме два терминални върха $s$ и $t$ и търсим само срезове, за които $s \in S$ и $t \in T$. Казано с други думи разглеждаме само срезове, които разделят върховете $s$ и $t$. Обикновено наричаме $s$ източник, а $t$ - приемник. Тази задача се нарича минимален $s-t$ срез. Всъщност, оригиналната задача може да бъде решена чрез тази - достатъчно е да фиксираме един връх за източник и да разглеждаме всички възможности за приемника.

Сега ще поговорим и за срез в ориентирани графи (...макар това понятие да е най-смислено за неориентирани графи), защото алгоритъмът, който ще разглеждаме, работи за такива графи. Понятието за срез остава без промяна - пак разбиваме върховете на две непразни множества. Също и капацитета на срез дефинираме по същия начин. Така можем да забележим, че всъщност при ориентирани графи се интересуваме само от ребра, които излизат от връх на $S$ и влизат във връх на $T$ (...това дефакто е така и при неориентирани графи, но там ребрата са двупосочни, така че гледаме и в двете посоки). По този начин пак има някакво прекъсване на свързаност - след махане на ребрата от среза, от върховете в $S$ не можем да достигнем до върховете в $T$. Съответно понятието за минималния $s-t$ срез остава без промяна. Така търсим срезове, така че да не можем да стигнем от източника до приемника.

Вече сме готови с предварителната работа и продължаваме към алгоритъма, с който решаваме задачата за минимален $s-t$ срез и за ориентирани графи, и за неориентирани графи.

Нека разглеждаме ориентиран претеглен граф $G(V,E,c)$ (означили сме с $c$ тегловата функция). Освен това, нека сме фиксирали два върха $s$ и $t$ - съответно източник и приемник. Главната ни цел в тази точка ще е да докажем следният централен факт и да видим какви са последствията:

Теорема (за максималния поток и минималния срез): Максималният поток разгледан в графа $G$, като $f_w$ считаме за функцията, задаваща капацитета на ребрата, е равен на минималния $s-t$ срез в графа.

Тази теорема показва интересна дуалност между двете понятия. Ще докажем две неравенства, от които ще следва равенството. Първо ще докажем, че максималният поток е $\ge$ на минималния срез. За тази цел е достатъчно при намерен максимален поток, да намерим съответстващ срез. БОО можем да считаме, че графът $G$ е сведен до поточна мрежа, защото допълнителните ребра (обратните), които добавяме, имат капацитет 0, който не може да влияе на капацитета на среза. Разгледаме максимален поток в $G$ с големина $f_{max}$, като той се задава от функцията на потока $f$. Ще означим с $S$ множеството от върховете, които са достижими от източника (...това означава че има път от източника до тези върхове по ребра, които имат остатъчна пропускливост $c_f \gt 0$). Съответно останалите върхове ще означим с множеството $T$, т.е. $T=V \setminus S$. Ясно е, че $(S,T)$ е срез в графа. Както се очаква, ще покажем, че $c(S,T)=f_{max}$.

Нека си представим какво представлява максималния поток от гледна точка на среза. Потокът започва от множеството $S$ и отива в $T$. Така можем да си мислим за потока като сума на потоците на ребрата, насочени в посока от $S$ към $T$. Проблем е, че в общия случай може да имаме ребра в обратната посока от $T$ към $S$, които връщат някаква част от потока. Но да видим това възможно ли е за избрания срез. Нека вземем едно такова ребро $(u,v)$, така че $u \in T$ и $v \in S$, като $f(u,v) \gt 0$. Сега ако погледнем обратното ребро $(v,u)$, за него: $f(v,u)=-f(u,v)$ и $c(v,u)=0$. Но така остатъчната пропускливост $c_f(v,u)=c(v,u)-f(v,u)=f(u,v) \gt 0$. Като вземем предвид, че $v \in S$, това означава, че и $u$ ще е достижим и трябва да е там, но това не е вярно и получихме противоречие. Затова можем да направим извода, че за нашия срез няма ребра с положителен поток от $T$ към $S$. Това се получава, заради избора на срез и това, че включваме и обратните ребра в достижимостта.

Сега ще видим още едно свойство, което е важно и от практична гледна точка - всички ребра в посока от $S$ към $T$ са наситени. Нека разгледаме едно такова ребро $(u,v)$. Съответно имаме, че $u \in S$ и $v \in T$, като $f(u,v) \gt 0$. Но освен това $c_f(u,v)=0$, защото ако допуснем противното, че реброто не е наситено, то връх $v$ трябваше да е от $S$ - достижим от източника. Това в частност означава, че ако разглеждаме обратно ребро в посока от $S$ към $T$, то потокът през него трябва да е нула. Вече сме готови да заключим равенство. От една страна, големината на поток, дефиниран чрез срез, е сумата от положителните потоци на ребрата в посока от $S$ към $T$ минус сумата от положителните потоци на ребрата в обратната посока. Но понеже за нашия срез всички ребра, които прекосяват среза, са с неотрицателен поток, то можем спокойно да напишем, че $f_{max}=\sum_{x \in S} {\sum_{y \in T} f(x,y)}-\sum_{y \in T} {\sum_{x \in S} f(y,x)}$. Вече показахме, че за ребрата в обратната посока на среза няма поток, затова получаваме, че $f_{max}=\sum_{x \in S} {\sum_{y \in T} f(x,y)}$. Освен това имаме, че и те са наситени, така че окончателно: $f_{max}=\sum_{x \in S} {\sum_{y \in T} f(x,y)}$ $=\sum_{x \in S} {\sum_{y \in T} c(x,y)}=c(S,T)$.

Така понеже от произволен максимален поток, получихме съответстващ срез, то той е кандидат за минимален срез и директно максималният поток е $\ge$ на минималния срез. Сега ще покажем обратното, но то се получава лесно от направените вече разсъждения. Нека разглеждаме произволен срез на графа $S,T$ и произволен поток $flow$ на графа. Отново имаме, че потокът на графа е равен на сумата от положителните потоци на ребрата в посоката на среза минус сумата от положителните потоци на ребрата в обратната посока на среза. Тук трябва задължително да вземаме положителните потоци, защото може да имаме обратни ребра (в смисъл на поточната мрежа), които имат отрицателен поток през тях, който не трябва да броим. Казано по друг начин, за смятането на потока разглеждаме само реалните ребра (можем да считаме, че включваме неотрицателните потоци вместо положителните, без да променяме стойността). За удобство, нека означим поточната функция на реалните ребра с $f'$, като всъщност тя е същата като поточната функция $f$ с изключение на това, че за обратните ребра има стойност 0. Тогава имаме: $flow=\sum_{x \in S} {\sum_{y \in T} f'(x,y)}-\sum_{y \in T} {\sum_{x \in S} f'(y,x)}$. Понеже вадим само неотрицателни числа, то $flow \le \sum_{x \in S} {\sum_{y \in T} f'(x,y)}$ $ \le \sum_{x \in S} {\sum_{y \in T} c(x,y)}$. Но $c(S,T)=\sum_{x \in S} {\sum_{y \in T} c(x,y)}$. Така получихме именно, че $flow \le c(S,T)$, тоест произволен поток е по-малък или равен на всеки срез. Но това ще означава, че максималният поток ще е $ \le $ минималния срез, откъдето получаваме равенството между двете и с това доказахме теоремата.

Следва интерактивен пример, където по ориентиран граф се намира максималният поток и минималният му срез, където ясно се вижда доказаната еквивалентност.

Нека разгледаме какво се случва при неориентиран граф. Можем да направим аналогични разсъждения, понеже поток ще минава само в едната посока на двойката ребра, които съответстват на едно неориентирано. Така неориентираните ребра, които прекосяват среза, пак трябва да имат поток насочен в посока от $S$ към $T$.

Важно е да разгледаме някаква примерна задача, защото на пръв поглед задачите, при които се прилага този алгоритъм, нямат много общо с него. Затова нека разгледаме следната задача единствено в частта за намиране на максималното разпределение, т.е. само втора подзадача. Ще означим множеството на играчите от отбора на "добрите" със $S$, а тези от отбора на "лошите" с $T$. Освен това нека означим с $add_S[i]$ и $add_T[i]$ стойността, с която допринася всеки играч $i$, ако е в отбор $S$ или в отбор $T$ съответно и също така, с $rem[i][j]$, стойността на приятелството между играчи $i$ и $j$. Трябва да максимизираме следното: $\sum_{i \in S} add_S[i]$ $+$ $\sum_{j \in T} add_T[j]$ $-$ $\sum_{i \in S} {\sum_{j \in T} rem[i][j]}$. Това не е много далече от сумата, която имахме при минималния срез. Трябва да направим малки промени, за да стигнем до подходящ израз, където да минимизираме и да имаме само сумиране. Нека да извадим предния израз от фиксираната сума $\sum\limits_{i=1}^{N} {add_S[i]+add_T[i]}$. Ясно е, че всъщност така обръщаме нещата и ако оригинално търсим максимум, то сега ще търсим минимум и освен това няма да имаме изваждане. Получава се следната сума - $\sum_{i \in S} add_T[i]$ $+$ $\sum_{j \in T} add_S[j]$ $+$ $\sum_{i \in S} {\sum_{j \in T} rem[i][j]}$. Сега остава да проверим дали има подходящ граф, в който това да се явява срез.

Нека имаме два специални върха, единият за отбора на "добрите", а другият за отбора на "лошите". Също така ще направим по един връх за всеки играч. Най-логично е да свържем всеки играч с двата специални върха с ребра, чиято стойност е колко допринася съответния играч за съответния отбор. Освен това трябва да свържем играчите помежду си с ребра със стойностите на приятелствата. Нека разгледаме срез с терминални върхове - двата специални върха. Тогава е ясно, че разпадаме играчите на два отбора и освен това в среза участват точно ребрата, които съответстват на прекъснатите приятелства за играчи от различни отбори. Освен това ребра, които също се прекъсват (тоест са в среза) са и тези, които свързат играч с върха на срещуположния отбор. Така всеки срез има стойност, която е точно стойността на сумата, до която достигнахме и обратното за всяко разпределение на играчите в отбори съответства валиден срез. Ние търсихме минимума на сумата, така че точно ни трябва минималния срез в получения граф. Ако този срез е $m$, то за да получим крайният отговор трябва да върнем направеното изваждане или да сметнем $\sum\limits_{i=1}^{N} {add_S[i]+add_T[i]} - m$. Разпределението, което ни дава срезът също директно описва кой играч в кой отбор трябва да бъде, но това не се иска в задачата.

Накрая предоставяме интерактивен пример за задачата, където в текстовото поле се въвежда пример с до 6 играча във формата на входа без заявки.