Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007, страница 9

Такое разложение для данных з и 1 единственное, если потребовать, чтобы подграфы Ст последовательных сверхребер сами не являлись последовательными сверхребрами, а подграфы С параллельных сверхребер не являлись параллельными сверх1кюрами. Любой последовательно-параллельный граф удобно представить в виде дерева, у которого нег узлов степени 1. Листья дерева представляют ребра, а внутренние узлы — сверхребра, причем последовательные и параллельные сверхребра чередуются сделано для ткъиткиИана1а.огя 40 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 от уровни к уровню. Например, дерево соответствует последовательно-параллельным графам и подграфам а А= я, й= егу, С= ~Я, р —, (54) Ь г Ь с Х т У 1р = 1 для последовательных сверхребер, О в противном случае ("тип'* р); ср —— 1 в случае остовного дерева для р, и О в случае близкого дерева; 1„— указатель на крайнего левого потомка р, или О, если р — лист; гр — указатель на правого "брат" р (по циклу); 4„— указатель на выбранного потомка р, или О, если р — лист.

Если д указывает на крайнего правого потомка р, то его "правый брат" гт равен 1„. И если 4 указывает на щюизеаеьного потомка р, правила 1 и 2 гласят, что е, еслид=дг; ст = 1р, если д ~ с(р. (55) (Например, если р — внутренний узел, представляющий последовательное сверх- ребро„то для всех, кроме одного, потомков р получаем ет = 1; единственным исключением является выбранный потомок 4„. Таким образом„у нас должно быть сделано для итнж1п$апа4а.ого если верхний узел А рассматривать как параллельный.

В (54) поименованы ребра, но не вершины, поскольку именно ребра играют главную роль в остовных деревьях. Скажем, например, что баизкое дерево последовательно-параллельного графа межлу в и 1 представляет собой множество из и — 2 ребер без циклов, которые не соединяют е с 1. Остовные деревья и близкие деревья последовательно-параллельпого графа легко описать рекурсивно следующим образом. 1. Остовное дерево последовательного сверхребра соответствует остовным деревьям всех его главных подграфов С~, близкое дерево соответствует остовным деревьям всех подграфов, кроме одного, у которого используется близкое дерево. 2.

Близкое дерево параллельного сверхребра соответствует близким деревьям всех его главных подграфов С~; остовное дерево соответствует близким деревьям всех подграфов, кроме одного, у которого используется остовное дерево. Правила 1 и 2 наводят на мысль об использовании следующих структур данных для перечисления остовных деревьев и/или близких деревьев последовательно- параллельных графов. Пусть р указывает на узел в дереве наподобие (53), Тогда определим 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБЪЕКТОВ 41 остовное дерево для всех последовательно соединенных подграфов, образующих р, за исключением одного выбранного подграфа, и в этом случае мы имеем для р близкое дерево.) Для заданных выбранных указателей йр и произвольного значения 0 или 1 для ер в корне дерева формула (55) говорит о том, каким образом происходит распространение этих значений вниз по дереву вплоть до листьев. Например, если установить в дереве (53) ел — 1 и выбранным потомком каждого внутреннего узла считать крайний слева (т.е.

Ид =а, Нп = 5, Ис = с и ао = 7), то можно последовательно найти значения: еа = 1 ев — 0 еь = 0 ес = 1~ ес = 1 еэ = О ие = 1 ео = О, еу = О, сэ = 1. (56) Лист д присутствует в остовном дереве тогда и только тогда, когда ц, = 1; следовательно, (56) определяет остовное дерево асей последовательно-параллельного графа ,4 из (54). Для удобства будем говорить, что конфигррецшьмп (сопбу) р являются его остовные деревья, если еэ — — 1, и его близкие деревья, если е„= О.

Мы бы хотели сгенерировать все конфигурации корня. Внутренний узел р называется "простым", если ер —— $р, т,е. последовательный узел прост, если его конфигурациями являются остовные деревья, а параллельный узел прост, если его конфигурациями являются близкие деревья. Если внутренний узел р прост, его конфигурации представляют собой декартово произведение конфигураций его потомков, а именно все независимо изменяющиеся Й-кортежи дочерних конфигураций; выбранный потомок Иг в этом простом случае несущественен.

Однако, если р не является простым, его конфигурации представляют собой объединение таких декартовых Й-кортежей, взятых по всем возможным выборам Йр. Простые узлы относительно редки: простым может быть максимум один потомок узла, не являющегося простым (а именно выбранный потомок), и все потомки простого узла не являются простыми, если только они не листья. Даже при этом представление последовательно-параллельного графа в виде дерева делает рекурсивную генерацию всех его остовных и~или близких деревьев достаточно простой и эффективной. Операции алгоритма 8 — сжатие и восстановление, удаление и его отмена, проверка моста — не требуются при работе с последовательно-параллельными графами.

Более того, в упражнении 90 показано, что имеется красивый способ получить остовные деревья или близкие деревья в порядке кода Грея двери-вертушки, с использованием фокусных указателей, как в некоторых ранее встречавшихся нам алгоритмах. ~Усовершенствования алгоритма В. Хотя алгоритм В предоставляет нам простой и достаточно эффективный способ посещения всех остовных деревьев графа в общем случае, его автор Малькольм Смит (Ма1со!п1 Епп1п) выяснил, что свойства последовательно-параллельных графов позволяют улучшить его. Например, если граф имеет два или более ребер, проходящих между одними и теми же вершинами и и е„их можно скомбинировать в сверхребро; остовные деревья исходного графа в таком случае могут быть получены из этого более простого графа.

А если граф имеет вершину е степени 2, так что с ней связаны только ребра и — е и е — ш, то можно удалить вершину е и заменить указанные ребра одним сверхребром между сделано для вэлк! ВГапаса.ого 42 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 и и гс. Кроме того, можно удалить любую вершину степени 1 вместе с ее ребром, просто включая его в каждое осчовное дерево. Применив описанные приведения к данному графу С, мы получим приведенный граф С, не имеющий параллельных ребер и вершин степени 1 и 2, и множество т > 0 последовательно-параллельных графов Ям..., Я, представляющих ребра (или сверхребра), которые должны быть включены во все остовные деревья С.

Каждое оставшееся ребро и — и графа С фактически соответствует последовательно-параллельному графу Я„, между вершинами и н и. Остовные деревья графа С могут быть получены квк объединение, взятое по всем остовным деревьям Т графа С, декартова произведения остовных деревьев графов Ям..., Я„, и остовпых деревьев всех графов Я„„для ребер и — и в Т, вместе с близкими деревьями всех графов Я„„ для ребер и — с, которые входят в С, но не в Т. Все остовные деревья Т графа С можно получить с использованием стратегии из алгоритма Б.

Фактически прн таком применении алгоритма Б его операции по замене текущего графа С графом С/е или С'1с обычно влекут за собой дальнейшие приведения, если появляются новые параллельные ребра или степень некоторых вершин графа падает ниже 3. Таким образом, это приводит к тому, что "останавливающее состояние" неявной рекурсии алгоритма Б, а именно ситуация, когда остаются только две вершины (шаг 35), в действительности никогда не достигается: приведенный граф С либо состоит из единственной вершины без ребер, либо имеет, как минимум, четыре вершины и шесть ребер.

Производительность алгоритма Б и его улучшенной версии — алгоритма У— можнооценить, рассматривая количествообращений к памяти, выполняемых зтнми алгоритмами прн генерации всех остовных деревьев типичных графов, как показано в табл. 5. Нижняя строка таблицы соответствует графу р(апе ш(1св (16, О, О, 1, О, О, 0) из Бтап1огп СгарЬВаве, который служит "естественным" противоядием для чисто математических примеров в предыдущих строках. Случайный мультиграф в предпоследней строке, также взятый нз Бгап1огб СгарйВвве, более точно можно описать егоофицивльным именем гппйот угарИ(16,37,1,0,0,0,0,0,0,0), Хотятор4х4 изоморфеи четырехмерному кубу (см. упражнение 7.2.1.1-17), зти изоморфные графы дают немного отличающееся времн работы из-за того, что их вершины и ребра алгоритм обходит в разном порядке.

В общем случае алгоритм Я не так уж плох для небольших примеров, за исключением разреженных графов; однако алгоритм У превосходит его при наличии большого количества остовных деревьев. Когда алгоритм У входит в полную силу, на каждое новое дерево он тратит примерно 18 — 19 обращений к памяти. В табл.

5 также указывается, что математически определенные графы часто имеют на удивление "'круглое" количество остовных деревьев, Например, Д.М. Цветкович (В.М. Стегкот14) ~Бгрвкл А(пи(етуа 57аива, Ма1етансйез(п' Ьюс(1п1, 11 (Ве13гаг(е, 1971), 135-14Ц открыл, помимо прочего, что и-мерный куб имеет ровно 2т ъ 11(1)2(2) и( ) (57) остовных деревьев. В упражнениях 104-109 рассматриваются некоторые из причин зтого.

сделано для вьк1ьс! п$апаса.ого 7.2,1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 43 Таблица 5. Рабочее время в обращениях к памяти, необходимое для генерации всех остои- ных деревьев 794,0 473.0 9 974.0 5 063.0 348.0 99.8 3 556.1 105.4 ?5.8 83.5 37.6 18.6 60.0 22.7 9 10 99 100 10 10 100 100 6 4 45 10 25 10 1 1 10 100 16 100 000 000 390 625 794 л 9974 и 3480а 355605 л 1213л 3 759.58 Мн 23.43 Мн 473 л 5063 д 998н 10 538 и 1336 д 1 860.95 Мл 8.88 Мд 24 16 28 16 32 16 32 16 42467З28 З 168.15Мл 82З.О8Мн 42 467 328 3 168,16 Мл 823.38 МН Т4.6 19.4 74,7 19.4 Обобщенный квазнкод Грен. Завершим данный раздел обсуждением еще одного вопроса, совершенно отличного от предыдущих, тем не менее связанного с деревьями, Рассмотрим гибридные варианты двух стандартных способов обхода непустого леса.

Обход в прямо-обратном порядке 1ргервлсагдет~ Посетить корень первого дерева Обход в обратно-прямом порядке (роягргеогдег1 Обойти поддеревья первого дерева в прямо-обратном порядке Посетить корень первого дерева Обойтн поддеревья первого дерева в обратно-прямом порядке Обойтн оставшиеся деревья в прямо-об- Обойти оставшиеся деревья в обратно- ратном порядке прямом порядке В первом случае каждое дерево леса обходится в прямо-обратном порядке, причем первым посещается корень дерева; однако полдеревья этих корней обходятся в обратно-прямом порядке, причем последним посепшется корень. Второй вариант аналогичен, но в нем "'прямой" н "обратный" заменены друг на друга, В общем случае сделано для 5ньлнлп$апаза.оге Путь Рш Путь Рнн Цикл Сш Цикл Снн Полный граф Ка Полный граф Кш Полный диграф Ккэ 4 х 4 решетка Р4 х Р4 5 х 5 решетка Рз х Ре 4 х 4 цилиндр Р4 х С4 5 х 5 цилиндр Р5 хСе 4х4 тор С4 хС4 Четырехмерный куб Ра х Р5 х Рх х Р1 Случайный мультнгреф 16 городов т н К Алгоритм 8 Алгоритм 8' и иа одно дерево 100 352 12.01 МН 1.87 Мл 119,7 18.7 40 25 557 568 000 54 68 Сн 10,20 Сн 98.1 18 3 2 558976 230.96 Ма 49.09 Кл 90.3 19.2 45 25 38 720 000 000 3 165 31 Са 7И.69 Сд 81.7 18.4 37 16 59 933 756 3818.19 Мл 995.91 Мл 63.7 16.6 37 16 1796Т8881 11772.11 ма 326743ма 65.5 18,2 44 КОМБИНАТОРНЫЙ ПОИСК прямо-обратный порядок посещает корни на каждом четном уровне леса первыми, а на нечетном — последними.