Лекции. Теория графов и комбинаторика (стр. 8 )

6.  Для каждой вершины изменить метки:

7.  Вернуться к пункту 2.

Пример.

Смотри типовой расчет № 2.

Лекция № 10.

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ.

Дан ориентированный граф . – начальная, – конечная вершины. – длина дуги. Требуется найти путь из в , который обладает минимальной суммой весов входящих в него рёбер среди всех таких путей из в .

Алгоритм поиска минимального пути.

– временная метка вершины V (верхняя оценка длины минимального пути из в );

– постоянная метка вершины V (точное значение длины минимального пути из в ).

Этап I – нахождение длины минимального пути из в , т. е.

V – текущая вершина.

1. 

2. 

3.  Построить множество вершин, в которые ведут дуги из V;

4.  Для каждой вершины обновить временную метку ;

5.  Найти вершину с минимальной временной меткой (если их несколько, то берём любую);

6.  ;

7.  Если , то и вернуться к пункту 3.

Этап II – построение пути.

Путь в виде списка L строим с конца.

1. 

2.  Построить множество вершин , из которых идут дуги в V;

3.  Найти вершину (если их несколько, то берём любую).

4. 

5.  Если , то вернуться к пункту 2, иначе ВЫХОД.

Пример.

1.
2.
3.
4.
5.
6.

1.

2.

3.

4.

5.

ПОТОКИ В ТРАНСПОРТНЫХ СЕТЯХ.

Определение 1.

Сеть – ориентированный граф, обладающий следующими свойствами:

1.  из S (источника) дуги только выходят, в t (сток) дуги только входят.

2.  – пропускная способность дуги (будем указывать в скобках).

3.  – внутренняя вершина.

Определение 2.

Поток сети – отображение , которое обладает следующими свойствами:

1. 

2. 

Определение 3.

– величина потока.

Пример.

– поток наибольшей величины.

Лекция № 11.

ПОТОКИ В СЕТЯХ.

Определение 1.

Сечением сети называется разбиение множества вершин на два подмножества

Определение 2.

Разрез, соответствующий сечению – множество дуг, соединяющих вершины из разных множеств и . Обозначение .

– множество дуг, направленных от к (множество прямых дуг).