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

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

Черновик [показать страницу] (сравнить)

Данная версия статьи не досматривалась участниками с соответствующими правами. Вы можете прочитать последнюю досмотренную версию от 19 сентября 2008, однако она может значительно отличаться от текущей версии. Проверки требуют 12 правок.

Перейти к: навигация, поиск

В теории графов транспортная сеть $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$ . Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

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

Транспортная сеть с указанием потока и пропускной способности.

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

Остаточная сеть для показанного сверху потока, показывающая остаточные пропускные способности.

Ниже показана остаточная сеть для данного выше потока. Обратите внимание, что существует ограничивающая пропускная способность для некоторых ребер, тогда как в исходной сети она равна нулю. Например, ребро $\ (d,c)$ . Этот поток не максимален. Есть увеличивающие пути $\ (s,a,c,t)$ , $\ (s,a,b,d,t)$ и $\ (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

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

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

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

Содержание

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

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

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

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

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

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

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

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