Транспортные сети

Нахождение потока в транспортной сети

ЦЕЛЬ РАБОТЫ

10.1.1 Ознакомиться с теоретическими сведениями.

10.1.2 Получить практические навыки нахождения потока в транспортной сети.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

10.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

10.3.1 Изучить методические указания к практической работе.

10.3.2 В соответствии с полученным вариантом найдите максимальный поток в транспортной сети.

СОДЕРЖАНИЕ ОТЧЕТА

10.4.1 Цель работы

10.4.2 Методические рекомендации

10.4.3 Порядок выполнения работы

10.4.4 Ответы на контрольные вопросы

10.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

10.5.1 Что такое транспортная сеть?

10.5.2 Что такое источник?

10.5.3 Что такое сток?

10.5.4 Что значит пропускная способность дуги?

10.5.5 Какие вершины в транспортной сети называются промежуточными?

10.5.6 Что такое допустимый поток в сети?

10.5.7 Какая дуга называется насыщенной?

10.5.8 Какое поток называется максимальным?

10.5.9 Алгоритм построения полного потока в транспортной сети?

ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Транспортные сети

Определение. Транспортной сетью называется орграф D = (V, X) с множеством вершин V, для которого выполняются условия:

1) существует одна и только одна вершина v₁, называемая источником, такая, что D^-1(v₁) = 0 (т.е. ни одна дуга не заходит в v₁);

2) существует одна и только одна вершина v_n, называемая стоком, такая, что D(v_n) = 0 (т.е. из v_n не исходит ни одной дуги);

3) каждой дуге x (X) поставлено в соответствие целое число c(x) 0, называемое пропускной способностью дуги.

Определение. Вершины в транспортной сети, отличные от источника и стока, называются промежуточными.

В транспортной сети существует один исток и один сток. Случаи, когда имеется несколько источников или несколько стоков, могут быть сведены к рассматриваемому нами случаю введением обобщенных (фиктивных) источника и стока.