А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
8.2.5. Что изменится, если требуется не печатать вершины двоич- ного дерева, а подсчитать их количество? Решение. Печатание вершины следует заменить прибавлением еди- ницы к счётчику. Другими словами, инвариант таков: (общее число вершин) = (счётчик) + (сумма чисел вершин в поддеревьях, корни ко- торых лежат в стеке). 8.2.6. Для некоторых из шести возможных порядков возможны уп- рощения, делающие ненужным хранение в стеке элементов двух видов. Укажите некоторые из них. Решение. Если требуемый порядок таков: корень, левое поддерево, правое поддерево, то заказ на печатание корня можно не закладывать в стек, а выполнять сразу. Несколько более сложная конструкция применима для порядка левое поддерево, корень, правое поддерево. В этом случае все заказы в стеке, кроме самого первого (напечатать поддерево) делятся на пары: напечатать вершину x, напечатать «правое поддерево» x (= поддерево с корнем в правом сыне x). Объединив эти пары в за- казы специального вида и введя переменную для отдельного хранения первого заказа, мы обойдёмся стеком однотипных заказов. То же самое, разумеется, верно, если поменять местами левое и пра- вое | получается ещё два порядка. Замечание. Другую программу печати всех вершин дерева можно построить на основе программы обхода дерева, разобранной в главе 3 Там используется команда «вниз». Поскольку теперешнее представле- ние дерева с помощью массивов l и r не позволяет найти предка задан- ной вершины, придётся хранить список всех вершин на пути от корня к текущей вершине. См. также главу 9 8.3. Более сложные случаи рекурсии 143 8.2.7. Напишите нерекурсивный вариант программы быстрой сор- тировки (см. с. 132 ). Как обойтись стеком, глубина которого ограни- чена 𝐶 log 𝑛, где 𝑛 | число сортируемых элементов? Решение. В стек кладутся пары ⟨𝑖, 𝑗⟩, интерпретируемые как от- ложенные задания на сортировку соответствующих участков массива. Все эти заказы не пересекаются, поэтому размер стека не может превы- сить 𝑛. Чтобы ограничиться стеком логарифмической глубины, будем придерживаться такого правила: глубже в стек помещать больший из возникающих двух заказов. Пусть 𝑓(𝑛) | максимальная глубина сте- ка, которая может встретиться при сортировке массива из не более чем 𝑛 элементов таким способом. Оценим 𝑓(𝑛) сверху таким способом: после разбиения массива на два участка мы сначала сортируем более короткий (храня в стеке более длинный про запас), при этом глубина стека не больше 𝑓(𝑛/2) + 1, затем сортируем более длинный, так что 𝑓(𝑛) 6 max(𝑓(𝑛/2) + 1, 𝑓(𝑛 − 1)), откуда очевидной индукцией получаем 𝑓(𝑛) = 𝑂(log 𝑛). 8.3. Более сложные случаи рекурсии Пусть функция 𝑓 с натуральными аргументами и значениями опре- делена рекурсивно условиями 𝑓(0) = 𝑎, 𝑓(𝑥) = ℎ(𝑥, 𝑓(𝑙(𝑥))) (𝑥 > 0) где 𝑎 | некоторое число, а ℎ и 𝑙 | известные функции. Другими слова- ми, значение функции 𝑓 в точке 𝑥 выражается через значение 𝑓 в точке 𝑙(𝑥). При этом предполагается, что для любого 𝑥 в последовательности 𝑥, 𝑙(𝑥), 𝑙(𝑙(𝑥)), . . . рано или поздно встретится 0. Если дополнительно известно, что 𝑙(𝑥) < 𝑥 для всех 𝑥, то вычисле- ние 𝑓 не представляет труда: вычисляем последовательно 𝑓(0), 𝑓(1), 𝑓(2), . . . 8.3.1. Напишите нерекурсивную программу вычисления 𝑓 для об- щего случая. Решение. Для вычисления 𝑓(𝑥) вычисляем последовательность 𝑙(𝑥), 𝑙(𝑙(𝑥)), 𝑙(𝑙(𝑙(𝑥))), . . . 144 8. Как обойтись без рекурсии до появления нуля и запоминаем её, а затем вычисляем значения 𝑓 в точ- ках этой последовательности, идя справа налево. Ещё более сложный случай из следующей задачи вряд ли встретит- ся на практике (а если и встретится, то проще рекурсию не устранять, а оставить). Но тем не менее: пусть функция 𝑓 с натуральными аргу- ментами и значениями определяется соотношениями 𝑓(0) = 𝑎, 𝑓(𝑥) = ℎ(𝑥, 𝑓(𝑙(𝑥)), 𝑓(𝑟(𝑥))) (𝑥 > 0), где 𝑎 | некоторое число, а 𝑙, 𝑟 и ℎ | известные функции. Предпола- гается, что если взять произвольное число и начать применять к нему функции 𝑙 и 𝑟 в произвольном порядке, то рано или поздно получится 0. 8.3.2. Напишите нерекурсивную программу вычисления 𝑓. Решение. Можно было бы сначала построить дерево, у которого в корне находится 𝑥, а в сыновьях вершины 𝑖 стоят 𝑙(𝑖) и 𝑟(𝑖) | если только 𝑖 не равно нулю. Затем вычислять значения функции, идя от листьев к корню. Однако есть и другой способ. Обратной польской записью (или постфиксной записью) выраже- ния называют запись, где знак функции стоит после всех её аргументов, а скобки не используются. Вот несколько примеров: 𝑓(2) 2 𝑓 𝑓(𝑔(2)) 2 𝑔 𝑓 𝑠(2, 𝑡(7)) 2 7 𝑡 𝑠 𝑠(2, 𝑢(2, 𝑠(5, 3)) 2 2 5 3 𝑠 𝑢 𝑠 Постфиксная запись выражения позволяет удобно вычислять его с по- мощью стекового калькулятора. Этот калькулятор имеет стек, кото- рый мы будем представлять себе расположенным горизонтально (числа вынимаются и кладутся справа), и клавиши | числовые и функцио- нальные. При нажатии на клавишу с числом это число кладётся в стек. При нажатии на функциональную клавишу соответствующая функция применяется к нескольким аргументам у вершины стека. Например, если в стеке были числа 2 3 4 5 6 и нажата функциональная клавиша 𝑠, соответствующая функции от двух аргументов, то в стеке окажутся числа 2 3 4 𝑠(5, 6). 8.3. Более сложные случаи рекурсии 145 Перейдём теперь к нашей задаче. В процессе вычисления значения функции 𝑓 мы будем работать со стеком чисел, а также с последова- тельностью чисел и символов f, l, r, h, которую мы будем интерпре- тировать как последовательность нажатий клавиш на стековом каль- куляторе. Инвариант такой: если стек чисел представляет собой текущее состояние сте- кового калькулятора, то после нажатия всех клавиш после- довательности в стеке останется единственное число, и оно будет искомым ответом. Пусть нам требуется вычислить значение 𝑓(𝑥). Тогда вначале мы по- мещаем в стек число 𝑥, а последовательность содержит единственный символ f. (При этом инвариант соблюдается.) Далее с последователь- ностью и стеком выполняются такие преобразования: старый старая новый новая стек последовательность стек последовательность 𝑋 𝑥 𝑃 𝑋 𝑥 𝑃 𝑋 𝑥 l 𝑃 𝑋 𝑙(𝑥) 𝑃 𝑋 𝑥 r 𝑃 𝑋 𝑟(𝑥) 𝑃 𝑋 𝑥 𝑦 𝑧 h 𝑃 𝑋 ℎ(𝑥, 𝑦, 𝑧) 𝑃 𝑋 0 f 𝑃 𝑋 𝑎 𝑃 𝑋 𝑥 f 𝑃 𝑋 𝑥 𝑥 l f 𝑥 r f h 𝑃 Здесь 𝑥, 𝑦, 𝑧 | числа, 𝑋 | последовательность чисел, 𝑃 | последова- тельность чисел и символов f, l, r, h. В последней строке предполага- ется, что 𝑥 ̸= 0. Эта строка соответствует равенству 𝑓(𝑥) = ℎ(𝑥, 𝑓(𝑙(𝑥)), 𝑓(𝑟(𝑥))). Преобразования выполняются, пока последовательность не станет пу- ста. В этот момент в стеке окажется единственное число, которое и бу- дет ответом. Замечание. Последовательность по существу представляет собой стек отложенных заданий (вершина которого находится слева). 9. РАЗНЫЕ АЛГОРИТМЫ НА ГРАФАХ 9.1. Кратчайшие пути В этом разделе рассматриваются различные варианты одной задач. Пусть имеется n городов, пронумерованных числами от 1 до n. Для ка- ждой пары городов с номерами i, j в таблице a[i][j] хранится целое число | цена прямого авиабилета из города i в город j. Считается, что рейсы существуют между любыми городами, a[i][i] = 0 при всех i, a[i][j] может отличаться от a[j][i]. Наименьшей стоимостью про- езда из i в j считается минимально возможная сумма цен билетов для маршрутов (в том числе с пересадками), ведущих из i в j. (Она не превосходит a[i][j], но может быть меньше.) В предлагаемых ниже задачах требуется найти наименьшую стои- мость проезда для некоторых пар городов при тех или иных ограниче- ниях на массив a и на время работы алгоритма. 9.1.1. Предположим, что не существует замкнутых маршрутов, для которых сумма цен отрицательна. Докажите, что в этом случае марш- рут с наименьшей стоимостью существует. Решение. Маршрут длиной больше n всегда содержит цикл, поэто- му минимум можно искать среди маршрутов длиной не более n, а их конечное число. Во всех следующих задачах предполагается, что это условие (отсут- ствие циклов с отрицательной суммой) выполнено. 9.1.2. Найдите наименьшую стоимость проезда из 1-го города во все остальные за время 𝑂(n 3 ). Решение. Обозначим через МинСт(1,s,k) наименьшую стоимость проезда из 1 в s менее чем с k пересадками. Тогда выполняется та- 9.1. Кратчайшие пути 147 кое соотношение: МинСт(1, s, k+1) = min (︁МинСт(1,s,k), min i=1..n МинСт(1,i,k) + a[i][s]) )︁ Как отмечалось выше, искомым ответом является МинСт(1,i,n) для всех i = 1 . . . n. k:= 1; for i := 1 to n do begin x[i] := a[1][i]; end; {инвариант: x[i] = МинСт(1,i,k)} while k <> n do begin for s := 1 to n do begin y[s] := x[s]; for i := 1 to n do begin if y[s] > x[i]+a[i][s] then begin y[s] := x[i]+a[i][s]; end; end {y[s] = МинСт(1,s,k+1)} end; for i := 1 to n do begin x[s] := y[s]; end; k := k + 1; end; Приведённый алгоритм называют алгоритмом динамического про- граммирования, или алгоритмом Форда { Беллмана. 9.1.3. Докажите, что программа останется правильной, если не за- водить массива y, а производить изменения в самом массиве x (заменив в программе все вхождения буквы y на x и затем удалить ставшие лиш- ними строки). Решение. Инвариант будет таков: МинСт(1,i,n) 6 x[i] 6 МинСт(1,i,k). Этот алгоритм может быть улучшен в двух отношениях: можно за то же время 𝑂(n 3 ) найти наименьшую стоимость проезда i → j для всех пар i, j (а не только при i = 1), а можно сократить время работы до 𝑂(n 2 ). Правда, в последнем случае нам потребуется, чтобы все цены a[i][j] были неотрицательны. 9.1.4. Найдите наименьшую стоимость проезда i → j для всех i, j за время 𝑂(n 3 ). 148 9. Разные алгоритмы на графах Решение. Для k = 0 . . . n через A(i,j,k) обозначим наименьшую сто- имость маршрута из i в j, если в качестве пересадочных разрешено использовать только пункты с номерами не больше k. Тогда A(i,j,0) = a[i][j], A(i,j,k+1) = min(︀A(i,j,k), A(i,k+1,k) + A(k+1,j,k))︀ (два варианта соответствуют неиспользованию и использованию пунк- та k+1 в качестве пересадочного; отметим, что в нём незачем бывать более одного раза). Этот алгоритм называют алгоритмом Флойда. 9.1.5. Как проверить за 𝑂(n 3 ) действий, имеет ли граф с n верши- нами циклы с отрицательной суммой? [Указание. Можно применять алгоритм Флойда, причём разрешать i = j в A(i,j,k), пока не появится первый отрицательный цикл.] 9.1.6. Имеется 𝑛 валют и таблица обменных курсов (сколько фло- ринов дают за талер и т.п.). Коммерсант хочет неограниченно обога- титься, обменивая свой начальный капитал туда-сюда по этим курсам. Как проверить, возможно ли это? [Указание. После логарифмирования деньги уподобляются расстоя- ниям.] 9.1.7. Известно, что все цены неотрицательны. Найдите наимень- шую стоимость проезда 1 → i для всех i = 1 . . . n за время 𝑂(n 2 ). Решение. В процессе работы алгоритма некоторые города будут выделенными (в начале | только город 1, в конце | все). При этом: ∙ для каждого выделенного города i хранится наименьшая стои- мость пути 1 → i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города; ∙ для каждого невыделенного города i хранится наименьшая стои- мость пути 1 → i, в котором в качестве промежуточных исполь- зуются только выделенные города. Множество выделенных городов расширяется на основании следую- щего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истин- ной наименьшей стоимостью. В самом деле, пусть есть более короткий 9.1. Кратчайшие пути 149 путь. Рассмотрим первый невыделенный город на этом пути | уже до него путь длиннее! (Здесь существенна неотрицательность цен.) Добавив выбранный город к выделенным, мы должны скорректи- ровать информацию, хранимую для невыделенных городов. При этом достаточно учесть лишь пути, в которых новый город является послед- ним пунктом пересадки, а это легко сделать, так как минимальную стоимость проезда в новый город мы уже знаем. При самом бесхитростном способе хранения множества выделенных городов (в булевском векторе) добавление одного города к числу вы- деленных требует времени 𝑂(n). Этот алгоритм называют алгоритмом Дейкстры. 9.1.8. Имеется 𝑛 городов, соединённых дорогами (с односторонним движением). Для любых городов 𝑖, 𝑗 известен максимальный вес груза, который можно везти из 𝑖 в 𝑗 (грузоподъёмность дороги). Найдите за время 𝑂(𝑛 2 ) для всех городов максимальный вес груза, который в них можно привезти из столицы. [Указание. Действуйте аналогично алгоритму Дейкстры, заменив сумму на максимум.] Отыскание кратчайшего пути имеет естественную интерпретацию в терминах матриц. Пусть 𝐴 | матрица цен одной авиакомпании, а 𝐵 | матрица цен другой. Пусть мы хотим лететь с одной пересад- кой, причём сначала самолётом компании 𝐴, а затем | компании 𝐵. Сколько нам придётся заплатить, чтобы попасть из города i в город j? 9.1.9. Докажите, что эта матрица вычисляется по обычной формуле для произведения матриц, только вместо суммы надо брать минимум, а вместо умножения | сумму. 9.1.10. Докажите, что таким образом определённое произведение матриц ассоциативно. 9.1.11. Докажите, что задача о кратчайших путях эквивалентна вы- числению 𝐴 ∞ для матрицы цен 𝐴: в последовательности 𝐴, 𝐴 2 , 𝐴 3 , . . . все элементы, начиная с некоторого, равны искомой матрице стоимо- стей кратчайших путей. (Если нет отрицательных циклов!) 9.1.12. Начиная с какого элемента можно гарантировать равенство в предыдущей задаче? Обычное (не модифицированное) умножение матриц тоже может оказаться полезным, только матрицы должны быть другие. Пусть есть 150 9. Разные алгоритмы на графах не все рейсы (как раньше), а только некоторые, a[i][j] равно 1, если рейс есть, и 0, если рейса нет. Возведём матрицу a (обычным образом) в степень k и посмотрим на её (i-j)-й элемент. 9.1.13. Чему он равен? Ответ. Числу различных способов попасть из i в j за k рейсов (с k-1 пересадками). При описании кратчайших путей случай, когда есть не все рейсы, можно свести к исходному, введя фиктивные рейсы с бесконечно боль- шой (или достаточно большой) стоимостью. Тем не менее возникает такой вопрос. Число реальных рейсов может быть существенно мень- ше 𝑛 2 , поэтому интересны алгоритмы, которые работают эффективно в такой ситуации. Исходные данные естественно представлять тогда в такой форме: для каждого города известно число выходящих из него рейсов, их пункты назначения и цены. 9.1.14. Докажите, что алгоритм Дейкстры можно модифицировать так, чтобы для 𝑛 городов и 𝑚 рейсов (всего) он требовал не более 𝐶(𝑛 + 𝑚) log 𝑛 операций. [Указание. Что надо сделать на каждом шаге? Выбрать невыделен- ный город с минимальной стоимостью и скорректировать цены для всех городов, в которые из него есть маршруты. Если бы кто-то сообщал нам, для какого города стоимость минимальна, то хватило бы 𝐶(𝑛 + 𝑚) действий. А поддержание сведений о том, какой элемент в массиве ми- нимален (см. задачу на с. 115 ) обходится ещё в множитель log 𝑛.] Иногда нам нужны не все города. Пусть, скажем, в графе дорог нужно найти кратчайший путь между двумя близкими посёлками | тогда города и дороги в другой части страны нас явно не интересуют. С точки зрения алгоритма, если нас интересует расстояние от i до j, то алгоритм Дейкстры, вычисляющий расстояния от i до всех городов, можно остановить, как только город j станет выделенным. 9.1.15. Покажите, что в этот момент выделенными могут быть то- лько города, которые не дальше от i, чем j. [Указание. Для невыделенного города с минимальной стоимостью расстояние до него равно его стоимости, а для любого другого невы- деленного города 𝑢 расстояние не меньше (сравним с расстоянием до первого невыделенного города на кратчайшем пути в 𝑢).] Если мы (как это часто делают на практике) храним отдельно вы- деленные города (как множество, см. главы 13 и 14 ), а также невы- деленные города конечной стоимости (множество плюс приоритетная 9.1. Кратчайшие пути 151 очередь, с. 115 ), предыдущая задача ограничивает количество храни- мых городов: это города, отстоящие от i не больше, чем город j, а также все их соседи. Такой способ хранения полезен, если граф задан неявно | скажем, если мы ищем кратчайший путь из одной позиции какой-то головоломки в другую. (При реализации алгоритма Дейкстры от приоритетной очереди, помимо взятия наименьшего элемента, пона- добится операция увеличения приоритета элемента, но её тоже легко реализовать при способе хранения, описанном в задаче 6.4.2 .) Предыдущие замечания особенно полезны в сочетании с методом потенциалов. Пусть есть некоторая функция 𝜙 на вершинах графа, называемая потенциалом. Изменим длины всех рёбер графа, прибавив в длине ребра из 𝑢 в 𝑣 величину 𝜙(𝑣) − 𝜙(𝑢). 9.1.16. Докажите, что при таком изменении графа кратчайшие пу- ти сохранятся (кратчайший путь из одной вершины в другую останется кратчайшим), но их длины изменятся: к длине кратчайшего пути из 𝑝 в 𝑞 прибавится 𝜙(𝑞) − 𝜙(𝑝). [Указание. К длине любого пути из 𝑝 в 𝑞 прибавится как раз та же самая разность 𝜙(𝑞) − 𝜙(𝑝) (при сложении добавок к длинам рёбер все промежуточные члены сократятся).] Эта задача вместе с предыдущими используется в алгоритме, на- зываемом 𝐴 * -поиском.. Пусть нам надо найти кратчайшее расстояние от i до j. Возьмём в качестве потенциала некоторую эвристическую оценку расстояния до j. Тогда рёбра, идущие в сторону уменьшения этой оценки, станут короче, и поэтому алгоритм будет рассматривать их в первую очередь. Нужно только, чтобы длина всех рёбер остава- лась неотрицательной, то есть чтобы длина ребра 𝑢𝑣 была не меньше 𝜙(𝑢) − 𝜙(𝑣). 9.1.17. Покажите, что если это свойство выполнено, то эвристиче- ская оценка расстояния будет (гарантированно) нижней оценкой. [Указание. Как она меняется вдоль кратчайшего пути?] 9.1.18. Пусть рёбра в графе | это дороги, а их длина измеряет- ся вдоль дороги. Что тогда можно выбрать в качестве такой нижней оценки? Ответ. Геометрическое расстояние (по поверхности Земли) до j. 152 9. Разные алгоритмы на графах 9.2. Связные компоненты, поиск в глубину и ширину Наиболее простой случай задачи о кратчайших путях | если все цены равны 0 или +∞. Другими словами, мы интересуемся возможно- стью попасть из 𝑖 в 𝑗, но за ценой не постоим. В других терминах: мы имеем ориентированный граф (картинку из точек, некоторые из кото- рых соединены стрелками) и нас интересуют вершины, доступные из данной. Для этого случая задачи о кратчайших путях приведённые в пре- дыдущем разделе алгоритмы | не наилучшие. В самом деле, более бы- страя рекурсивная программа решения этой задачи приведена в главе 7 , а нерекурсивная | в главе 6 . Сейчас нас интересует такая задача: не просто перечислить все вершины, доступные из данной, но перечислить их в определённом порядке. Два популярных случая | поиск в ширину и в глубину. Поиск в ширину. Надо перечислить все вершины ориентированного графа, доступ- ные из данной, в порядке увеличения длины пути от неё. (Тем самым мы решим задачу о кратчайших путях, когда цены рёбер равны 1 или +∞.) 9.2.1. Придумайте алгоритм решения этой задачи с числом дей- ствий не более 𝐶 · (число рёбер, выходящих из интересующих нас вер- шин). Решение. Эта задача рассматривалась в главе 6 , с. 114 . Здесь мы приведём подробное решение. Пусть num[i] | количество рёбер, вы- ходящих из i, out[i][1], . . . , out[i][num[i]] | вершины, куда ведут рёбра. Вот программа, приведённая ранее: procedure Доступные (i: integer); {напечатать все вершины, доступные из i, включая i} var X: подмножество 1..n; P: подмножество 1..n; q, v, w: 1..n; k: integer; begin ...сделать X, P пустыми; writeln (i); ...добавить i к X, P; {(1) P = множество напечатанных вершин; P содержит i; (2) напечатаны только доступные из i вершины; 9.2. Связные компоненты, поиск в глубину и ширину 153 (3) X - подмножество P; (4) все напечатанные вершины, из которых выходит ребро в ненапечатанную вершину, принадлежат X} while X непусто do begin ...взять какой-нибудь элемент X в v; for k := 1 to num [v] do begin w := out [v][k]; if w не принадлежит P then begin writeln (w); добавить w в P; добавить w в X; end; end; end; end; Тогда нам было безразлично, какой именно элемент множества X вы- бирается. Если мы будем считать X очередью (первым пришёл | пер- вым ушёл), то эта программа напечатает все вершины, доступные из i, в порядке возрастания их расстояния от i (числа рёбер на кратчайшем пути из i). Докажем это. Обозначим через 𝑉 (𝑘) множество всех вершин, расстояние которых от i (в описанном смысле) равно 𝑘. Имеет место такое соотношение: 𝑉 (𝑘 + 1) = (концы рёбер с началами в 𝑉 (𝑘)) ∖ (𝑉 (0) ∪ . . . ∪ 𝑉 (𝑘)) Докажем, что для любого 𝑘 = 0, 1, 2 . . . в ходе работы программы будет такой момент (после очередной итерации цикла while), когда в очереди стоят все элементы 𝑉 (𝑘) и только они; напечатаны все элементы 𝑉 (0), . . . , 𝑉 (𝑘). (Для 𝑘 = 0 это будет состояние перед циклом.) Рассуждая по индукции, предположим, что в очереди скопились все элементы 𝑉 (𝑘). Они будут просматриваться в цикле, пока не кончатся (поскольку новые элемен- ты добавляются в конец, они не перемешаются со старыми). Концы ведущих из них рёбер, если они уже не напечатаны, печатаются и ста- вятся в очередь | то есть всё как в записанном выше соотношении для 𝑉 (𝑘 + 1). Так что когда все старые элементы кончатся, в очереди будут стоять все элементы 𝑉 (𝑘 + 1). Поиск в глубину. Рассматривая поиск в глубину, удобно представлять себе ориенти- рованный граф как образ дерева. Более точно, пусть есть ориентиро- ванный граф, одна из вершин которого выделена. Будем предполагать, 154 9. Разные алгоритмы на графах что все вершины доступны из выделенной по ориентированным путям. Построим дерево, которое можно было бы назвать «универсальным на- крытием» нашего графа. Его корнем будет выделенная вершина графа. Из корня выходят те же стрелки, что и в графе | их концы будут сы- новьями корня. Из них в дереве выходят те же стрелки, что и в графе и так далее. Разница между графом и деревом в том, что пути в гра- фе, ведущие в одну и ту же вершину, в дереве «расклеены». В других терминах: вершина дерева | это путь в графе, выходящий из корня. Её сыновья | это пути, продолженные на одно ребро. Заметим, что дерево бесконечно, если в графе есть ориентированные циклы. Имеется естественное отображение дерева в граф (вершин в вер- шины). При этом каждая вершина графа имеет столько прообразов, сколько путей в неё ведёт. Поэтому обход дерева (посещение его вершин в том или ином порядке) одновременно является и обходом графа | только каждая вершина посещается многократно. Будем предполагать, что для каждой вершины графа выходящие из неё рёбра упорядочены (например, пронумерованы). Тем самым для каждой вершины дерева выходящие из неё рёбра также упорядочены. Будем обходить дерево так: сначала корень, а потом поддеревья (в по- рядке ведущих в них рёбер). Такой обход дерева рассматривался нами в главе 7 . Ему соответствует обход графа. Если выкинуть из этого об- хода повторные посещения уже посещённых вершин, то получится то, что называется «поиск в глубину». Другими словами, на путях, выходящих из выделенной вершины, введём порядок: путь предшествует своему продолжению; если два пу- ти расходятся в некоторой вершине, то меньшим считается тот, кото- рый выходит из неё по меньшему ребру. Вершины теперь упорядочива- ются в соответствии с минимальными путями, в них ведущими. Обход вершин графа в указанном порядке называется поиском в глубину. 9.2.2. Напишите программу поиска в глубину. [Указание. Возьмём программу обхода дерева (корень → левое под- дерево → правое поддерево) из главы 7 или из главы 8 и используем её применительно к обстоятельствам. Главное изменение: не надо по- сещать вершины повторно. Так что если мы попали в уже посещённую вершину, то можно с ней ничего не делать. (Если путь не минимален среди ведущих в данную вершину, то и все его продолжения не мини- мальны | их просматривать не надо).] Замечание. Напомним, что в главе 8 упоминались две возможности устранения рекурсии в программе обхода дерева (с. 142 ). Оба варианта можно использовать для поиска в глубину. 9.2. Связные компоненты, поиск в глубину и ширину 155 Поиск в глубину лежит в основе многих алгоритмов на графах, по- рой в несколько модифицированном виде. 9.2.3. Неориентированный граф называется двудольным, если его вершины можно раскрасить в два цвета так, что концы любого ребра | разного цвета. Составьте алгоритм проверки, является ли заданный граф двудольным, в котором число действий не превосходит 𝐶 · (число рёбер + число вершин). [Указание. (а) Каждую связную компоненту можно раскрашивать отдельно. (б) Выбрав цвет одной вершины и обходя её связную компо- ненту, мы определяем единственно возможный цвет остальных.] Замечание. В этой задаче безразлично, производить поиск в ширину или в глубину. 9.2.4. Составьте нерекурсивный алгоритм топологической сорти- ровки ориентированного графа без циклов. (Рекурсивный алгоритм см. на с. 128 .) Решение. Предположим, что граф имеет вершины с номерами 1 . . . n, для каждой вершины i известно число num[i] выходящих из неё рёбер и номера вершин dest[i][1], . . . , dest[i][num[i]], в которые эти рё- бра ведут. Будем условно считать, что рёбра перечислены «слева напра- во»: левее то ребро, у которого номер меньше. Нам надо напечатать все вершины в таком порядке, чтобы конец любого ребра был напечатан перед его началом. Мы предполагаем, что в графе нет ориентирован- ных циклов | иначе такое невозможно. Для начала добавим к графу вершину 0, из которой рёбра ведут в вершины 1, . . . , n. Если её удастся напечатать с соблюдением правил, то тем самым все вершины будут напечатаны. Алгоритм хранит путь, выходящий из нулевой вершины и идущий по рёбрам графа. Переменная l отводится для длины этого пути. Путь образован вершинами vert[1] . . . vert[l] и рёбрами, имеющими номе- ра edge[1] . . . edge[l]. Номер edge[s] относится к нумерации рёбер, выходящих из вершины vert[s]. Тем самым для всех s должны выпол- няться неравенство edge[s] 6 num[vert[s]] и равенство vert[s+1] = dest [vert[s]] [edge[s]]. Заметим, что конец последнего ребра нашего пути (то есть вершина dest[vert[l]][edge[l]], не включается в массив vert. Кроме того, 156 9. Разные алгоритмы на графах для последнего ребра мы делаем исключение, разрешая ему указывать «в пустоту», т. е. разрешаем edge[l] равняться num[vert[l]]+1. В процессе работы алгоритм будет печатать номера вершин, при этом соблюдая требование «вершина напечатана только после тех вер- шин, в которые из неё ведут рёбра». Кроме того, будет выполняться такое требование (И): вершины пути, кроме последней (vert[1] . . . vert[l]) не на- печатаны, но свернув с пути налево, мы немедленно упира- емся в напечатанную вершину. Вот что получается: l:=1; vert[1]:=0; edge[1]:=1; while not( (l=1) and (edge[1]=n+1)) do begin if edge[l]=num[vert[l]]+1 then begin {путь кончается в пустоте, поэтому все вершины, следующие за vert[l], напечатаны - можно печатать vert[l]} writeln (vert[l]); l:=l-1; edge[l]:=edge[l]+1; end else begin {edge[l] <= num[vert[l]], путь кончается в вершине} lastvert:= dest[vert[l]][edge[l]]; {последняя} if lastvert напечатана then begin edge[l]:=edge[l]+1; end else begin l:=l+1; vert[l]:=lastvert; edge[l]:=1; end; end; end; {путь сразу же ведёт в пустоту, поэтому все вершины левее, то есть 1..n, напечатаны} 9.2.5. Докажите, что если в графе нет циклов, то этот алгоритм заканчивает работу. Решение. Пусть это не так. Каждая вершина может печататься то- лько один раз, так что с некоторого момента вершины не печатаются. В графе без циклов длина пути ограничена (вершина не может входить в путь дважды), поэтому подождав ещё, мы можем дождаться момен- та, после которого путь не удлиняется. После этого может разве что увеличиваться edge[l] | но и это не беспредельно. 9.3. Сети, потоки и разрезы 157 Тем самым мы построили искомый нерекурсивный алгоритм топо- логической сортировки графа. 9.2.6. Докажите, что время работы этого алгоритма не превосхо- дит 𝑂(число вершин + число рёбер). 9.2.7. Как модифицировать алгоритм так, чтобы он отыскивал один из циклов, если таковые имеются, и производил топологическую сортировку, если циклов нет? 9.3. Сети, потоки и разрезы В этом разделе мы разберём алгоритм для решения ещё одного типа задач, связанных с графами. 9.3.1. В пункте 𝐴 добывают нефть, а в пункте 𝐵 её перерабатыва- ют. Доставка от добычи до переработки происходит по трубам. Около каждой трубы показана её пропускная способность: сколько единиц нефти можно по ней прокачать за единицу времени. Какое максималь- ное количество нефти можно доставить из 𝐴 в 𝐵 за единицу времени и как это сделать? 𝐴 𝐵 6 4 4 6 1 Решение. Сразу же ясно, что больше 10 из 𝐴 не вывезти (потому что есть только трубы 4 и 6), да и в 𝐵 не доставить по той же причине. Но даже и 10 не получится: пришедшие по верхней трубе 6 единиц некуда девать (максимум можно отправить 5 = 4 + 1). Но 9 единиц пропустить по сети можно: 𝐴 𝐵 5[6] 4[4] 4[4] 5[6] 1[1] Около каждой трубы указано направление потока и его величина (в квадратных скобках | максимально возможная величина). 158 9. Разные алгоритмы на графах Легко поверить, что это наилучший вариант и что больше 9 единиц пропустить по сети нельзя, но если кто сомневается, можно объяснить это так. Проведём в сети границу (пунктирная линия на рисунке), раз- деляющую 𝐴 и 𝐵. 𝐴 𝐵 4 4 1 9.3. Сети, потоки и разрезы 159 Через неё ведут трубы пропускной способности 4, 1, 4, в сумме 9, так что больше не получится. В этом разделе мы увидим, что примерно так же обстоит дело и в общем случае: в любой сети максимально возможный поток ограничен минимальным разрезом той же величины, и разберём один (самый пер- вый и самый простой) алгоритм поиска этого потока и этого разреза. Но прежде чем это всё точно сформулировать и доказать, надо до- говориться об обозначениях. В нашем примере трубы были «неориенти- рованные» | они могли работать в обе стороны, и пропускные способ- ности туда и сюда были одинаковые. Но это не обязательно: будем счи- тать, что по трубе из узла 𝑖 в узел 𝑗 можно прокачивать 𝑐[𝑖, 𝑗] единиц, а в обратную сторону 𝑐[𝑗, 𝑖] единиц, и эти границы в принципе могут быть разными (например, для односторонней трубы одно из этих чи- сел равно нулю). Мы предполагаем, что узлы сети (= вершины графа) пронумерованы от 1 до 𝑛, так что 𝑐 будет двумерным массивом чисел. Эти обозначения вызывают несколько естественных вопросов: ∙ Чему равно 𝑐[𝑖, 𝑗], если из 𝑖 в 𝑗 нет трубы? Ответ: отсутствующая труба | всё равно что труба с нулевой пропускной способностью, так что мы полагаем 𝑐[𝑖, 𝑗] = 𝑐[𝑗, 𝑖] = 0 в этом случае. (При оценке времени работы алгоритма нам будет важно, какие рёбра есть, а каких нет, но пока что можно считать так.) ∙ А если из 𝑖 в 𝑗 ведут две трубы? Ответ: такое не разрешается, но это не важно, потому что несколько труб можно всегда заменить одной, сложив их пропускные способности. ∙ Чему равны 𝑐[𝑖, 𝑖]? Ответ: не имеет значения, но можно считать, что 𝑐[𝑖, 𝑖] = 0. Массив 𝑐[𝑖, 𝑗] задаёт сеть (по-английски network), значение 𝑐[𝑖, 𝑗] называют пропускной способностью (capacity) трубы из 𝑖 в 𝑗. Теперь надо договориться, как мы будем представлять и хранить в алгоритме поток (Ӏow) в этой сети, то есть схему транспортировки. Тут полезна маленькая хитрость: поток из 𝑗 в 𝑖 мы будем считать потоком из 𝑖 в 𝑗, но с противоположным знаком. Другими словами, мы будем рассматри- вать массив 𝑓[𝑖, 𝑗] того же размера, у которого 𝑓[𝑖, 𝑗] = −𝑓[𝑗, 𝑖] при всех 𝑖, 𝑗 от 1 до 𝑛. Из этого условия следует, что 𝑓[𝑖, 𝑖] = 0 (и это логич- но: нам не нужен поток из вершины в себя). Более формально, пусть фиксированы два разных числа 𝑠 (номер узла-источника) и 𝑡 (номер узла-потребителя). Иногда 𝑠 называют истоком (source), а 𝑡 называют 160 9. Разные алгоритмы на графах стоком (sink). Массив 𝑓 называют потоком в сети 𝑐, если ∙ 𝑓[𝑖, 𝑗] = −𝑓[𝑗, 𝑖] для всех 𝑖, 𝑗 от 1 до 𝑛 (уже обсуждали); ∙ 𝑓[𝑖, 𝑗] 6 𝑐[𝑖, 𝑗] для всех 𝑖, 𝑗 от 1 до 𝑛 (поток по ребру не превышает его пропускной способности); ∙ ∑︀ 𝑛 𝑗=1 𝑓[𝑖, 𝑗] = 0 при всех 𝑖, отличных от 𝑠 и 𝑡. Последнее условие означает, что во всех вершинах, кроме 𝑠 и 𝑡, на- ша условная нефть не добывается и не теряется | сколько приходит, столько и уходит. Заметим, что наши соглашения о знаках позволяют записать это условие, не разделяя входящие и выходящие рёбра, и это удобно. |