Жизнедеятельность современного общества тесно связана с различными сетями – транспортными, коммуникационными и пр. Изучением свойств сетей и графов занимается специальный раздел дискретной математики [1].

Одной из наиболее известных задач теории графов является задача о максимальном потоке в сети, которая активно изучается и исследуется уже более 60 лет. Повышенный интерес к этой задаче связан с ее огромной практической значимостью – множество прикладных задач (расчет электрических сетей, моделирование процессов в физике и химии, транспортные задачи и многие другие) могут быть сведены к задаче о максимальном потоке в сети.

Целью настоящей работы является изучение методов и алгоритмов решения задач с помощью потоков в сетях. В работе рассмотрены понятия потока в сети и их свойства, рассмотрены примеры решения задач о максимальном потоке в сети алгоритмом пометок Форда-Фалкерсона.

Глава 1. Задачи о потоках в сетях

1.1. Основные понятия.

Определим некоторые основные понятия теории графов и сетей, используемые в работе.

Графом называют пару объектов , где  – множество вершин графа, а  – множество связей между вершинами (рисунок 1) [2]. Символически граф обозначают как .  Иными словами, любое конечное множество соединенных между собой точек можно рассматривать как граф [3].

Рис. 1. Граф  

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

Обозначим как  и  - множество дуг, входящих и исходящих из i‑ой вершины.

Если вершины  и  соединены ребром/дугой, они называются соседними или смежными. Дуги/ребра  и  также называются смежными, если они имеют хотя бы одну общую точку. Дуга, которая соединяет вершину саму с собой, называется петлей [4].

Если каждому i-му ребру или дуге графа поставлено в соответствие некоторое неотрицательное число , то такой граф называется взвешенным, а само число  – весом i-ого ребра (дуги).

Чередующуюся конечная последовательность вершин и дуг (ребер)  называют путем  (в ортграфе) или маршрутом (в неориентированном графе). При этом  называют начальной вершиной,  – конечной, а остальные вершины – внутренними. Число , означающее количество ребер/дуг в пути/маршруте, называют длиной пути/маршрута и обозначается как .

Путь называется замкнутым, если . В противном случае путь называется открытым. Если все дуги пути различны, то маршрут называется цепью. Граф без цикла называется ациклическим.

Замкнутый путь с длиной больше 0 называется циклом. Цикл называется простым, если кроме  и  в нем больше нет повторяющихся вершин.

Если для любых вершин графа  и  существует маршрут/путь, который их соединяет, такой граф называется связанным.

Степенью вершины графа называется число выходящих из нее дуг. Изолированной вершиной называется вершина, из которой не выходит ни одной дуги [5].

1. Авдеюк О. А. Конспект лекций по дискретной математике: учебное пособие. – Волгоград: ВолгГТУ, 2015. – 144 с.
2. Ананичев Д. С., Андреева И. Ю., Гредасова Н. В., Костоусов К. В. Элементы дискретной математики: учебное пособие – Екатеринбург: Издательство Уральского университета, 2015. – 108 с.
3. Глибичук А. А., Дайняк А. Б., Ильинский Д. Г., Купавский А. Б., Райгородский А. М., Скопенков А. Б., Чернов А. А. Элементы дискретной математики в задачах. – М.: МЦНМО, 2013. – 171 с.
4. Новиков Ф. А. Дискретная математика: Учебник для ВУЗов. 2-е издание. Стандарт третьего поколения. – СПб.: Питер, 2013. – 432 с.
5. Феофанова В. А., Воротников В. И. Дискретная математика: учебно-методическое пособие. – Нижний Тагил: НТИ (филиал) УрФУ, 2013. – 256 с.
6. Алексеева В. А. Теория графов и математическая логика. Практикум: учебное пособие. – Ульяновск: УлГТУ, 2014. – 127 с.
7. Зарипова Э. Р., Кокотчикова М. Г. Дискретная математика. Часть III. Теория графов: Учебное пособие. – М.: Издательство РУДН, 2013. – 178 с.
8. Ильев В. П. Комбинаторные задачи на графах: учебное пособие. – Омск: Издательство Омского государственного университета, 2013. – 80 с.
9. Альсина К. Мир математики в 40 томах. Том11. Карты метро и нейронные сети. Теория графов / Перевод с испанского. – М.: Де Агостини, 2014. – 144 с.
10. Bapat R. B. Graphs and Matrices& - L.: Springer, 2014. – 193 p.
11. Benjamin A., Chartrand G., Zhang P. The Fascinating World of Graph Theory. Princeton: Princeton University Press, 2015. – 344 p.
12. Симонов Б. В., Авдеюк О. А., Симонова И. Э., Тарасова И. А. Элементы теории  графов. Теория  и  практика: учебное пособие. – Волгоград: ВолгГТУ, 2014. –                   82 с.
13. Геут К. Л., Коновалова С. С., Титов С. С. Дискретная математика: учебное пособие. – Екатеринбург: УрГУПС, 2015. – 111 с.
14. Benjamin A., Chartrand G., Zhang P. The Fascinating World of Graph Theory. – Princeton: Princeton University Press, 2015. – 344 p.
15. Bapat R. B. Graphs and Matrices. – L.: Springer, 2014. – 193 p.