В этой лекции будем рассматривать ориентированные графы без петель
и кратных ребер. Для вершины $$x$$ множество всех входящих в нее
ребер обозначается через $$E^{+}(x)$$, а множество выходящих -
через $$E^{-}(x)$$.
Вершины сети, отличные от источника и стока, будем
называть
Пусть задана сеть $$N$$ с множеством вершин $$V$$
и множеством
ребер $$E$$. Функция $$f$$ с вещественными
значениями, определенная на $$E$$, называется
На рис. 16.1 показан пример сети и потока в ней. Число, вписанное в примыкающий к ребру квадрат, представляет пропускную способность, а другое число, написанное около ребра, - величину потока.
(рис 16.1) Условие (2), называемое условием сохранения потока, иногда удобно представлять в несколько иной форме. Пусть $$f$$ - любая числовая функция, определенная на ребрах сети. Дивергенцией функции $$f$$ в вершине $$x$$ называется величина
$$\mathop{\rm div}\nolimits_{f} (x)=\sum_{e\in E^{-} (x)}f(e) -\sum _{e\in E^{+} (x)}f(e).$$Заметим, что для любой такой функции $$f$$ имеет место равенство
$$\suml_{x\in V}\mathop{\rm div}\nolimits_{f} (x) =0,$$так как каждое ребро является входящим для одной вершины и выходящим для другой, и, следовательно, каждое ребро $$e$$ в этой сумме представлено двумя слагаемыми: $$f(e)$$ и $$-f(e)$$.
Условие сохранения означает, что дивергенция потока в каждой внутренней вершине должна быть равна $$0$$. Поэтому из равенства (1) следует, что для потока $$f$$
$$\mathop{\rm div}\nolimits_{f} (s)+ \mathop{\rm div}\nolimits_{f}(t)=\suml_{e\in E^{-} (s)}f(e)-\suml_{e\in E^{+} (t)}f(e) =0.$$Величина
$$M(f)=\mathop{\rm div}\nolimits_{f} (s)=\suml_{e\in E^{-}(s)}f(e)$$называется
Введем некоторые вспомогательные понятия и установим два полезных
соотношения. Пусть $$X\subseteq V$$, $$\overline{X}=V-X$$.
Множество всех
ребер, у которых начальная вершина принадлежит $$X$$, а концевая
- $$\overline{X}$$,
обозначим через $$(X,\overline{X})$$. Пропускной способностью
множества $$(X,\overline{X})$$ называется сумма пропускных способностей
всех
его ребер, она обозначается через $$c(X)$$. Если $$f$$
- поток, то для
каждого множества $$X\subseteq V$$ можно определить
величину $$f(X)=\suml_{e\in (X,\bar{X})}f(e)$$.
Очевидно, для любого множества $$X$$ и любого потока $$f$$
выполняется неравенство $$f(X)\le c(X)$$.
Множество $$(X,\overline{X})$$ называется
Лемма 1. Для любого потока $$f$$ и любого разреза $$(X,\overline{X})$$ выполняется равенство $$M(f)=f(X)-f(\overline{X})$$.
Доказательство. Рассмотрим величину $$S=\suml_{x\in X}\mathop{\rm div}\nolimits_{f} (x)$$.
Так как дивергенция во
Отсюда следует, что $$S=\suml_{e\in (X,\overline{X})}f(e) - \suml_{e\in (\overline{X},X)}f(e) =f(X)-f(\overline{X})$$.
Лемма 2. Для любого потока $$f$$ и любого разреза $$(X,\overline{X})$$ имеет место неравенство $$M(f)\le c(X)$$.
Доказательство. Это следует из леммы 1 и неравенств $$f(X)\le c(X)$$, $$f(\overline{X})\ge 0$$.
При внимательном рассмотрении рисунка 16.1 можно обнаружить, что
представленный на нем поток не является максимальным, так как существует
ориентированный путь $$s,a,b,t$$, на каждом ребре которого поток
можно
увеличить на 1. Иногда поток можно увеличить и при отсутствии таких
"недогруженных" путей из источника в сток. Рассмотрим пример сети
и потока
на рис. 16.2 слева. Среди ребер,
выходящих
из источника, только на ребре $$(s,a)$$ можно было бы увеличить
поток на 1. Но тогда нарушится условие сохранения потока в вершине $$a$$, а дальше эту дополнительную единицу
потока передать нельзя, так как ребро $$(a,t)$$ полностью загружено.
Можно, однако, заметить, что в вершину $$a$$ входит еще
ребро $$(b,a)$$
с
(рис 16.2) В этом примере, как и в предыдущем, удалось найти
путь $$s,a,b,c,t$$
(выделен на рисунке), вдоль которого можно направить дополнительный поток.
Отличие в том, что этот путь не ориентированный - при движении вдоль него
от источника к стоку некоторые ребра проходятся в направлении ориентации
(прямые), другие против ориентации (обратные). При этом все прямые ребра
пути недогружены, то есть поток на каждом из них не достигает пропускной
способности, а на каждом из обратных ребер имеется положительный поток.
Благодаря этому можно увеличить поток на всех прямых ребрах пути
и уменьшить на всех обратных на одну и ту же величину. В результате условие
сохранения потока во
Приведенный пример иллюстрирует общий метод, на котором основаны многие
алгоритмы решения
Допустим, имеется сеть $$N$$ и в ней поток $$f$$. Пусть $$x_{1},e_{1},x_{2},e_{2} \ldots$$ $$e_{k-1},x_{k}$$ -
неориентированный
путь в сети. Ребро $$e_{i}$$ назовем f(ei)< c(ei), а для каждого
обратного $$f(e_{i} )>0$$. Таким образом, на каждом прямом ребре
подходящего пути поток можно увеличить, а на каждом обратном - уменьшить.
Лемма 3. Если относительно потока $$f$$ имеется увеличивающий путь, то этот поток не максимален.
Доказательство. Пусть $$P$$ - увеличивающий путь для потока $$f$$, $$A$$ - множество всех прямых, $$B$$ - множество всех обратных ребер этого пути. Положим,
$$\delta _{1} =\min_{e\in A} (c(e)-f(e)),\\ \delta _{2} =\min_{e\in B} f(e)$$.Тогда на каждом прямом ребре пути можно увеличить поток на величину $$\delta_{1}$$, а на каждом обратном - уменьшить на величину $$\delta_{2}$$. Возьмем $$\delta =\min \{\delta_{1},\delta_{2}\}$$
и определим на ребрах сети новую функцию $$f'$$:
$$f'(e)=\left\{\begin{aligned} f(e)+\delta, \text{если } e \text{ прямое}, \\ f(e)-\delta, \text{если } e \text{ обратное},\\ f(e), \text{если } e \text{ не принадлежит пути } P. \end{aligned}\right$$.Легко видеть, что условия (1) и (2) для функции $$f'$$ выполняются, так что эта функция является потоком. Вместе с тем, очевидно, $${M(f'){=}M(f){+}\delta}$$, причем $$\delta >0$$.
Теорема 1. Поток максимален тогда и только тогда,
когда относительно него нет увеличивающего пути. Максимальная
Доказательство. Если поток максимален, то из леммы 3 следует, что увеличивающего пути нет. Обратно, пусть $$f$$ - поток, относительно которого нет увеличивающего пути. Покажем, что этот поток максимален. Для этого рассмотрим множество $$X$$, состоящее из всех вершин сети, достижимых подходящими путями из вершины $$s$$, $$\overline{X}=V-X$$. Так как увеличивающих путей нет, то $$t\in \overline{X}$$, так что $$(X,\overline{X})$$ - разрез. Пусть $$e=(x,y)$$ - ребро этого разреза. Вершина $$x$$ достижима из $$s$$ подходящим путем, а вершина $$y$$ недостижима. Тогда $$f(e)=c(e)$$, так как иначе к подходящему пути, ведущему из $$s$$ в $$x$$, можно было бы добавить ребро $$e$$ и вершину $$y$$, и получился бы подходящий путь из $$s$$ в $$y$$. Итак, на каждом ребре разреза $$(X,\overline{X})$$ поток равен пропускной способности, следовательно, $$f(X)=c(X)$$. Аналогично, рассматривая ребра из множества $$(\overline{X},X)$$, убеждаемся, что поток на каждом таком ребре равен 0, в противном случае опять можно было бы продолжить некоторый подходящий путь до вершины из $$\overline{X}$$. Следовательно, $$f(\overline{X})=0$$. Применяя лемму 1, получаем
$$M(f)=f(X)-f(\bar{X})=c(X)$$.По лемме 2, величина любого потока не превосходит пропускной способности
любого разреза. Значит, $$f$$ -
Многие известные алгоритмы построения
f(e)< c(e), то ребро $$e$$
включается в сеть $$R$$ и ему
в этой сети присваивается пропускная
способность $$c'(e)=c(e)-f(e)$$ ;Легко видеть, что увеличивающие пути в исходной сети находятся во взаимно
однозначном соответствии с ориентированными путями из источника в сток в
В этой лекции будем рассматривать ориентированные графы без петель
и кратных ребер. Для вершины $$x$$ множество всех входящих в нее
ребер обозначается через $$E^{+}(x)$$, а множество выходящих -
через $$E^{-}(x)$$.
Вершины сети, отличные от источника и стока, будем
называть
Пусть задана сеть $$N$$ с множеством вершин $$V$$
и множеством
ребер $$E$$. Функция $$f$$ с вещественными
значениями, определенная на $$E$$, называется
На рис. 16.1 показан пример сети и потока в ней. Число, вписанное в примыкающий к ребру квадрат, представляет пропускную способность, а другое число, написанное около ребра, - величину потока.
(рис 16.1) Условие (2), называемое условием сохранения потока, иногда удобно представлять в несколько иной форме. Пусть $$f$$ - любая числовая функция, определенная на ребрах сети. Дивергенцией функции $$f$$ в вершине $$x$$ называется величина
$$\mathop{\rm div}\nolimits_{f} (x)=\sum_{e\in E^{-} (x)}f(e) -\sum _{e\in E^{+} (x)}f(e).$$Заметим, что для любой такой функции $$f$$ имеет место равенство
$$\suml_{x\in V}\mathop{\rm div}\nolimits_{f} (x) =0,$$так как каждое ребро является входящим для одной вершины и выходящим для другой, и, следовательно, каждое ребро $$e$$ в этой сумме представлено двумя слагаемыми: $$f(e)$$ и $$-f(e)$$.
Условие сохранения означает, что дивергенция потока в каждой внутренней вершине должна быть равна $$0$$. Поэтому из равенства (1) следует, что для потока $$f$$
$$\mathop{\rm div}\nolimits_{f} (s)+ \mathop{\rm div}\nolimits_{f}(t)=\suml_{e\in E^{-} (s)}f(e)-\suml_{e\in E^{+} (t)}f(e) =0.$$Величина
$$M(f)=\mathop{\rm div}\nolimits_{f} (s)=\suml_{e\in E^{-}(s)}f(e)$$называется
Введем некоторые вспомогательные понятия и установим два полезных
соотношения. Пусть $$X\subseteq V$$, $$\overline{X}=V-X$$.
Множество всех
ребер, у которых начальная вершина принадлежит $$X$$, а концевая
- $$\overline{X}$$,
обозначим через $$(X,\overline{X})$$. Пропускной способностью
множества $$(X,\overline{X})$$ называется сумма пропускных способностей
всех
его ребер, она обозначается через $$c(X)$$. Если $$f$$
- поток, то для
каждого множества $$X\subseteq V$$ можно определить
величину $$f(X)=\suml_{e\in (X,\bar{X})}f(e)$$.
Очевидно, для любого множества $$X$$ и любого потока $$f$$
выполняется неравенство $$f(X)\le c(X)$$.
Множество $$(X,\overline{X})$$ называется
Лемма 1. Для любого потока $$f$$ и любого разреза $$(X,\overline{X})$$ выполняется равенство $$M(f)=f(X)-f(\overline{X})$$.
Доказательство. Рассмотрим величину $$S=\suml_{x\in X}\mathop{\rm div}\nolimits_{f} (x)$$.
Так как дивергенция во
Отсюда следует, что $$S=\suml_{e\in (X,\overline{X})}f(e) - \suml_{e\in (\overline{X},X)}f(e) =f(X)-f(\overline{X})$$.
Лемма 2. Для любого потока $$f$$ и любого разреза $$(X,\overline{X})$$ имеет место неравенство $$M(f)\le c(X)$$.
Доказательство. Это следует из леммы 1 и неравенств $$f(X)\le c(X)$$, $$f(\overline{X})\ge 0$$.
При внимательном рассмотрении рисунка 16.1 можно обнаружить, что
представленный на нем поток не является максимальным, так как существует
ориентированный путь $$s,a,b,t$$, на каждом ребре которого поток
можно
увеличить на 1. Иногда поток можно увеличить и при отсутствии таких
"недогруженных" путей из источника в сток. Рассмотрим пример сети
и потока
на рис. 16.2 слева. Среди ребер,
выходящих
из источника, только на ребре $$(s,a)$$ можно было бы увеличить
поток на 1. Но тогда нарушится условие сохранения потока в вершине $$a$$, а дальше эту дополнительную единицу
потока передать нельзя, так как ребро $$(a,t)$$ полностью загружено.
Можно, однако, заметить, что в вершину $$a$$ входит еще
ребро $$(b,a)$$
с
(рис 16.2) В этом примере, как и в предыдущем, удалось найти
путь $$s,a,b,c,t$$
(выделен на рисунке), вдоль которого можно направить дополнительный поток.
Отличие в том, что этот путь не ориентированный - при движении вдоль него
от источника к стоку некоторые ребра проходятся в направлении ориентации
(прямые), другие против ориентации (обратные). При этом все прямые ребра
пути недогружены, то есть поток на каждом из них не достигает пропускной
способности, а на каждом из обратных ребер имеется положительный поток.
Благодаря этому можно увеличить поток на всех прямых ребрах пути
и уменьшить на всех обратных на одну и ту же величину. В результате условие
сохранения потока во
Приведенный пример иллюстрирует общий метод, на котором основаны многие
алгоритмы решения
Допустим, имеется сеть $$N$$ и в ней поток $$f$$. Пусть $$x_{1},e_{1},x_{2},e_{2} \ldots$$ $$e_{k-1},x_{k}$$ -
неориентированный
путь в сети. Ребро $$e_{i}$$ назовем f(ei)< c(ei), а для каждого
обратного $$f(e_{i} )>0$$. Таким образом, на каждом прямом ребре
подходящего пути поток можно увеличить, а на каждом обратном - уменьшить.
Лемма 3. Если относительно потока $$f$$ имеется увеличивающий путь, то этот поток не максимален.
Доказательство. Пусть $$P$$ - увеличивающий путь для потока $$f$$, $$A$$ - множество всех прямых, $$B$$ - множество всех обратных ребер этого пути. Положим,
$$\delta _{1} =\min_{e\in A} (c(e)-f(e)),\\ \delta _{2} =\min_{e\in B} f(e)$$.Тогда на каждом прямом ребре пути можно увеличить поток на величину $$\delta_{1}$$, а на каждом обратном - уменьшить на величину $$\delta_{2}$$. Возьмем $$\delta =\min \{\delta_{1},\delta_{2}\}$$
и определим на ребрах сети новую функцию $$f'$$:
$$f'(e)=\left\{\begin{aligned} f(e)+\delta, \text{если } e \text{ прямое}, \\ f(e)-\delta, \text{если } e \text{ обратное},\\ f(e), \text{если } e \text{ не принадлежит пути } P. \end{aligned}\right$$.Легко видеть, что условия (1) и (2) для функции $$f'$$ выполняются, так что эта функция является потоком. Вместе с тем, очевидно, $${M(f'){=}M(f){+}\delta}$$, причем $$\delta >0$$.
Теорема 1. Поток максимален тогда и только тогда,
когда относительно него нет увеличивающего пути. Максимальная
Доказательство. Если поток максимален, то из леммы 3 следует, что увеличивающего пути нет. Обратно, пусть $$f$$ - поток, относительно которого нет увеличивающего пути. Покажем, что этот поток максимален. Для этого рассмотрим множество $$X$$, состоящее из всех вершин сети, достижимых подходящими путями из вершины $$s$$, $$\overline{X}=V-X$$. Так как увеличивающих путей нет, то $$t\in \overline{X}$$, так что $$(X,\overline{X})$$ - разрез. Пусть $$e=(x,y)$$ - ребро этого разреза. Вершина $$x$$ достижима из $$s$$ подходящим путем, а вершина $$y$$ недостижима. Тогда $$f(e)=c(e)$$, так как иначе к подходящему пути, ведущему из $$s$$ в $$x$$, можно было бы добавить ребро $$e$$ и вершину $$y$$, и получился бы подходящий путь из $$s$$ в $$y$$. Итак, на каждом ребре разреза $$(X,\overline{X})$$ поток равен пропускной способности, следовательно, $$f(X)=c(X)$$. Аналогично, рассматривая ребра из множества $$(\overline{X},X)$$, убеждаемся, что поток на каждом таком ребре равен 0, в противном случае опять можно было бы продолжить некоторый подходящий путь до вершины из $$\overline{X}$$. Следовательно, $$f(\overline{X})=0$$. Применяя лемму 1, получаем
$$M(f)=f(X)-f(\bar{X})=c(X)$$.По лемме 2, величина любого потока не превосходит пропускной способности
любого разреза. Значит, $$f$$ -
Многие известные алгоритмы построения
f(e)< c(e), то ребро $$e$$
включается в сеть $$R$$ и ему
в этой сети присваивается пропускная
способность $$c'(e)=c(e)-f(e)$$ ;Легко видеть, что увеличивающие пути в исходной сети находятся во взаимно
однозначном соответствии с ориентированными путями из источника в сток в
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.