В.А. Носов - Комбинаторика и теория графов (1023552), страница 17
Текст из файла (страница 17)
Например, для сети на рис. 1 множество дуг (v1, ω), (v3, ω) является разрезом. Его пропускная способность равна 6, т.е. совпадает с величиной максимального потока. Дуга e, для которой ϕ(e) = ω(e), называется насыщенной. Поток, прикотором ϕ(e) = 0 для всех дуг e, называется нулевым.Заметим, что величина любого потока не превышает пропускной способностилюбого разреза и, значит, величина максимального потока не превосходит пропускнойспособности минимального разреза.
Оказывается, что эти два числа равны между собой.Соответствующий результат известен, как теорема Форда-Фалкерсона.106Теорема 1. Во всякой сети величина минимального разреза потока равна пропускной способности любого минимального разреза.♦ В силу замечания о том, что величина любого максимального потока не превышает пропускной способности любого минимального разреза, достаточно доказать,что существует разрез, пропускная способность которого равна величине данного максимального потока.
Действительно, путь ϕ - максимальный поток. Определим два множества вершин сети V и W следующим образом: пусть G - скелетный граф для графа Г.Тогда вершину z сети N включаем в множество V тогда и только тогда, когда в G существует простая цепь из v в z: v = v0, v1, … , vm-1, vm = z, обладающая тем свойством, чтолюбое ее ребро {vi, vi+1} соответствует либо не насыщенной дуге (vi, vi+1), либо дуге(vi+1, vi) , через которую проходит не нулевой поток. Очевидно, что множество V содержит вершину v. Пусть множество W есть дополнение множества V в множестве вершинсети N. Покажем, что множество W содержит вершину w. Если это не так, то w принадлежит множеству V.
Значит существует простая цепь v, v1, … , vm-1, w такая, что ребро{vi, vi+1} соответствует либо ненасыщенной дуге (vi, vi+1), либо дуге (vi+1, vi) с ненулевымпотоком. Определим положительное число ε, удовлетворяющее условиям:а) Для дуг первого типа число ε не превышает величину разности пропускнойспособности каждой дуги и соответствующего ей потока.б) Для дуг второго типа число ε не превышает величины потока через каждуюиз них.Теперь заметим, что если потоки через дуги первого типа увеличить на ε, а потоки черездуги второго типа уменьшить на ε, то величина потока ϕ увеличится и станет равнойϕ + ε. Однако это противоречит предположению о максимальности потока ϕ.
Значит wсодержится в множестве W.Обозначим теперь через R множество дуг вида (x, y), где x ∈ V, y ∈ W. Ясно,что R является разрезом. Далее, каждая дуга (x, y) из R является насыщенной, посколькув противном случае y должна принадлежать множеству V. Значит сумма потоков дуг поразрезу R равна его пропускной способности, а с другой стороны, равна величине потока. Значит R и есть искомый разрез. ♦Данная теорема еще не дает алгоритма построения максимального потока черезсеть.
Приведем такой алгоритм для целочисленного потока. Алгоритм построения максимального потока состоит из трех этапов.1071. Отыскание какого-нибудь потока. Строим произвольный поток ϕ, удовлетворяющий условиям сохранения потока в каждой внутренней вершине и условиям на пропускную способность дуг. За ϕ можно взять нулевой поток.2. Отыскание полного потока, т.е. такого потока, у которого любой ориентированный путь из v в w содержит насыщенную дугу. Если поток ϕ не полный, то существует путь из v в w, все дуги которого не насыщены.
Увеличивая поток по этому пути донасыщения одной из дуг получаем новый поток ϕ′, величина которого превосходит исходный поток.3. Отыскание максимального потока. Для этого применяем следующую процедуру.3.1. Помечаем вершину v символом o. Если вершина vi помечена, то помечаемсимволом + i все непомеченные вершины, в которое из vi идут не насыщенные дуги, исимволом - i все непомеченные вершины, из которых идут дуги в вершину vi с ненулевым потоком.3.2.
Если продолжая таким образом, вершина w оказалась помеченной, то этоозначает, что существует цепь из v в w, все вершины которой помечены. Увеличиваяпоток во всех дугах цепи на 1, у которых направление совпадает с прохождением пути, иуменьшая поток на 1 во всех дугах, направление которых обратно прохождению пути.Ясно, что поток в сети увеличивается на 1. Повторяем шаги 3.1. и 3.2. до тех пор, покавершину w удается пометить.Если при некотором потоке ϕ, вершину w не удается пометить, то поток ϕ будетмаксимальным. Действительно, если через V обозначить множество помеченных вершин, а через W - множество непомеченных, причемx ∈ V, w ∈ W, то множество дуг R вида (x, y), где x ∈ V, y ∈ W будет разрезом. Приэтом все такие дуги (x, y) будут насыщенными, в противном случае y была бы помечена.
Значит ϕ - максимальный поток. Рассмотрим одно приложение данных результатов.Паросочетанием в неориентированном графе G(V, E) называется произвольное множество ребер M ⊆ E, такое, что никакие два ребра из М не имеют общей вершины. Особыйинтерес представляет нахождение паросочетаний для двудольных графов, посколькуэтот вопрос возникает в задачах теории связи. Покажем, как задача нахождения наибольшего паросочетания в двудольном графе сводится к построению максимальногопотока в некоторой сети. Пусть H = (V1, V2, E) - произвольный двудольный граф.
Этоозначает, что V1 I V2 = ∅ и каждое ребро e ∈ E имеет вид (x, y), x ∈ V1, y ∈ V2.108Построим сеть S(H) следующим образом:1. Добавим вершины s (источник) и t (сток).2. Добавим дуги от s к каждой вершине x ∈ V1 и дуги от каждой вершины y ∈V2 к t.3. Ориентируем ребра e ∈ E , e=(x,y) от x к y.4. Припишем всем дугам пропускную способность 1.Согласно изложенному выше, для сети S(H) существует максимальный поток ϕ.Теорема 2. Существует взаимно однозначное соответствие между паросочетаниями в H и потоками в S(H), при котором паросочетанию М мощности k соответствуетпоток величины k, причем соответствие устанавливается так:Паросочетание M = {(x1, y1), … , (xk, yk)}мощности k⇒Поток ϕ(s, xi) = ϕ(xi, yi) = ϕ(yi, t) = 1величины kϕ(e) = 0(1)для остальных дугПоток ϕ величины k⇒Паросочетание M= {(x, y)},x∈ V1, y ∈ V2мощности k ϕ(x, y) = 1(2)♦ Пусть M = {(x1, y1), … , (xk, yk)} - паросочетание мощности k. Тогда вершиныx1, … , xk и вершины y1, … , yk попарно различны.
Отсюда следует, что функция ϕ, определенная (1), является потоком из s в t. Далее, разным паросочетаниям М соответствуютразные потоки ϕ. С другой стороны, если ϕ - поток в сети S(H), то количество потока,прибывающего (а значит, убывающего) в каждую вершину x ∈ V1 не превосходит единицы, т.к. единственная дуга, входящая в x - это дуга (s, x) с пропускной способностью,равной 1. Отсюда следует, что в множестве М, определенном (2) нет ребер вида (x, y1),(x, y2),y1 ≠ y2 . Аналогично в М нет ребер вида (x1, y), (x2, y), x1 ≠ x2 .
Следовательно, М - паросочетание в H. Легко заметить, что отображения, определенные (1) и (2), являются обратными друг к другу. ♦Таким образом, для построения максимального паросочетания можно использовать алгоритм построения максимального потока.109110Упражнения.1. Доказать, что если число ребер графа с вершинами (n > 2) больше, чем n − 1 , то он связен. 2 2. Доказать, что если степень каждой вершины G не меньше двух, то G содержит цикл.3. Выяснить, при каких m, n графы Кm,n (полный двудольный граф с m и n вершинами в долях), Кn (полный граф на n вершинах), Вn (граф единичного куба) являютсяэйлеровыми.4. Доказать, что графы Кn , Кn,n , Вn являются гамильтоновыми.5.
Индукцией по n доказать, что каждое дерево с n ≥ 2 вершинами является двудольным графом.6. Найти число остовных деревьев графа де Брейна с n = 3.7. Найти максимальный поток в графе6a13sb1722a2792b25a314t6b3111ЛИТЕРАТУРА[1]Холл. М. Комбинаторика.
М., Мир, 1970.[2]Райзер Г.Дж. Комбинаторная математика, М., Мир, 1966.[3]Рыбников К.А. Введение в комбинаторный анализ. М., МГУ, 1985.[4]Айгнер М. Комбинаторная теория. М., Мир, 1982.[5]Липский В. Комбинаторика для программистов, М., Мир, 1988.[6]Оре О. Теория графов. М., Наука, 1968.[7]Харари Ф. Теория графов. М., Мир, 1973.[8]Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях, М., Мир, 1963.[9]Уилсон Р.
Введение в теорию графов, М., 1977.[10]Кофман А. Введение в прикладную комбинаторику. М., 1975.[11]Комбинаторный анализ. Задачи и упражнения. Под ред. Рыбникова К.А.,М., 1982[12]Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики, М., Наука, 1992.112.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
