Транспортная сеть

Материал из Википедии — свободной энциклопедии

В теории графов транспортная сеть $G = (V, E)$ -- ориентированный граф, в котором каждое ребро $(u,v) \in E$ имеет неотрицательную пропускную способность $c (u, v)$ > $0$ и поток $f (u, v)$ . Выделяются две вершины: источник $s$ и сток $t$ , такие, что любая другая вершина сети лежит на пути из $s$ в $t$ . Транспортная сеть может быть использована для моделирования, например, дорожного траффика.

[править] Определения

$\ G(V,E)$ ориентированный граф, в котором каждому ребру $\ (u,v) \in E$ приписана пропускная способность $\ c(u,v)$ . Если $\ (u, v) \not \in E$ , то $\ c(u, v) = 0$ . Выделяются две вершины: источник $s$ и сток $t$ , такие, что любая другая вершина сети лежит на пути из $s$ в $t$ . Поток -- $\ f:V \times V \rightarrow \mathbb{R}$ со следующими своиствами для вершин $\ u$ и $\ v$ :

Ограничение пропускной способности:	$\ f(u,v) \le c(u,v)$ . Поток не может привысить пропускную способность.
Антисимметричность:	$\ f(u,v) = - f(v,u)$ . Поток из $\ u$ в $\ v$ должен быть противоположным потоку из $\ v$ в $\ u$ .
Сохранение потока:	$\ \sum_{w \in V} f(u,w) = 0$ .

Остаточная пропускная способность ребра $\ c_f(u,v) = c(u,v) - f(u,v)$ . Остаточная сеть обозначается $\ G_f(V,E_f)$ . В остаточной сети может быть ребро из $\ u$ в $\ v$ , даже если его нет в исходной сети. Увеличивающий путь -- это путь $\ (u_1,u_2,\dots,u_k)$ в остаточной сети, где $\ u_1=s$ , $\ u_k=t$ , и $\ c_f(u_i, u_{i+1}) > 0$ . Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

[править] Пример

A flow network showing flow and capacity.

Здесь изображена транспортная сеть с источником $\ s$ , стоком $\ t$ и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно $\ f/c$ . Поток из источника к стоку равен 5, что легко видно, так как поток из $\ s$ равен 5, что есть также в $\ t$ .

Residual network for the above flow network, showing residual capacities.

Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых ребер, тогда как в исходной сети она равна нулю. Например, ребро $\ (d,c)$ . Этот поток не максимален. Есть увеличивающие пути $\ (s,a,c,t)$ , $\ (s,a,b,d,t)$ and $\ (s,a,b,d,c,t)$ . Остаточная пропускная способность первого пути $\ min(c(s,a)-f(s,a), c(a,c)-f(a,c), c(c,t)-f(c,t)) = \min(5-3, 3-2, 2-1) = \min(2, 1, 1) = 1$ . Увеличивающего пути $\ (s,a,b,d,c,t)$ не существует в исходной сети, но можно пропустить по нему правильный поток.

[править] Применение

Самый частый пример использования транспортных сетей -- нахождение максимального потока, который означает максимальный суммарный поток от $s$ к $t$ .

В задаче о потоке минимальной стоимости, каждому ребру $(u, v)$ сопоставляется цена $k (u, v)$ , цена пересылки потока $f (u, v)$ через ребро $f(u,v) \cdot k(u,v)$ . Задача -- послать заданное количество потока от $s$ к $t$ с наименьшей ценой.

[править] См также

Алгоритм Форда-Фалкерсона для решения задачи о максимальном потоке

[править] Литература

Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

[править] Ссылки(англ.)

Категория: Алгоритмы на графах

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Транспортная сеть

Материал из Википедии — свободной энциклопедии

Содержание

[править] Определения

[править] Пример

[править] Применение

[править] См также

[править] Литература

[править] Ссылки(англ.)

Views

Навигация

Участие

Поиск

На других языках