Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
THEN IF ДЛИНА) = ? % v - новая { ДОБАВИТЬ, ДЛИНА) := ДЛИНА) + 1}; % добавить (u,v) к сети AN: 15 AL(u) := AL(u) ? {v}; AM (v) := AM (v) ? {u}; 16 ac(u, v) := c(u, v) ? f (u, v) 17 } ; 18 FOR ALL v ? M(u) DO % поиск обратных дуг (ДЛИНА) < ДЛИНА) ? ДЛИНА) AND f(v, u) > 0) 20 THEN IF ДЛИНА) = ? % v - новая { ДОБАВИТЬ, ДЛИНА) := ДЛИНА) + 1}; 23 IF ac(u, v) = 0 % добавить (u,v) к сети AN 24 THEN { AL(u) := AL(u) ? {v}; AM(v) := AM(v) ? {u} }; 25 ac(u, v) := ac(u, v) + f (v, используя "обратный"поиск в ширину от t, удалить из AN(f) все вершины, из которых нет пути в t и инцидентные им дуги. Следующая теорема устанавливает основные свойства алгоритма ПОВС и получаемой в его результате вспомогательной сети. Теорема 7.4. а) Если в результате работы алгоритма ПОВС ДЛИНА) = ?, тов сети N нет увеличивающего пути от s к t и, следовательно, поток f максимальный. б) Если ДЛИНА) = l 6= ?, то кратчайший увеличивающий путь изв в сети имеет длину l. Более того, пути изв в сети AN взаимно однозначно соответствуют увеличивающим путям длины l в сети в) Если maxf величина максимального потока в N, то величина максимального потока в AN(f) равна maxf ? г) Время работы процедуры ПОВС O(|E|) ? где n = |V Пример 19. Применим алгоритм ПОВС к сети N с потоком f, приведенной на рис. В результате получится сеть AN(f), показанная наследующем рисунке. Отметим, что b a c f Рис. 29: Вспомогательная сеть AN(f) для сети N с потоком f с рис. 27 62 вершина g не попала в эту сеть, так как единственное, ведущее в нее ребро (b, g) насыщено, т.е. f(b, g) = c(b, g), и ДЛИНА) = ? до конца алгоритма. Определение 27. Поток g в сети AN называется тупиковым, если для него не существует увеличивающего пути без обратных дуг ( прямого увеличивающего пути). Определение 28. Потенциал p(v) вершины v в сети N - это максимальное количество потока, которое можно протолкнуть через v, те. p(v) = min(P u?V c(u, v), P u?V c(v, для v ? V \ {s, t} , p(s) = P u?V c(s, u), p(t) = P u?V c(u, АЛГОРИТМ МАХП ПОСТРОЕНИЯ МАКСИМАЛЬНОГО ПОТОКА Вход: сеть N = (V, E, s, t, Выход максимальный поток f в N. 1 FOR ALL v ? V DO f(u, v) := 0; готово := "нет готово="нет" DO % Новый этап: 3 { ПОВС; % построить вспомогательную сеть AN(f) 4 IF t недостижима изв готово := "да максимальный поток построен Построение тупикового потока ALL (u, v) ? E(f) DO g(u, v) := инициал. тупикового потока p(s) > 0 AND p(t) > 0 найти v с минимальным потенциалом p(v) > ПРОТОЛКНУТЬ, ПРОТЯНУТЬ, p(v)) 12 WHILE есть v ? V (f) \ {s, t}, для которой p(v) = 0 13 DO удалить v и все инцидентные ей дуги из AN(f); 14 } % Добавление тупикового потока ALL (u, v) ? E DO 16 IF (u, v) ? E(f) % прямая дуга f(u, v) := f(u, v) + g(u, v) 18 ELSE IF (v, u) ? E(f) % обратная дуга f(u, v) := f(u, v) ? g(u, v) 20 } } PROCEDURE ПРОТОЛКНУТЬ(y,h) увеличивает поток g на h единиц, проталкиваемых от y к создать очередь Q; ДОБАВИТЬ, y); % треб и треб размер выталкиваемого из y и u потока: 2 треб[y] := h; 3 FOR ALL u ? V (f) \ {y} DO треб := 0; 4 WHILE Q 6= ? DO 5 { v НАЧАЛО УДАЛИТЬ, v); 6 FOR ALL v 0 ? AL(v) and UNTIL треб = 0 DO 7 { m := min(ac(v, треб, v 0 ) := ac(v, v 0 ) ? m; 63 9 g(v, v 0 ) := g(v, v 0 ) + m; 10 IF треб = 0 THEN ДОБАВИТЬ, v 0 ) треб := треб ? треб треб + m; 13 IF ac(v, v 0 ) = 0 THEN E(f) := E(f) \ {(v, v 0 )}; 14 } PROCEDURE ПРОТЯНУТЬ, Эта процедура увеличивает поток g на h единиц, протягиваемых от s к Алгоритм аналогичен процедуре ПРОТОЛКНУТЬ. Пример 20. Построим тупиковый поток g для вспомогательной сети AN(f), приведенной на рис. 29. Минимальный потенциал, равный 1, имеют три вершины b, c и f. Выбрав в качестве v вершину b, после завершения процедур ПРОТОЛКНУТЬ, ПРОТЯНУТЬ b a c f e t (1) 0 (1)1 (1) 1 (2) 1 (1) 1 (2) 2 (2) 1 (3) 1 (2) Рис. 30: Вспомогательная сеть AN(f) для сети N с потоком f ( рис. получим поток g(s, b) = g(b, f) = g(f, t) = 1. Затем будут удалены вершины b и f и инцидентные им дуги (f, t), (b, t), (a, f) и (s, b). Тогда минимальный потенциал 1 останется у вершины c. После вызова процедур ПРОТОЛКНУТЬ, ПРОТЯНУТЬ) получим потоки будет удалена вершина c с дугами (a, c) и (c, e). После этого потенциал p(e) = 1 и после вызова процедур ПРОТОЛКНУТЬ, ПРОТЯНУТЬ) поток на дуге (e, t) увеличится на 1, что в результате даст g(e, t) = 2, g(a, e) = 1, g(s, a) = 1. После удаления e и дуги (e, t) отенциал p(t) = 0 и алгоритм построения тупикового потока завершается. Результирующий поток g показан на рисунке Лемма 7.2. Дуга e сети AN(f) удаляется из E(f) на некотором шаге только в том случае, если в AN(f) нет прямого увеличивающего пути относительно потока g, проходящего через Доказательство. Так как для любой дуги e вначале этапа g(e) = 0, а затем уменьшение ее пропускной способности и увеличение потока происходят одновременно и на одну и туже величину (стр. 8 и 9 процедуры ПРОТОЛКНУТЬ, тов каждый момент (после стр. 9) g(e) + ac(e) = где ac 0 (e) начальная пропускная способность дуги e. Поэтому, если эта дуга удаляется в стр. 12 процедуры ПРОТОЛКНУТЬ, то g(e) = и e не может входить в прямой увеличивающий путь в AN(f). Если же e = (u, v) удаляется в стр. 13 МАХП, то либо p(u) = либо p(v) = 0. В первом случае для всякой входящей в u дуги e 1 g(e 1 ) = а во втором дл всякой выходящей из v дуги e 2 g(e 2 ) = В обоих случаях это означает, что нет прямого увеличивающего пути через Лемма 7.3. В конце каждого этапа g тупиковый поток в AN(f). 64 Доказательство. Переход на новый этап происходит, когда в стр. 8 МАХП проверяется, что p(s) = 0 или p(t) = 0. В первом случае g(e) = для всякой дуги e, выходящей из s, во втором - тоже имеет место для всякой дуги e, входящей в t. В обоих случаях это означает, что в AN(f) нет прямого увеличивающего пути. Лемма 7.4. Расстояние от s до t в AN(f + g) на произвольном этапе строго больше, чем расстояние от s до t в AN(f) на предыдущем этапе. Доказательство. Вспомогательная сеть AN(f + g) совпадает со вспомогательной сетью сети AN(f) относительно потока g (Доказать. По лемме 3 поток g тупиковый, те. в (f нет прямых увеличивающих путей относительно g. Поэтому все имеющиеся увеличивающие пути "непрямые те. их длины больше, чем расстояние от s до t в AN(f), и лемма следует из теоремы 4.б. Теорема 7.5. Алгоритм МАХП корректно решает задачу о максимальном потоке для сети = (V, E, s, t, за время O(n 3 ) (n = |V Доказательство. Алгоритм МАХП завершается (стр. 4,5), когда в сети AN(f) s и t не связаны. Но тогда в этой сети максимальный поток нулевой и по теореме в val(f) = те. f максимальный поток. Для оценки времени отметим, что по лемме 4 число этапов не превосходит |V |. На каждом этапе построение вспомогательной сети AN(f) алгоритмом ПОВС выполняется за O(|V шагов. После выполнения процедур ПРОТОЛКНУТЬ и ПРОТЯНУТЬ для вершины v ее потенциал) становится нулевым (почему ?) иона удаляется из сети (стр. 13). Поэтому число вызовов каждой из них на одном этапе < |V |. Оценим теперь общее число обработок дуг на каждом этапе. При каждой такой обработке дуги (v, в стр. 9 процедуры ПРОТОЛКНУТЬ (ПРОТЯНУТЬ) поток g(v, увеличивается. Назовем такое увеличение насыщающим, если после него этот поток равен исходной пропускной способности дуги, те. g(v, v 0 ) = ac 0 (v, а остаточная пропускная способность ac(v, v 0 ) = Ясно, что для каждой дуги насыщающее увеличение потока может произойти не более одного раза и, следовательно, общее число насыщающих увеличений не превосходит |E|. В каждом вызове процедур ПРОТОЛКНУТЬ и ПРОТЯНУТЬ число ненасыщающих увеличений не превосходит числа выбираемых из очереди вершин, поскольку для каждой из них такое увеличение может произойти лишь по одной дуге. Так как в процедуре ПРОТОЛКНУТЬ (ПРОТЯНУТЬ) каждая вершина может попасть в очередь Q только 1 раз, то число ненасыщающих увеличений при вызове каждой из этих процедур не превосходит |V |. Таким образом, общее число увеличений потока (в стр. 9) на одном этапе не превосходит |E| + |V и каждый этап можно выполнить за время O(|V Отсюда общее время работы алгоритма МАХП можно оценить как O(|V ЗАДАЧА. Написать алгоритм для процедуры ПРОТЯНУТЬ. 7.3 Сети с единичными пропускными способностями Рассмотрим работу алгоритма МАХП на сетях, в которых пропускные способности всех дуг равны Лемма 7.5. Каждый этап алгоритма МАХП, примененного к сети N = (V, E, s, t, c), такой что c(e) = 1 для любой дуги e из E, можно выполнить за O(|E|) шагов. Доказательство. В этом случае и во вспомогательной сети AN(f) на каждом этапе пропускные способности дуг будут равны 1. Но тогда кажда дуга может обрабатываться в процедурах ПРОТОЛКНУТЬ и ПРОТЯНУТЬ не более 1 раза, после чего она "насыщается"и удаляется из сети Лемма 7.6. В сети N из леммы 5 расстояние l между s и t не может быть больше, чем 2 ? |V |/pval(fm) , где fm максимальный поток. Доказательство. Пусть V i = {v расстояние от s до v равно i}. Множество вершин V i = V 0 ?V 1 ?...?V i задает разрез в N при i < l. Тогда f(V V i , V \V V i ) = |{e | e дуга изв Но число дуг извне больше, чем |V i | ? Поэтому либо либо |V i+1 | Отсюда следует, что по крайней мере для каждого второго уровн V i имеет место |V i | и l ? pval(fm) ? 2 ? |V Теорема 7.6. Для сетей с единичными пропускными способностями дуг время работы алгоритма МАХП не превосходит O(|E| ? |V Доказательство. Покажем, что число этапов s не превосходит |V | 2/3 a) Если val(fm) ? |V то этапов "мало так как на каждом этапе поток увеличивается по крайней мерена б) Если val(fm) > |V то пусть i такой этап, после которого впервые поток превосходит Пусть g это поток вначале этапа i. Так как величина дополнительного потока ? |V то s ? i ? |V С другой стороны, i < (расстояние от s до t в сети (g) ) ? 2 ? |V |/pval(fm) ? val(g) (по лемме 6 итак как величина максимального потока в AN(g) равна val(fm) ? val(g) по теореме в. Но по выбору g имеем перед i-ым этапом val(f m) ? val(g) ? |V Отсюда i ? 2 ? |V и s ? 3 ? |V Теперь теорема следует из леммы 5 и этой оценки числа этапов. Определение 29. Сеть, у которой пропускные способности всех дуг равны 1, назовем простой, если для любой вершины сети степень захода или степень исхода равны 1 или Лемма 7.7. В простой сети N расстояние l между s и t не может быть больше, чем |/val(f где fm максимальный поток. Доказательство. Определим V i как в лемме 6. Так как через каждую вершину может проходить не более одной единицы максимального потока, а весь он проходит через каждое V i , то val(fm) ? Отсюда l ? val(fm) ? |V Теорема 7.7. Для простых сетей время работы алгоритма МАХП не превосходит O(|E|p|V Доказательство. Покажем, что число этапов s не превосходит p|V |. a) Если val(fm) ? p|V |, то этапов "мало так как на каждом этапе поток увеличивается по крайней мерена б) Если val(fm) > p|V |, то пусть i такой этап, после которого впервые поток превосходит. Пусть g поток вначале этапа i. Величина максимального потока в AN(g) ? p|V |. Тогда по лемме 7 l ? p|V |. ( Докажите, что AN(f) простая сеть и лемма применима. Поэтому i ? p|V | и s ? i ? p|V |, те. s = O(p|V Максимальные паросочетания в двудольных графах Определение 30. Паросочетание в неориентированном графе G = (V, E) это произвольное подмножество ребер M такое, что никакие два ребра из него не имеют общей вершины. Паросочетание наибольшей мощности называется максимальным. Напомним определение двудольных графов, рассмотренных в задаче Определение 31. Граф G = (V, E) называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества X итак, что каждое ребро e ? имеет вид e = (x, y), где x ? X, а y ? Y. 66 Пусть дан двудольный граф B = (X, Y, E). Определим сеть N(B) = (W, A, s, t, c) : 1) вершины W = s, t ? X ? Y ; 2) дуги A = {(s, x) | x ? X} ? {(y, t) | y ? Y } ? {(x, y) | (x, y) ? E}; 3) пропускные спосбности c(e) = 1 для всех e ? Замечание. Построенная сеть N(B) - простая. Лемма 7.8. Мощность максимального паросочетания в графе B равна величине максимального потока в сети Доказательство. Пусть M паросочетание в B. Определим поток f в N(B) следующим образом. Для каждой дуги (u, v) ? M положим f(s, u) = 1, f(u, v) = 1, f(v, t) = 1. Тогда f - допустимый потоки Пусть теперь f максимальный поток в N(B), построенный алгоритмом МАХП. Тогда он имеет целочисленные значения (0 или 1). Пусть M состоит из таких дуг (u, v), для которых f (u, v) = Нетрудно проверить, что M паросочетание и что |M| = Теорема 7.8. Задачу о максимальном паросочетании для двудольных графов можно решить за время O(|E| ? p|V Доказательство. Алгоритм поиска максимального паросочетания работает следующим образом) По графу B строим сеть N(B). 2) С помощью алгоритма МАХП находим максимальный поток в N(B). 3) Поэтому потоку строим максимальное паросочетание в B (по лемме Так как N(B) простая сеть, то время го этапа - O(|E|?p|V |). Время го этапа а время гоп о чему. Отсюда следует оценка теоремы. Пример 21. Рассмотрим двудольный граф B = (X, Y, E), в котором X = {x 1 , x 2 , x 3 , x 4 }, Y = {y 1 , y 2 , y 3 , y 4 } E = {(x 1 , y 1 ), (x 1 , y 2 ), (x 2 , y 4 ), (x 3 , y 1 ), (x 4 , y 3 ), (x 4 , y 4 )} . Соответствующая ему простая сеть N(B) показана на рис. 31. 67 1 P P P P q @ @ @ @ R @ @ @ @ R P P P P q 1 - P P P P P P P P q - 1 H H H H H H H H H H j * s Рис. 31: Сеть Вспомогательная сеть AN(B)(0) для любой сети N(B) относительно нулевого потока совпадает с самой N(B) (почему ?). Построив тупиковый поток g на AN(B) и добавив его к нулевому потоку, получим на N(B) поток f(= g), показанный на рис. 32. 1 P P P P q @ @ @ @ R @ @ @ @ R P P P P q 1 - P P P P P P P P q - 1 H H H H H H H H H H j * s Рис. 32: Сеть N(B) с текущим потоком Построим теперь вспомогательную сеть AN(B)(f) для N(B) относительно построенного потока f. Она показана на рис. 33. s Рис. 33: Сеть В этой сети ребро (y 1 , обратное, а остальные прямые. Ясно, что тупиковый поток в этой сети равен 1 на всех ребрах. После его добавления к предыдущему потоку получаем сеть с новым потоком f, показанную на рис. 34. 68 1 P P P P q @ @ @ @ R @ @ @ @ R P P P P q 1 - P P P P P P P P q - 1 H H H H H H H H H H j * s Рис. 34: Сеть N(B) с максимальным потоком Этот поток, очевидно, является максимальным (попытка построить вспомогательную сеть поместит в нее лишь вершину s). Ему соответствует максимальное паросочетание M = {(x 1 , y 2 ), (x 2 , y 4 ), (x 3 , y 1 ), (x 4 , в графе B. 7.4.1 Паросочетания в общих графах В определении 30 понятие паросочетания и максимального паросочетания было определено для произвольного неориентированного графа G = (V, E). Для взвешенных графов максимальным называется паросочетание наибольшего веса. Совершенным называется паросочетание, ребра которого инцидентны всем вершинам графа. Оно, например, всегда существует в полном графе четной степени или в графе-цикле четной длины. Для взвешенных графов минимальное совершенное паросочетание это совершенное паросочетание минимального веса. Для поиска максимальных и минимальных совершенных паросочетаний в произвольных неориентированных графах имеется достаточно эффективный алгоритм, предложенный Эдмондсом и Джонсоном (см. например, [5], глава 12, [9], глава 5, [8], глава 9). Его сложность не превосходит O(|V Отметим также, что теория паросочетаний в двудольных и произвольных графах имеет много важных приложений в математике, физике, химии и других областях. Многие вопросы этой теории и ее приложений рассмотрены в монографии [8]. 7.5 Задачи Задача 7.1. Используя алгоритм Форда-Фалкерсона, построить максимальный поток для сети N : V = {s, v1, v2, v3, t}, E = {(s, v1, 2), (s, v2, 2), (s, v3, 2), (v1, v2, 1), (v1, t, 1), (v2, v3, 2), (v2, t, 1), (v3, t, 3)} ( формат (v, u, c(v, Задача 7.2. Построить, используя алгоритм МАХП, тупиковый поток для следуюшей (вспомогательной) сети ( формат (v, u, c(v, u))) : (s, v1, 7), (s, v2, 6), (s, v3, 5), (v1, v4, 7), (v2, v5, 5), (v3, v6, 4), (v2, v6, 3), (v4, t, 4), (v5, t, 5), (v1, v5, 1), (v6, t, Задача 7.3. Построить, используя алгоритм МАХП, максимальный поток для следую- шей сети N : V = {s, v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , t}, E = (s, v 1 , 5), (s, v 2 , 3), (s, v 3 , 5), (v 1 , v 4 , 7), (v 2 , v 5 , 5), (v 3 , v 6 , 4), (v 6 , v 2 , 3), (v 4 , t, 4), (v 5 , t, 5), (v 1 , v 5 , 2), (v 6 , t, 3). ( формат (v, u, c(v, Задача 7.4. Назовем запасом связности неориентированного графа минимальное число ребер, которые необходимо удалить, чтобы сделать его несвязным. Например, для дерева это число равно 1, для простого цикла 2. Чему оно равно для полного вершинного графа? Какова сложность "переборного"алгоритма для нахождения запаса связности Постройте алгоритм вычисления запаса связности по графу, использующий сведение этой задачи к задаче нахождения максимального потока и оцените его сложность. Задача 7.5. Пусть в сети N = (V, E, s, t) заданы пропускные способности дуги вершин d(v), v ? V . Поток через вершину v не должен превышать d(v). Покажите, как задачу о максимальном потоке в такой "обобщенной"сети можно свести к задаче о максимальном потоке в "обычной"сети. Используйте это сведение для решения следующей задачи о выходе. Имеется граф G = (V, E), вершины которого расположены в вершинах прямоугольной плоской решетки V = {(i, j) |i = 1, . . . , n, j = 1, . . . , n, }. Ребра графа это отрезки, соединяющие соседние вершины, в частности, у каждой "внутренней"вершины (i, j) имеется 4 соседа ? 1, j), (i, j + 1), (i + 1, j), (i, j ? 1) , ух "угловых"вершин по 2, ау вершин на "границах "графа по 3. Скажем, что подмножество из m вершин U ? V имеет выход , если существует m непересекающихся путей, соединяющих вершины U с граничными вершинами графа G. Предложите алгоритм, который пои подмножеству U ? V определяет имеет ли U выход. Оцените его сложность. Задача 7.6. Предположим, что известен максимальный поток f в сети N = (V, E, s, t; и пропускные способности всех ребер целые числа. Предположим, что пропускная способность некоторого ребра (u, v) увеличилась на 1: c 0 (u, v) = c(u, v) + 1 . Предложите алгоритм, находящий максимальный поток для измененной сети за время O(|V | + |E|). Предложите также алгоритм, решающий туже задачу в случае уменьшения пропускной способности ребра (u, v) на Задача 7.7. Пусть обобщенная сеть - это сеть, для каждой дуги (u, v) которой указана как верхняя c(u, v), таки нижняя b(u, v) граница величины потока. Показать, что задачу о максимальном потоке в обобщенной сети можно свести к задаче о максимальном потоке в "обычной"сети. (Рассмотрите случай, когда для каждой v сумма b(u, v) по входяшим в v дугам равна сумме b(v, w) по выходящим из v дугам). Задача 7.8. Показать, что для простой сети N с потоком f , имеющим значения 0 или вспомогательная сеть AN(f) является простой. Задача 7.9. Доказать, что длины всех путей изв во вспомогательной сети AN(f) одинаковы и равны длине кратчайшего увеличивающего пути в N с потоком Задача 7.10. По договору с рестораном поставщик должен обеспечивать поставку d i сафе- ток в i-ый день в течение n дней. Салфетки можно покупать по цене a рублей за штуку или отдавать в стирку старые салфетки. Обычная стирка одной салфетки стоит b руби требует двух дней, экспресс-стирка одной салфетки обходится вруби они готовы через один день. Определить оптимальную политику поставщика по закупке и стирке салфеток (т.е. политику, минимизирующую его затраты. Оценить сложность получившегося алгоритма. Задача 7.11. Предложить алгоритм для поиска вершины с минимальным потенциалом в алгоритме МАХП (стр. 12) и оценить его сложность Задача 7.12. Доказать, что алгоритм ПОВС можно реализовать за время O(|V | + указание использовать для представления ac и af не массивы, а списки, связанные с дугами сети). Задача 7.13. Пусть дана сеть N = (V, E, s, t; c), у которой некоторые пропускные способности дуг могут быть отрицательны. Построить алгоритм, который находит максимальный поток в этой сети и оценить его сложность. Указание. Рассмотрите сеть N 0 = (V 0 , E 0 , s 0 , t 0 ; c 0 ) : V 0 = V ? {s 0 , t 0 } ; E 0 = E ? {(u, v) | (v, u) ? E} ? {(s 0 , v) | v ? V } ? {(u, t 0 ) | u ? V } ? {(s, t), (t, Для каждого ребра (u, v) ? E положим c 0 (u, v) = c 0 (v, u) = (c(u, v) + c(v, u))/2 . c 0 (s 0 , u) = max{0, (c(V, u) ? c(u, V для каждой u ? V и c 0 (u, t 0 ) = max{0, (c(u, V ) ? c(V, для каждой u ? V . Кроме того, положим c 0 (s 0 , t 0 ) = c 0 (t 0 , s 0 ) = а) Докажите, что если в сети N существует поток, тов сети все пропускные способности неотрицательны ив ней существует максимальный поток, в котором все ребра, входящие в t 0 насыщены. б) По любому потоку в N 0 , в котором все ребра, входящие в насыщены, можно построить поток в Задача 7.14. Предложите алгоритм, который посети и максимальному потоку в ней f m находит такое ребро, увеличение пропускной способности которого приводит к увеличению максимального потока. Оцените его сложность. Задача 7.15. Найти максимальное паросочетание в двудольном графе, используя сведение к задаче о максимальном потоке для простой сети. G =< {v1, v2, v3, v4}, {u1, u2, u3, u4, u5}, E = {(v1, u1), (v1, u2), (v2, u2), (v2, u4), (v3, u1), (v3, u2), (v4, u5), (v4, u3), (v4, u4)} Задача 7.16. Пусть G = (V, E) двудольный граф с равномощными долями, те. V = X ? Y, X ? Y = и |X| = |Y |. Совершенным паросочетанием в таком графе называется паросочетание, в которое входят все вершины. Для каждого подмножества вершин U ? определим множество соседних вершин N(U) = {w|?u ? U[(u, w) ? E]}. Докажите, что в G существует совершенное паросочетание тогда и только тогда, когда для любого A ? выполнено |A| ? |N(A)| (теорема Холла полные задачи для графов Полиномиальная сводимость и полные задачи В предыдущих разделах мы рассмотрели много алгоритмических задач для графов и для решения каждой из них находился достаточно эффективный алгоритм. Самые сложные из этих задач поиск кратчайших путей в произвольном графе и поиск максимального потока в транспортной сети решались за время O(n 3 ) , где n число вершин графа. Однако имеется много важных для приложений задач на графах, для которых неизвестны алгоритмы полиномиальной сложности относительно размеров рассматриваемых графов. Эти задачи принадлежат классу так называемых полных задач. Для задач этого класса по мнению большинства исследователей не существует алгоритмов, работающих в полиномиальное время, хотя формально эта гипотеза не доказана и сначала х годов ХХ века является одной из самых интригующих проблем информатики. Напомним основные понятия, связанные с полнотой. В качестве алгоритмических проблем будем рассматривать проблемы разрешения, те. проблемы вхождения элемента во множество. Проблемы разрешения представляют собой пары множеств (D, Y ), где D это множество исходных данных, входов проблемы, являющихся, обычно, строками в некотором конечном алфавите, а Y это подмножество допустимых, распознаваемых, хороших данных из D. Алгоритм (детерминированный) корректно решает такую проблему, если он для каждого входа из Y выдает ответ Да, а для каждого входа из D \Y ответ Нет. Недетерминированный алгоритм для каждого входа порождает дерево вычислений. Он решает проблему, если для всякого входа изв этом дереве есть путь вычисления, приводящий к ответу Да и ни для какого входа из D\Y такого пути нет (предполагается, что на любом пути алгоритм либо останавливается с ответом Да, либо вовсе не останавливается. Временем работы недетерминированного алгоритма считается минимальная длина пути, приводящего к ответу Да. В качестве основной формальной модели алгоритмов обычно рассматриваются детерминированные и недетерминированные машины Тьюринга (ДМТ и НМТ). Для границы сложности f (n) (n длина входа) через DT IME(f) (NT IME(f) обозначим класс проблем разрешения, решаемых ДТМ (НТМ) за время, ограниченное функцией f(n), а через SP ACE(f) класс проблем решаемых ДТМ с емкостной сложностью (в памяти, ограниченной функцией Проблемы разрешения мы будем классифицировать по сложности с помощью хорошо известных классов P = ? ? k=1 DT IM E(n k ) класс проблем, решаемых за полиномиальное время |