Гамма-алгоритм (в общем виде) 6 страница
Рисунок 23.11
Пункт 1.Пронумеровать произвольным образом вершины сети:
Рисунок 23.12
Пункт 2.Задать произвольный начальный поток в сети (например нулевой):
Рисунок 23.13
Пункт 3.1. Истоку (вершине №1) присвоить метку «0»
Рисунок 23.14
Пункт 3.2. Прямое помечивание: Пусть 
– непомеченная, а 
– помеченная вершины. Тогда вершине 
, такой что 
присвоить метку, равную номеру вершины , а дуге 
– знак «+».
Рисунок 23.15
Обратное помечивание вершине , такой что 
, присвоить метку равную номеру вершины , а другие – знак «-». Таких вершин на этом шаге не найдено:
Рисунок 23.16
Пункт 4.Вершина №6 (сток) получила метку. Значит, максимальный поток еще не найден. Продолжаем решение.
Рисунок 23.17
Пункт 5.Рассмотрим последовательность вершин 
, каждая из которых имеет метку, ревную номеру следующей вершины и последовательность дуг 
, соединяющих соседние вершины из 
.
Рисунок 23.18
Зададим новый поток по правилу:
Если 
;
Если ( 
имеет знак «+») 
;
Если ( имеет знак «-») 
;
, , имеет знак «+»
, , имеет знак «-»
В нашем случае 
, новый поток показан на рисунке.
Переход к пункту 3.1:
Пункт 3.1 (вторая итерация).Вершине №1 (истоку) присваиваем метку «0»:
Рисунок 23.19
Пункт 3.2 (вторая итерация).Прямое помечивание:
Рисунок 23.20
Обратное помечивание: соответствующих вершин не найдено.
Рисунок 23.21
Пункт 4 (вторая итерация).Вершина №6 (сток) получила метку. Значит, максимальный поток еще не найден. Продолжаем решение:
Рисунок 23.22
Пункт 5 (вторая итерация). 
; 
. Задаем новый поток:
Рисунок 23.23
Пункт 3.1 (третья итерация).Истоку (вершине №1) присвоить метку «0».
Рисунок 23.24
Пункт 3.2 (третья итерация).Прямое и обратное помечивание:
Рисунок 23.25
Пункт 4 (третья итерация).Вершина №6 получила метку. Значит, максимальный поток еще не найден. Продолжаем решение.
Рисунок 23.26
Пункт 5 (третья итерация). 
; 
; Задаем новый поток:
Рисунок 23.27
Пункт 3.1 (четвертая итерация).Исток (вершина №1) получает метку «0».
Рисунок 23.28
Пункт 3.2 (четвертая итерация).Прямое помечивание:
Рисунок 23.29
Обратное помечивание: соответствующих вершин не найдено.
Рисунок 23.30
Пункт 4 (четвертая итерация).Вершин №6 (сток) не получила метку. Значит, задача решена. Максимальный поток найден 
.
Рисунок 23.40
23.5 Контрольные вопросы и задания
1. Что такое транспортная сеть.
2. Поясните понятие пропускной способности дуг.
3. Приведите и поясните особенности использования алгоритма Дейкстры поиска кратчайших путей.
4. Приведите и поясните особенности использования алгоритма Форда-Фалкерсона.
УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
Основная литература
1. Бондаренко, М. Ф. Комп’ютерна дискретна математика [Текст] : підручник / М. Ф. Бондаренко, Н. В. Білоус, А. Г. Руткас. – Харків: «Компанія СМІТ», 2004. – 480 с. (існує електронний варіант).
2. Капітонова, Ю. В. Основи дискретної математики [Текст] / Ю. В. Капітонова, С. Л. Кривий, О. А. Летичевський, Г. М. Луцький, М. К. Печорін – Київ: Наукова думка, 2002. – 578 с.
3. Тевяшев, А. Д. Основы дискретной математики в примерах и задачах [Текст] : учеб. пособие для вузов / А. Д. Тевяшев, И. Г. Гусарова. – Харьков: ХНУРЭ, 2003. – 272 с.
4. Бардачев, Ю. Н. Основы дискретной математики [Текст] : учебное пособие / Ю. Н. Бардачев, Н. А. Соколова, В. Е. Ходаков; под редакцией В. Е. Ходакова. – Херсон: ХГТУ, 2000. – 356 с. (існує електронний варіант).
5. Шапорев, С. Д. Дискретная математика. Курс лекций и практических занятий [Текст] / С. Д. Шапорев – СПб.: БХВ-Петербург, 2006. – 400 с. (існує електронний варіант).
6. Кузнецов, О. П. Дискретная математика для инженера [Текст] / О. П. Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат, 1988. – 480 с.
7. Сигорский, В. П. Математический аппарат инженера [Текст] / В. П. Сигорский. – Киев: Техніка, 1977. – 768 с. (існує електронний варіант).
8. Яблонский, С. В. Введение в дискретную математику [Текст] / С. В. Яблонский. – М.: Наука, 1986. – 384 с.
9. Горбатов, В.А. Основы дискретной математики [Текст] / В. А. Горбатов – М.: Высшая школа, 1986. – 312с.
10. Харари, Ф. Теория графов [Текст] / Ф. Харари. – М.: Мир, 1973. – 304 с.
11. Глускин, Л.М. Задачи и алгоритмы комбинаторики и теории графов [Текст] / Л. М. Глускин, В. Я. Шварц, Л. А. Шор. – Донецк: Изд-во ДПИ, 1982. – 110с.
12. Білоус, Н.В. Основи комбінаторного аналізу. [Текст] : навч. посібник / Н. В. Білоус, З. В. Дудар, Н. С. Лєсна, І. Ю. Шубін. – Харків: ХТУРЕ, 1999. – 96 с.
13. Бондаренко, М. Ф. Збірник тестових завдань з дискретної математики [Текст] / М. Ф. Бондаренко, Н. В. Білоус, І. Ю. Шубін. – Харків: ХТУРЕ, 2000. – 156 с. (існує електронний варіант).
Дополнительная литература
14. Новиков, Ф. А. Дискретная математика для программистов [Текст] / Ф. А. Новиков. – СПб: Питер, 2001. – 304 с. (існує електронний варіант).
15. Донской, В.И. Дискретная математика [Текст] / В. И. Донской. – Симферополь: СОНАТ, 2000. – 360 с.
16. Андерсон, Дж. А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон. – М.: Издательский дом «Вильямс», 2003. – 960 с.
17. Виленкин, Н.Я. Комбинаторика [Текст] / Н. Я. Виленкин. – М.: Наука, 1969. – 328 с.
18. Белоус, Н.В. Тесты. Физика. Математическая логика [Текст] : Навч. посібник / Н. В. Белоус, Е. Е. Гетьманова, З. В. Дударь, В. Ф. Захарченко, М. А. Красноголовец, Н. С. Лесная, В. В. Семенец, В. А. Стороженко, А. А. Харьковская. – Харків: ХТУРЕ, 1998. – 152 с.
19. Капитонова, Ю. В. Лекции по дискретной математике [Текст] / Ю. В. Капитонова, С. Л. Кривой, А. А. Летичевский, Г. М. Луцкий. – СПб.: БХВ-Петербург, 2004. – 624 с.
Методические указания
20. Методичні вказівки до практичних робіт з дисципліни «Дискретна математика» (Частина 1) для студентів усіх форм навчання напряму 6.050101 – комп’ютерні науки / Упоряд. Н. В. Васильцова, Л.Е. Чала – Харків: ХНУРЕ, 2012. – 68 с.
21. Методичні вказівки до самостійної роботи з дисципліни «Дискретна математика» для студентів усіх форм навчання напряму 6.050101 – комп’ютерні науки / Упоряд. Н. В. Васильцова, Л.Е. Чала – Харків: ХНУРЕ, 2014. (навчальне електронне видання).
Глоссарий терминов дисциплины