А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
какой смысл идти в точку, которая ближе к началу пути, чем текущая? Так что расстояние или останется прежним, или увеличится (ведь одно из рёбер дополняющего пути пропало, и другого пути той же длины может не быть). Формально говоря, мы не рассмотрели случай, когда расстояние уже было бесконечным (пути из 𝑠 в 𝑢 не было) и не доказали, что оно останется бесконечным. Тут надо сказать так: новые рёбра могут вести только в вершины, доступные из 𝑠, потому новых доступных вершин не появится. 9.3. Сети, потоки и разрезы 171 Как мы уже говорили, на каждом шаге работы алгоритма (увели- чение потока вдоль дополняющего пути) одно из рёбер дополняющего пути (то, где пропускная способность минимальна | его ещё назы- вают критическим ребром) исчезает, заменяясь на противоположное. Если мы оценим сверху, сколько раз это может происходить с каждым ребром, то получим и верхнюю оценку для числа шагов (умножив на общее число рёбер). 9.3.24. Докажите, что одно и то же ребро не может быть критиче- ским (в ту и в другую сторону) более чем 𝑂(𝑛) раз. (Напомним, что 𝑛 | число вершин.) Решение. Пусть нас интересует ребро 𝑢{𝑣. Оно может быть крити- ческим лишь поочерёдно в ту и в другую сторону. Будем следить, как меняются расстояния от истока до 𝑢 и до 𝑣. Мы уже знаем, что они мо- гут только возрастать (и не превосходят 𝑛, раз у нас всего 𝑛 вершин). При этом, когда ребро критическое, одно из расстояний превышает другое ровно на 1, как мы видели. Остаётся заметить, что если есть два пешехода, которые идут по дороге в 𝑛 километров, не поворачивая назад, и в какой-то момент первый обгонял второго на километр, потом второй первого, потом снова первый второго и так далее, общее число таких моментов не больше 𝑛 (потому что между соседними моментами один из пешеходов должен пройти как минимум два километра, а всего они проходят 2𝑛). Отсюда следует, что алгоритм Эдмондса { Карпа всегда завершает работу, и тем самым мы доказали теорему Форда { Фалкерсона в общем случае (не только для целых пропускных способностей). Можно попробовать оценить время работы этого алгоритма. Сразу видно, что он, как говорят, полиномиальный (время работы ограничено полиномом от 𝑛), никакого перебора экспоненциального числа вариан- тов в нём нет. При практической реализации полезно хранить данные (значения 𝑐 и 𝑓) не про все пары вершин, а только для тех пар, которые в изначальной сети соединены ребром (и у каждой вершины иметь спи- сок соседей в исходном графе) | для всех остальных пар и в массиве 𝑐, и в массиве 𝑓 стоят только нули, которые так и остаются нулями. Если, следуя традиции, обозначать число вершин за 𝑉 , а число рёбер за 𝐸, то при таком способе хранения данных ∙ поиск кратчайшего пути (поиск в ширину) требует 𝑂(𝐸) шагов; ∙ коррекция вдоль дополняющего пути требует 𝑂(𝑉 ) шагов (что поглощается 𝑂(𝐸) шагами поиска); 172 9. Разные алгоритмы на графах ∙ число итераций есть 𝑂(𝐸𝑉 ), потому что каждое из 𝐸 рёбер явля- ется критическим 𝑂(𝑉 ) раз. 9.3.25. Какое общее число шагов дают эти оценки? Ответ. Всего получается 𝑂(𝐸 2 𝑉 ). Есть много более эффективных алгоритмов (построенных на раз- ных идеях), это большой раздел информатики, но мы ограничимся при- ведённым простым алгоритмом, и в заключение приведём два примера, когда этот алгоритм можно использовать для решения других задач. Первый пример совсем простой. 9.3.26. Рассмотрим сеть без стока и истока, и будем искать в ней циркуляции (жидкость циркулирует по трубам, ∑︀ 𝑗 𝑓[𝑖,𝑗] = 0 при всех 𝑖). Будем разрешать отрицательные значения функции 𝑐[𝑖, 𝑗] (что означа- ет, что в некоторых трубах указано минимальное допустимое значение потока). Как проверить, возможна ли в данной сети циркуляция? Решение. Добавим к сети отдельные вершины стока и истока, и соединим их со всеми вершинами исходной сети трубами пропускной способности 𝑐, где 𝑐 | достаточно большая константа. 𝑠 𝑡 Построим в полученной сети некоторый поток. Для этого пустим по каждой трубе какое-то разрешённое количество жидкости (предпола- гаем, что для каждой трубы условия на 𝑓[𝑖, 𝑗] и 𝑓[𝑗, 𝑖] не противоречат друг другу, иначе задача тривиальна), беря эту жидкость при необхо- димости по трубе из истока и сливая её по трубе в сток. Проблем не возникнет, поскольку мы предположили, что 𝑐 достаточно велико. Итак, у нас есть некоторый поток в результирующей сети. Теперь используем алгоритм Эдмондса { Карпа для его максимизации. Ясно, что не может получиться больше 𝑐𝑉 , где 𝑉 | число вершин, и что 9.3. Сети, потоки и разрезы 173 ровно 𝑐𝑉 получится в том и только том случае, когда в исходной сети существует циркуляция. Второй пример | эта задача о максимальном паросочетании в дву- дольном графе. В адаптированном для школьников варианте её можно сформулировать так. Есть несколько школьников, каждый из них ре- шил несколько задач. Надо организовать разбор максимального числа задач, при этом один и тот же школьник не может выступать дважды, и нельзя дважды рассказывать одну и ту же задачу. 9.3.27. Схема «кто что решил» показана на рисунке (слева школь- ники 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, справа задачи 1, 2, 3, 4, 5). Какое максимальное число задач можно разобрать, соблюдая ограничения? 𝑎 𝑏 𝑐 𝑑 𝑒 1 2 3 4 5 школьники задачи Решение. Можно организовать разбор трёх задач (паросочетание 𝑎{2, 𝑏{1, 𝑒{5, см. рисунок). Как убедиться, что больше нельзя, не перебирая варианты? Заме- тим, что школьники 𝑎, 𝑐, 𝑑, 𝑒 не решили ничего, кроме задач 2 и 5 (а школьник 𝑑 даже и задачу 2 не решил, но это не важно). Поэтому из них могут выступить только двое | а двое других останутся не у дел. Терминология: двудольный граф на рисунках состоит из левой доли (школьники) и правой доли (задачи). Паросочетание (способ разбо- ра) | набор рёбер, у которых все левые концы разные (ни один школь- ник не выступает дважды) и все правые концы разные (ни одну задачу 174 9. Разные алгоритмы на графах не рассказывают дважды). Аналогичную задачу о максимальном па- росочетании можно поставить для произвольного двудольного графа (произвольной схемы соединения вершин слева и справа). 9.3.28. Найдите максимальное паросочетание в произвольном дву- дольном графе, сведя эту задачу к отысканию максимального потока. Решение. Будем считать рёбра графа идущими слева направо и име- ющими неограниченную пропускную способность, и добавим исток сле- ва и сток справа, соединив их с вершинами односторонними рёбрами с пропускной способностью 1. 𝑠 𝑡 1 1 1 1 Целочисленный поток в таком графе | это в точности паросочета- ние. В самом деле, приходящая из истока единица потока должна ку- да-то направиться. Поскольку поток целый, то она может пойти только по одному ребру. И если два таких использованных ребра приведут в одну вершину справа, то из неё уже поток не сможет выйти. А как искать максимальный целочисленный поток, мы знаем, для этого да- же алгоритм Эдмондса { Карпа не нужен, можно использовать любые дополняющие пути. В этой задаче дополняющие пути в остаточной сети имеют ясный смысл: из левой доли мы идём вправо по неиспользованным рёбрам гра- фа, потом влево по использованным, потом снова вправо по неисполь- зованным и так далее, поэтому этот алгоритм называют иногда «поиск максимального паросочетания с помощью чередующихся цепей». 9.3. Сети, потоки и разрезы 175 Мы поняли, что (целочисленные) потоки в построенной сети со- ответствуют паросочетаниям. А чему соответствуют разрезы и что можно извлечь из совпадения максимального потока и минимального разреза? Вспомним объяснение про школьников: поток не может быть большим, потому что есть четыре школьника, которые решили одни и те же две задачи. Оказывается, что именно такого рода препятствие есть всегда, и это как раз соответствует разрезу в сети. Представим себе, что в левой доле, где всего 𝑚 вершин, есть набор 𝑈 из 𝑢 вершин, у которых все их соседи входят в какой-то набор 𝑉 из меньшего числа вершин 𝑣 в правой доле. 𝑚 𝑛 𝑈 𝑉 𝑢 𝑣 Это означает, что как минимум 𝑢 − 𝑣 вершин слева останутся без дела, так что максимальное паросочетание не превосходит 𝑚 − (𝑢 − 𝑣) = 𝑚 − 𝑢 + 𝑣. Оказывается, что такую оценку всегда можно сделать точной. 9.3.29. Пусть в двудольном графе (слева 𝑚 вершин, справа 𝑛 вер- шин) не существует паросочетания размера 𝑘 > 0. Тогда в левой доле есть набор 𝑈 из 𝑢 вершин, а в правой доле есть набор 𝑉 из 𝑣 вершин, для которых (1) все соседи вершин из 𝑈 попадают в 𝑉 ; (2) 𝑚 − 𝑢 + 𝑣 < 𝑘. (Поскольку исходная задача симметрична, можно сформулировать и симметричное утверждение о вершинах в правой доле и их соседях в левой доле; это эквивалентно переходу от множеств 𝑈 и 𝑉 к их допол- нениям.) Решение. Рассмотрим максимальный разрез | по теореме Фор- да { Фалкерсона он меньше 𝑘. Левая его компонента 𝑆 содержит исток, какие-то вершины левой доли (назовём их 𝑈), и какие-то вершины пра- вой доли (назовём их 𝑉 ). Заметим, что вершина в 𝑈 не может быть соединена ребром с вер- шиной не из 𝑉 , потому что тогда это ребро попадает в разрез, а та- кие рёбра имеют неограниченную (очень большую) пропускную спо- собность. Пусть в 𝑈 попало 𝑢 вершин, а в 𝑉 попало 𝑣 вершин. Какие 176 9. Разные алгоритмы на графах 𝑚 𝑛 𝑈 𝑉 𝑠 𝑡 рёбра пересекают разрез? Это 𝑚 − 𝑢 рёбер, которые из истока ведут в вершины не из 𝑈, а также 𝑣 рёбер, которые из 𝑉 ведут в сток. Все они имеют пропускную способность 1, поэтому минимальный разрез равен 𝑚 − 𝑢 + 𝑣 и меньше 𝑘 (мы с этого начали). То же самое утверждение в чуть другой форме: 9.3.30. В школе работает несколько кружков. Требуется в каждом кружке выбрать старосту из числа участников этого кружка, причём один человек не может быть старостой двух кружков. Докажите, что это невозможно в том и только том случае, когда при некотором 𝑢 найдётся 𝑢 кружков, в которых вместе занимается меньше 𝑢 человек. Решение. Кружки | точки в левой доле, школьники | в правой, а рёбра ведут от кружка ко всем его участникам. В такой форме это утверждение называют теоремой Холла о пред- ставителях (староста представляет свой кружок). В одну сторону оно очевидно: если в 𝑢 кружках всего занимаются меньше 𝑢 человек, то старост выбрать не удастся. В обратную сторону оно, как мы видели, следует из теоремы Форда { Фалкерсона. Но можно доказать его и без неё. 9.3.31. Докажите это обратное утверждение индукцией по числу кружков, рассмотрев два случая: (1) есть набор из некоторого числа 𝑢 кружков, в которых вместе занимаются ровно 𝑢 школьников, и (2) все- гда есть запас: для любого семейства кружков общее число школьников в них больше числа кружков в семействе. Вот ещё одна переформулировка того же утверждения, называемая теоремой Кёнига; её преимущество в том, что обе доли графа входят в неё симметричным образом. 9.3.32. Покажите, что размер максимального паросочетания в дву- дольном графе равен размеру минимального вершинного покрытия. 9.3. Сети, потоки и разрезы 177 (Множество вершин называется вершинным покрытием, если у любо- го ребра хотя бы один конец принадлежит этому множеству. Вершины можно выбирать из обеих долей.) Следующую задачу можно найти в сборниках олимпиадных задач для школьников, но, по-видимому, её решение по существу требует те- оремы Холла в том или ином виде (а особенно просто её решить, зная о потоках и разрезах). 9.3.33. На контрольной каждый школьник решил 5 задач, и каждую задачу решило 5 школьников. Докажите, что можно организовать раз- бор так, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были бы разобраны. [Указание. Число задач равно числу школьников (посчитаем реше- ния двумя способами), обозначим его за 𝑛. В соответствующем графе есть дробный поток величины 𝑛, в котором каждая задача рассказы- вается с весом 1/5, значит, есть и целый поток такой величины. (Если избегать упоминания потоков, то можно заметить, что препятствие к разбору всех задач из теоремы Холла невозможно, потому что в этом случае из 𝑈 выходит больше рёбер, чем может зайти в 𝑉 .)] 10. СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ 10.1. Простейший пример 10.1.1. Имеется последовательность символов x[1] . . . x[n]. Опреде- лите, имеются ли в ней идущие друг за другом символы abcd. (Други- ми словами, требуется выяснить, есть ли в слове x[1] . . . x[n] подслово abcd.) Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомое подслово в исходном слове. Для каждой из позиций можно проверить, действительно ли там оно нахо- дится, сравнив четыре символа. Однако есть более эффективный спо- соб. Читая слово x[1] . . . x[n] слева направо, мы ожидаем появления бу- квы a. Как только она появилась, мы ищем за ней букву b, затем c, и, наконец, d. Если наши ожидания оправдываются, то слово abcd обнару- жено. Если же какая-то из нужных букв не появляется, мы оказываемся у разбитого корыта и начинаем всё сначала. Этот простой алгоритм можно описать в разных терминах. Ис- пользуя терминологию так называемых конечных автоматов, мож- но сказать, что при чтении слова x слева направо мы в каждый мо- мент находимся в одном из следующих состояний: «начальное» (0), «сразу после a» (1), «сразу после ab» (2), «сразу после abc» (3) и «сра- зу после abcd» (4). Читая очередную букву, мы переходим в следу- ющее состояние по правилу, указанному в таблице (см. следующую страницу). Как только мы попадём в состояние 4, работа заканчива- ется. Наглядно выполнение алгоритма можно представить себе так: фиш- ка двигается из кружка в кружок по стрелкам; стрелка выбирается так, чтобы надпись на ней соответствовала очередной букве входного слова. Чтобы этот процесс был успешным, нужно, чтобы для каждой буквы 10.1. Простейший пример 179 Текущее Очередная Новое состояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a 1 1 кроме a,b 0 2 c 3 2 a 1 2 кроме a,c 0 3 d 4 3 a 1 3 кроме a,d 0 Правила перехода для конечного автомата была ровно одна подходящая стрелка из любого кружка. 0 1 2 3 4 𝑎 𝑎 𝑎 ̸ = 𝑎, 𝑑 ̸ = 𝑎, 𝑐 ̸ = 𝑎, 𝑏 ̸ = 𝑎 𝑎 𝑏 𝑐 𝑑 начало Соответствующая программа очевидна (мы указываем новое состо- яние, даже если оно совпадает со старым; эти строки можно опустить): i:=1; state:=0; {i - первая непрочитанная буква, state - состояние} while (i <> n+1) and (state <> 4) do begin if state = 0 then begin if x[i] = a then begin state:= 1; end else begin state:= 0; end; end else if state = 1 then begin if x[i] = b then begin state:= 2; end else if x[i] = a then begin state:= 1; 180 10. Сопоставление с образцом end else begin state:= 0; end; end else if state = 2 then begin if x[i] = c then begin state:= 3; end else if x[i] = a then begin state:= 1; end else begin state:= 0; end; end else if state = 3 then begin if x[i] = d then begin state:= 4; end else if x[i] = a then begin state:= 1; end else begin state:= 0; end; end; end; answer := (state = 4); Иными словами, мы в каждый момент храним информацию о том, какое максимальное начало нашего образца abcd является концом про- читанной части. (Его длина и есть то «состояние», о котором шла речь.) Терминология, нами используемая, такова. Слово | это любая по- следовательность символов из некоторого фиксированного конечного множества. Это множество называется алфавитом, его элементы | буквами. Если отбросить несколько букв с конца слова, останется дру- гое слово, называемое началом первого. Любое слово также считает- ся своим началом. Конец слова | то, что останется, если отбросить несколько первых букв. Любое слово считается своим концом. Подсло- во | то, что останется, если отбросить буквы и с начала, и с конца. (Другими словами, подслова | это концы начал, или, что то же, начала концов.) В терминах индуктивных функций (см. раздел 1.3 ) ситуацию можно описать так: рассмотрим функцию на словах, которая принимает два значения «истина» и «ложь» и истинна на словах, имеющих abcd своим подсловом. Эта функция не является индуктивной, но имеет индуктив- ное расширение 𝑥 ↦→ длина максимального начала слова abcd, являющегося концом 𝑥. 10.2. Повторения в образце | источник проблем 181 10.2. Повторения в образце | источник проблем 10.2.1. Можно ли в предыдущих рассуждениях заменить слово abcd на произвольное слово? Решение. Нет, и проблемы связаны с тем, что в образце могут быть повторяющиеся буквы. Пусть, например, мы ищем вхождения слова ababc. Вот появилась буква a, за ней идёт b, за ней идёт a, затем снова b. В этот момент мы с нетерпением ждём буквы c. Однако | к нашему разочарованию | вместо неё появляется другая буква, и наш образец ababc не обнаружен. Однако нас может ожидать утешительный приз: если вместо c появилась буква a, то не всё потеряно: за ней могут по- следовать буквы b и c, и образец-таки будет найден. Вот картинка, поясняющая сказанное: x y z a b a b a b c . . . ← входное слово a b a b c ← мы ждали образца здесь a b a b c ← а он оказался здесь Таким образом, к моменту x y z a b a b ← входное слово a b a b c ← мы ждали образца здесь a b a b c ← а он оказался здесь есть два возможных положения образца, каждое из которых подлежит проверке. Тем не менее по-прежнему возможен конечный автомат, чи- тающий входное слово буква за буквой и переходящий из состояния в состояние в зависимости от прочитанных букв. 10.2.2. Укажите состояния соответствующего автомата и табли- цу перехода (новое состояние в зависимости от старого и читаемой буквы). Решение. По-прежнему состояния будут соответствовать наиболь- шему началу образца, являющемуся концом прочитанной части слова. Их будет шесть: 0, 1 (a), 2 (ab), 3 (aba), 4 (abab), 5 (ababc). Таблица перехода показана на следующей странице. 182 10. Сопоставление с образцом Текущее Очередная Новое состояние буква состояние 0 a 1 (a) 0 кроме a 0 1 (a) b 2 (ab) 1 (a) a 1 (a) 1 (a) кроме a,b 0 2 (ab) a 3 (aba) 2 (ab) кроме a 0 3 (aba) b 4 (abab) 3 (aba) a 1 (a) 3 (aba) кроме a,b 0 4 (abab) c 5 (ababc) 4 (abab) a 3 (aba) 4 (abab) кроме a,c 0 Для проверки посмотрим, к примеру, на вторую снизу строку. Ес- ли прочитанная часть кончалась на abab, а затем появилась буква a, то теперь прочитанная часть кончается на ababa. Наибольшее начало образца (ababc), являющееся её концом | это aba. Философский вопрос: мы говорили, что трудность состоит в том, что есть несколько возможных положений образца, каждое из которых может оказаться истинным. Им соответствуют несколько начал образ- ца, являющихся концами входного слова. Но конечный автомат помнит лишь самое длинное из них. Как же остальные? Философский ответ. Дело в том, что самое длинное из них опре- деляет все остальные | это его концы, одновременно являющиеся его началами. Не составляет труда для любого конкретного образца написать про- грамму, осуществляющую поиск этого образца описанным способом. Однако хотелось бы написать программу, которая ищет произволь- ный образец в произвольном слове. Это можно делать в два этапа: сначала по образцу строится таблица переходов конечного автомата, а затем читается входное слово и состояние преобразуется в соответ- ствии с этой таблицей. Подобный метод часто используется для бо- лее сложных задач поиска (см. далее), но для поиска подслова суще- ствует более простой и эффективный алгоритм, называемый алгорит- мом Кнута { Морриса { Пратта. (Ранее сходные идеи были предложены Ю. В. Матиясевичем.) Но прежде нам понадобятся некоторые вспомо- гательные утверждения. 10.3. Вспомогательные утверждения 183 10.3. Вспомогательные утверждения Для произвольного слова 𝑋 рассмотрим все его начала, одновре- менно являющиеся его концами, и выберем из них самое длинное. (Не считая, конечно, самого слова 𝑋.) Будем обозначать его 𝑙(𝑋). Примеры: 𝑙(aba) = a, 𝑙(abab) = ab, 𝑙(ababa) = aba, 𝑙(abc) = пустое слово. 10.3.1. Докажите, что все слова 𝑙(𝑋), 𝑙(𝑙(𝑋)), 𝑙(𝑙(𝑙(𝑋))) и т. д. явля- ются началами слова 𝑋. Решение. Каждое из них (согласно определению) является началом предыдущего. По той же причине все они являются концами слова 𝑋. 10.3.2. Докажите, что последовательность предыдущей задачи об- рывается (на пустом слове). Решение. Каждое слово короче предыдущего. 10.3.3. Докажите, что любое слово, одновременно являющееся нача- лом и концом слова 𝑋 (кроме самого 𝑋) входит в последовательность 𝑙(𝑋), 𝑙(𝑙(𝑋)), . . . Решение. Пусть слово 𝑌 есть одновременно начало и конец 𝑋. Слово 𝑙(𝑋) | самое длинное из таких слов, так что 𝑌 не длиннее 𝑙(𝑋). Оба эти слова являются началами 𝑋, поэтому более короткое из них является началом более длинного: 𝑌 есть начало 𝑙(𝑋). Аналогично, 𝑌 есть конец 𝑙(𝑋). Рассуждая по индукции, можно предполагать, что утверждение задачи верно для всех слов короче 𝑋, в частности, для слова 𝑙(𝑋). Так что слово 𝑌 , являющееся концом и началом 𝑙(𝑋), либо равно 𝑙(𝑋), либо входит в последовательность 𝑙(𝑙(𝑋)), 𝑙(𝑙(𝑙(𝑋))),. . . , что и требовалось доказать. 10.4. Алгоритм Кнута { Морриса { Пратта Алгоритм Кнута { Морриса { Пратта (КМП) получает на вход слово X = x[1]x[2] . . . x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1] . . . l[n], где l[i] = длина слова 𝑙(x[1] . . . x[i]) 184 10. Сопоставление с образцом (функция 𝑙 определена в предыдущем пункте). Словами: l[i] есть дли- на наибольшего начала слова x[1] . . . x[i], одновременно являющегося его концом. 10.4.1. Какое отношение всё это имеет к поиску подслова? Други- ми словами, как использовать алгоритм КМП для определения того, |