Основы теории транспортных систем. Горев А.Э. - 30 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

Составители: 

Рубрика: 

58 59
А. Э. Горев. Основы теории транспортных систем
стороннее движение и их пропускная способность в обоих направле-
ниях одинакова.
Вся сеть произвольно разбивается на два дерева. В одном должен
находиться источник А, а в другом – сток F. Разбиение сети на деревья
основывается на теореме Форда – Фалкерсона: на любой сети макси-
мальная величина потока из источника s в сток S равна минимальной
пропускной способности разреза, отделяющего s от S.
На рис. 2.12, б одно дерево состоит из четырех ребер: AB, AC, AD,
CE, а другое – из одной вершины F.
Для пропуска потока необходимо два дерева соединить одним из
возможных ребер, например EF, по которому можно пропустить насы-
щенный поток q
1
. Величина q
1
равна минимальной пропускной спо-
собности одного из ребер. На рис. 2.12, б таких ребер два: CE EF. Про-
пускаем поток, равный 1, по маршруту A–C–E–F. После этого одно из
ребер (выбираем EF) исключаем из сети.
Сеть опять разорвалась на два дерева. Соединим их ребром DF,
по которому можно пропустить насыщенный поток q
2
. Его размер, оп-
ределяемый минимальной пропускной способностью ребер маршрута
A–D–F, равен 2 (рис. 2.12, в). Пропускаем этот поток и исключаем из
сети ребро DF.
На рис. 2.12, г таким же образом пропускаем поток q
3
= 1 (часть
пропускной способности ребра AC использована в первом маршруте)
по ребрам A–C–F и исключаем из сети ребро AC.
На рис. 2.12, д сеть состоит из двух деревьев: с вершинами A, B, D
и с вершинами C, E, F. Эти два дерева соединяем ребром AE и опреде-
ляем дополнительный поток q
4
, который можно пропустить от источ-
ника к стоку. На ребре CE он пойдет навстречу уже существующему
потоку, поэтому его размер надо вычесть из ранее распределенного
на это ребро потока. Поток q
4
равен 1 (рис. 2.12, е). На ребре поток
становится равным 0. Теперь по этому же маршруту можно пропус-
тить поток q
5
. Его величина определяется пропускной способностью
ребра CE и равна 1.
На рис. 2.12, ж показан дополнительный поток q
6
, равный 2,
а на рис. 2.12, з максимальный поток по сети, равный 8.
Задача поиска кратчайшего пути является основой для задач
маршрутизации грузового и пассажирского транспорта. Поскольку ребрам
сети можно приписать значения расстояния, стоимости или времени
поездки, одинаково просто найти кратчайшие расстояния, наименьшую
стоимость или время поездки от одной вершины до всех остальных.
Существует множество методов решения задачи о кратчайшем пути. Один
из наиболее простых – метод потенциалов (метод Минти).
AB
C
D
E F
4
2
5
3
1
5
2
2
1
2 2
AB
C
D
E F
5
2
2
1
а
б
в
AB
C
D
E F
5
1
2
2
1
q
2
AB
C
D
E F
5
1
q
3
1+q
3
2
1
2
г
д
AB
C
D
E F
5
q
4
1
1+q
4
2
2
1
2
AB
C
D
E F
5
1+q
5
1
2+q
5
2
2
1
2
е
ж
AB
C
D
E F
q
6
5
2
1
3+q
6
2
2
1
2
AB
C
D
E F
2
2
2 1
5
2
2
1
2
з
q
1
Рис. 2.12. Последовательность решения задачи о максимальном потоке
Глава 2. Транспортные системы

Страницы