Введение
Вычислительная задача в теории графов
В теории оптимизации задачи о максимальном потоке включают в себя поиск допустимого потока в сети потоков, достигающего максимально возможной пропускной способности. Задача о максимальном потоке может рассматриваться как частный случай более сложных задач сетевого потока, таких как задача о циркуляции. Максимальное значение s-t потока (то есть потока от источника s к стоку t) равно минимальной пропускной способности s-t разреза (то есть разреза, разделяющего s и t) в сети, как утверждает теорема о максимальном потоке и минимальном разрезе.
История
Проблема максимального потока была впервые сформулирована в 1954 году Т. Э. Харрисом и Ф. С. Россом как упрощенная модель потока железнодорожного транспорта в Советском Союзе. В 1955 году Лестер Р. Форд-младший и Делберт Р. Фулкерсон разработали первый известный алгоритм – алгоритм Форда-Фулкерсона. В своей статье 1955 года, а также Келнер, Ли, Орекчиа и Сидфорд находят приближенно оптимальный максимальный поток, однако их работы применимы только к неориентированным графам. В 2013 году Джеймс Б. Орлин опубликовал статью, описывающую алгоритм. Для задачи поиска кратчайшего пути из одного источника (SSSP) с отрицательными весами, являющейся частным случаем задачи о потоке минимальной стоимости, также был предложен алгоритм, работающий за почти линейное время. Оба алгоритма были отмечены как лучшие работы на симпозиуме 2022 года по основам компьютерных наук.
Проблема максимального потока с несколькими источниками и несколькими раковинами
Имея сеть с набором источников и набором стоков вместо одного источника и одного стока, необходимо найти максимальный поток через сеть. Мы можем преобразовать задачу о множественных источниках и множественных стоках в задачу о максимальном потоке, добавив единый источник, соединяющийся с каждой вершиной в , и единый сток, соединенный с каждой вершиной в (также известные как суперисточник и суперосток) с бесконечной пропускной способностью на каждом ребре (см. рис. 4.1.1).
Максимальная кардинальность двустороннего совпадения
Для заданного двудольного графа необходимо найти максимальное по кардинальности паросочетание в этом графе, то есть паросочетание, содержащее наибольшее возможное количество ребер. Эту задачу можно свести к задаче о максимальном потоке, построив сеть , где содержатся ребра из , направленные от к для каждого и из к для каждого (см. рис. 4.3.1). Тогда величина максимального потока в равна размеру максимального паросочетания в , а максимальное по кардинальности паросочетание можно найти, выбрав те ребра, по которым протекает поток 1 в целочисленном максимальном потоке.
contains the edges in directed from to for each and for each for each (See Fig. 4.3.1). Then the value of the maximum flow in is equal to the size of the maximum matching in , and a maximum cardinality matching can be found by taking those edges that have flow in an integral max flow.
Минимальная площадь покрытия траектории в направленном ациклическом графике
Для заданного направленного ациклического графа , требуется найти минимальное количество непересекающихся по вершинам путей, покрывающих каждую вершину в . Можно построить двудольный граф из , где затем можно показать, что имеет паросочетание размера , если и только если имеет покрытие непересекающимися по вершинам путями, содержащее ребер и путей, где – число вершин в . Следовательно, задачу можно решить, найдя паросочетание максимальной мощности в . Предположим, мы нашли паросочетание и построили покрытие из него. Чтобы показать, что покрытие состоит из непересекающихся путей, рассмотрим следующее: каждая вершина в может быть либо не сопоставлена в , в этом случае из не выходит ни одного ребра; либо она может быть сопоставлена, в этом случае из выходит ровно одно ребро. В любом случае, из каждой вершины в не выходит более одного ребра. Аналогично для каждой вершины в – если она сопоставлена, в нее входит одно ребро; в противном случае в нее не входит ни одного ребра. Таким образом, ни одна вершина не имеет двух входящих или двух исходящих ребер в , что означает, что все пути в покрытии не пересекаются по вершинам. Чтобы показать, что покрытие имеет размер , начнем с пустого покрытия и будем строить его инкрементально. Чтобы добавить вершину в покрытие, мы можем либо добавить ее к существующему пути, либо создать новый путь длины ноль, начинающийся в этой вершине. Первый случай применим, когда либо и какой-то путь в покрытии начинается в , либо и какой-то путь заканчивается в . Второй случай всегда применим. В первом случае общее число ребер в покрытии увеличивается на 1, а число путей остается прежним; во втором случае число путей увеличивается на 1, а число ребер остается прежним. Теперь ясно, что после покрытия всех вершин сумма числа путей и ребер в покрытии равна . Следовательно, если число ребер в покрытии равно , то число путей равно .
Then it can be shown that has a matching of size if and only if has a vertex disjoint path cover containing edges and paths, where is the number of vertices in Therefore, the problem can be solved by finding the maximum cardinality matching in instead. Assume we have found a matching of , and constructed the cover from it. Intuitively, if two vertices are matched in , then the edge is contained in Clearly the number of edges in is To see that is vertex disjoint, consider the following:
Each vertex in can either be non matched in , in which case there are no edges leaving in ; or it can be matched, in which case there is exactly one edge leaving in In either case, no more than one edge leaves any vertex in Similarly for each vertex in – if it is matched, there is a single incoming edge into in ; otherwise has no incoming edges in Thus no vertex has two incoming or two outgoing edges in , which means all paths in are vertex disjoint. To show that the cover has size , we start with an empty cover and build it incrementally. To add a vertex to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either and some path in the cover starts at , or and some path ends at The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all vertices, the sum of the number of paths and edges in the cover is Therefore, if the number of edges in the cover is , the number of paths is .
Максимальный поток с вершинами
Пусть G – сеть. Предположим, что в каждой вершине, помимо пропускной способности ребер, есть собственная пропускная способность, то есть отображение c, такое что поток f должен удовлетворять не только ограничению на пропускную способность ребер и закону сохранения потока, но и ограничению на пропускную способность вершин.
Другими словами, количество потока, проходящего через вершину, не может превышать её пропускную способность. Чтобы найти максимальный поток в сети G, мы можем преобразовать задачу к стандартной задаче о максимальном потоке, расширив сеть следующим образом: сначала каждая вершина v заменяется двумя вершинами v_in и v_out, где v_in соединена ребрами, входящими в v, а v_out соединена ребрами, выходящими из v. Затем ребру, соединяющему v_in и v_out, присваивается пропускная способность c(v) (см. рис. 4.4.1). В этой расширенной сети ограничение на пропускную способность вершин устраняется, и, следовательно, задачу можно рассматривать как стандартную задачу о максимальном потоке.
Максимальное количество путей от s до t
Учитывая ориентированный граф и две вершины *s* и *t*, требуется найти максимальное количество путей из *s* в *t*. Эта задача имеет несколько вариантов:
1. Пути должны быть непересекающимися по ребрам. Эту задачу можно свести к задаче о максимальном потоке, построив сеть *G'* из *G*, где *s* и *t* являются источником и стоком соответственно, и присвоив каждому ребру пропускную способность 1. В этой сети максимальный поток равен *k* тогда и только тогда, когда существует *k* непересекающихся по ребрам путей.
2. Пути должны быть независимыми, то есть непересекающимися по вершинам (за исключением *s* и *t*). Можно построить сеть *G'* из *G* с пропускными способностями вершин, где пропускная способность всех вершин и всех ребер равна 1. Тогда значение максимального потока равно максимальному количеству независимых путей из *s* в *t*.
3. Помимо требования непересекаемости путей по ребрам и/или вершинам, на пути также может быть наложено ограничение на длину: учитываются только пути, длина которых равна точно *k*, или не превышает *k*. Большинство вариантов этой задачи являются NP-полными, за исключением малых значений *k*.
3. In addition to the paths being edge disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly , or at most Most variants of this problem are NP complete, except for small values of .
Проблема закрытия
Закрытие направленного графа — это множество вершин C, из которого не выходит ни одного ребра. Задача о закрытии — это задача нахождения замыкания с максимальным или минимальным весом в ориентированном графе с весами на вершинах. Её можно решить за полиномиальное время с помощью сведения к задаче о максимальном потоке.
Расписание авиакомпании
В авиационной отрасли основной проблемой является составление расписания для лётных экипажей. Задача планирования авиаперевозок может рассматриваться как применение расширенного максимального потока в сети. Входными данными для этой задачи является набор рейсов F, содержащий информацию о месте и времени отправления и прибытия каждого рейса. В одной из версий задачи составления расписания авиакомпании целью является создание выполнимого расписания, требующего не более чем k экипажей. Для решения этой задачи используется вариант задачи о циркуляции, называемый ограниченной циркуляцией, который является обобщением задач о сетевом потоке с дополнительным ограничением на нижнюю границу потока по рёбрам. Пусть G = (V, E) – сеть, где s, t ∈ V являются исходной и конечной вершинами соответственно. Для источника и пункта назначения каждого рейса i добавляются две вершины в V: si – как источник, и di – как пункт назначения рейса i. Также к E добавляются следующие рёбра:
Рёбро с пропускной способностью [0, 1] между s и каждым si. Рёбро с пропускной способностью [0, 1] между каждым di и t. Рёбро с пропускной способностью [1, 1] между каждой парой si и di. Рёбро с пропускной способностью [0, 1] между каждым di и sj, если источник sj достижим из пункта назначения рейса i за разумное время и с приемлемыми затратами. Рёбро с пропускной способностью [0, ∞] между s и t.
An edge with capacity [0, 1] between s and each si. An edge with capacity [0, 1] between each di and t.
An edge with capacity [1, 1] between each pair of si and di. An edge with capacity [0, 1] between each di and sj, if source sj is reachable with a reasonable amount of time and cost from the destination of flight i. An edge with capacity [0, ∞] between s and t.
В описанном методе утверждается и доказывается, что нахождение потока со значением k в G между s и t эквивалентно нахождению выполнимого расписания для набора рейсов F, требующего не более k экипажей. Другая версия задачи составления расписания авиакомпании заключается в поиске минимально необходимого количества экипажей для выполнения всех рейсов. Для решения этой задачи создаётся двудольный граф, в котором каждый рейс представлен копией в множестве A и множестве B. Если один и тот же самолёт может выполнять рейс j после рейса i, то i ∈ A соединяется с j ∈ B. Сопоставление в G' определяет расписание для F, и, очевидно, максимальное двудольное сопоставление в этом графе даёт расписание авиакомпании с минимальным количеством экипажей.
Расширения
1. В задаче о потоке минимальной стоимости каждая дуга (u,v) имеет, помимо своей пропускной способности, также коэффициент стоимости auv. Если поток через дугу равен fuv, то общая стоимость равна auvfuv. Требуется найти поток заданного размера d с минимальной стоимостью. В большинстве случаев коэффициенты стоимости могут быть как положительными, так и отрицательными. Для этой задачи существует несколько алгоритмов, работающих за полиномиальное время. 2. К задаче о максимальном потоке можно добавить дизъюнктивные ограничения: отрицательное дизъюнктивное ограничение означает, что определённая пара дуг не может одновременно иметь ненулевой поток; положительное дизъюнктивное ограничение означает, что хотя бы одна из определённой пары дуг должна иметь ненулевой поток. При наличии отрицательных ограничений задача становится сильно NP-трудной даже для простых сетей. При наличии положительных ограничений задача решается за полиномиальное время, если допускаются дробные потоки, но может быть сильно NP-трудной, если потоки должны быть целыми.