На этом шаге рассмотрим постановку задачи о максимальном потоке.
Ориентированный взвешенный граф служит математической моделью широкого класса задач на нахождение потоков в сетях. Для примера рассмотрим граф с четырьмя вершинами, пронумерованными от 1 до 4 (рис. 1):
Рис.1. Ориентированный взвешенный граф
Веса C[i,j] дуг графа (рис. 2):
Рис.2. Таблица весов
Пусть веса дуг (от вершин 1 к вершинам 3 и 4 и от вершины 2 к вершине 3) равны 10. Реальная постановка задачи, сводящейся к такому графу, может быть, например, такой: имеются две буровые вышки, добывающие нефть (вершины 1 и 2 на рис. 1), и два нефтеперерабатывающих завода (вершины 3 и 4 на рис. 1), которые эту нефть потребляют. Между вышками и заводами проложена сеть труб. В нашем примере от первой вышки (вершина 1) проведены трубы к обоим заводам (вершины 3 и 4), а от второй вышки (вершина 2) — только к первому заводу (вершина 3). Заданы также пропускные способности каждой трубы — по 10 т/ч. Требуется узнать, какое максимальное количество нефти в час может поставляться на переработку.
Ответ для приведенных исходных данных: 20 тонн. Нужно, чтобы из вершины 1 поставлялось 10 т/ч в вершину 4 (по дуге 1-4), а из вершины 2 поставлялось 10 т/ч в вершину 3 (по дуге 1-3).
В общем случае пропускные способности разных дуг, безусловно, могут различаться. Более того, вместо потоков жидкого вещества (нефти) можно рассматривать движение тока по проводам и многое другое.
Классической задачей, сводящейся к задаче о потоках в сетях, является также задача о максимальном паросочетании в двудольном графе. Пусть имеется граф (рис. 1). Веса C[i,j] дуг графа (рис. 3):
Рис.3. Таблица весов графа в задаче о максимальном паросочетании
Пусть вершины 1 и 2 соответствуют женихам, вершины 3 и 4 — невестам, a c[i,j] = 1 в том случае, если i и j готовы стать супругами. Требуется узнать максимально возможное количество супружеских пар. Правильный ответ в данных условиях — 2. Сочетаться браком могут жених 1 с невестой 4 и жених 2 с невестой 3.
Для корректности применения метода нахождения максимального потока в сетях необходимо, чтобы в физической постановке задачи соблюдались условия, которые рассморим на следующем шаге.
На следующем шаге рассмотрим условия, которые нужно соблюдать при решении задачи о максимальном потоке.
