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

! Как и в других рассмотренных алгоритмах циклы на шагах 04 и 05 обычно достаточно коротки (см. упражнение 88). В упражнении 90 доказывается, что небольших изменений данного алгоритма достаточно для генерации всех размещений ребер, формирующих свободные деревья. Останные деревья. Теперь рассмотрим минимальные подгрвфы, которые "охватывают" данный граф. Если С вЂ” связный граф нз и вершин, его оспювнммп дереве»ьни (эрашппй ггееэ) являются подмножества из и — 1 ребер, не содержащие циклов; или, что эквивалентно, они представляют собой подмножества ребер„которые сделано для вълк! п$апаса.ого Зб КОМВИНАТОРНЫй ПОИСК 7.2.1 Я(С) = еБ(С/е) ОБ(С~,е).

(47) В своей диссертации в университете Виктории (1999) Малькольм Д. Смит (Ма)- со)ш Л. Бпн1п) разработал красивый способ использования рекурсии (47) для поиска всех остовных деревьев в порядке "кода Грея двери-вертушки": каждое дерево в его схеме получается из предшествующего путем простого удаления одного ребра и подстановки другого.

Такой порядок деревьев найти нетрудно, проблема в том, чтобы сделать зто эффективно. Основная идея алгоритма Смита состоит в генерации Я (С) таким образом, что первое остовное дерево включает данное близкое дерево (пеаг ггее), состоящее из и — 2 ребер и не содержащее циклов. Эта задача тривиальна при и = 2; мы просто перечисляем все ребра. При п > 2 и данном близком дереве (ем..., е„з) мы действуем следующим образом. Считаем, что граф С связный, в противном случае остовных деревьев не существует. Образуем С/ег и добавляем ег к квлсдому из его остовных деревьев, начиная с того, которое содержит (ез,..., еа я); заметим, что (ез,..., ев я) — близкое дерево для С/ем так что зта рекурсия имеет смысл.

Если последним найденным таким путем остовным деревом для С/ег является /г... /„з, завершим работу перечислением всех осговных деревьев для С~ем начиная с того, которое содержит близкое дерево Я,..., /„з). Предположим, например, что С вЂ” граф р 2 г 6 = 1 4 4 3 (48) сделано для волк! 0$апа7а.ого образуют свободное дерево, соединяющее все вершины. Остовные деревья играют важную роль во многих приложениях, особенно при изучении сетей, так что задача генерации всех остовных деревьев рассматривалась многими авторами. Фактически систематические способы их перечисления разработаны в начале 20-го века В. Фосснером (%.

Гепззпег) (Аппп)еп пег РЬузГк, (4) 9 (1902), 1304-1329], задолго до того, как стали задумываться о генерации других типов деревьев. В дальнейшем рассмотрении мы допускаем, что граф может содержать любое количество ребер между двумя вершинами; однако петли (ребра, выходящие и возвращающиеся в одну и ту же вершину) запрещены, поскольку петля не может быть частью дерева. Основная идея Фосснера очень проста и хорошо подходит для вычислений: если е — произвольное ребро графа С, то остовное дерево либо содержит его, либо нег. Предположим, что ребро е соединяет вершину и с вершиной е, и пусть оно является частью остовного дерева; тогда остальные и — 2 ребер этого дерева покрывают граф С/е, который мы получим, рассматривая вершины и н е как идентичные. Другими словами, остовные деревья, которые содержат е, по сути те же, что и остовные деревья сжатого графа С/е, который получается в результате сжатия ребра е в точку.

С другой стороны, остовные деревья, которые не содержат е, являются остовными деревьями уменьшенного графа С~е, полученного в результате удаления ребра е, Таким образом, множество Я (С) всех остовных деревьев С удовлетворяет соотношению 7.2д гвнврлция основных комвинлторных овъектов з7 с четырьмя вершинами и пятью ребрами (р,с,г,л,1). Начиная с близкого дерева (р, д), процедура Смита сначала образует сжатый граф С~21 у С,гр - «~г Яз- г~ 2 з б)р 1 г 4 з начиная с того, которое содержит (г, г); это деревья гэд, гдс, 41л.

Детальная реализация влюритма Смита весьма поучительна. Как обычно, мы представляем граф, используя для представления каждого ребра и — и двух дуге— и — н и с — и, и поддерживая список "узлов дуге для представления дуг, покидающих каждую вершину, Нам потребуется уменьшать я увеличивать количество ребер графа, так что зти списки лучше сделать дважды связанными. Если а укэзывает на узел дуги, представляющий и — и, то указывает "напариикае а, который представляет дугу и — и; является "верхушкой'* а, т.е. э (следовательно, $, вг — — и); представляет собой необязательное имя, которое идентифицирует данное ребро (эквивалентно 1 нг)~ указывает на следующий элемент в списке дуг и; указывает на предыдущий эммент в списке дуг и; представляет собой связь, используемую для восстановлении дуг, как по- ясннется ниже. Ра Вершины представлены цельпии числами (1,, и); номер дуги с — 1 представляет собой головной узел дважды связанного списка для вершины ш Головной узел а распознается по тому факту, что его верхушка 1„(см.

пояснение выше) равна О. Обозначим степень вершины с как г( . Так, например, граф (48) может быть представлен при помощи (амат„дэ, о4) = (2, 3, 3, 2) и следующих 14 узлов луг: а = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 — О О 0 О 1 2 1 3 2 3 2 4 3 4 (а р р э э г г э э и„ = 5 4 6 10 9 7 8 О 13 11 12 1 3 2 р, = 7 11 13 12 1 О 2 5 6 4 3 9 10 8 ~Следуи автору, мм используем дли обозначении направленного ребра термин "дуга". — Иримеч. гмр. сделано для эиэлилп$апаса.ого и перечисляет ею остовнью деревья, начиная с того, которое содержит д. Это может быть список за, бч, ПЧ 1г, гл; таким образом, деревья рзл, р91, р1э, рг н ргл покрывают С.

Остается только перечислить остовные деревья графа 38 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 Управлять неявной рекурсией алгоритма Смита удобно при помощи массива указателей на дуги а~... а„ь На уровне 1 процесса дуги а1... а~ 1 означают ребра, которые были включены в текущее остовное дерево; а~ игнорируется, а дуги а~+1... а„1 обозначают ребра близкого дерева сжатого граФа (... (О/а1) .. ) /ас-и которое должно быть частью следующего остовного дерева.

Существует и другой массив указателей на дуги э~... э„э, представляющий стеки луг, временно удаленных из текущего графа. Верхний элемент стека для уровня 1 — эь и каждая дуга а связывается со следующей эа ней, (р (которая равна О на дне стека). Ребро, удаление которого разъединяет связный граф, называется мостом (Ьг)айе). Одним иэ ключевых моментов приведенного далее алгоритма является то, что мы хотим сохранять текущий граф связным; следовательно, мы не можем устанавливать с' — С'1е, когда е является мостом. Алгоритм Я (Все остовпые деревья). Данный алгоритм посещает все останные деревья заданного связного графа, представленного структурами данных, которые поясняются выше.

Для удаления и воссталовления элементов в дважды связанных списках здесь используется метод "танцующих связей", который будет всесторонне рассмотрен в разделе 7.2.2.1. Обозначение "Ие1е1е (а)" в шагах алгоритма представляет собой сокращенную запись пары операций (51) ир. - и, р„, — р,; аналогично эюму, "иийе1е$е (а)" означает (52) р„, — а, ир, — а. Я1. [Инициализация.[ Установить а1... а„~ равным остовному дереву графа (см.

упражнение 94). Установить также х — О, 1 — 1 и э~ ~- О, Если и = 2, установить и — 1, е †ион перейти к шагу 95. Я2. [Вход на уровень Ц Установить е - а~+и и ~- $, и р — 1,~ц. Если 4„ > 4„, обменять р +-~и и установить е — е ш 1. ЯЗ. [Сжатие е.[ (Сейчас и будет сделано идентичным р путем вставки списка смежности и в список р, Следует также удалить все бьющие ребра между и и р, включан ребро е, поскольку иначе такие ребра станут петлями.

Удаленные ребра связываются вместе, так что мы сможем восстановить нх на шаге Б7.) УСтапаэятъ й — Э)„+ар, 1' — И„1 И 9 — О. ПОКа 17 ~ О, ВЫПОЛНЯЕМ СЛЕЛУЮЩЕЕ: если $7 = с, выполнить де(с1е ()'), 4е(е1е (у э1 1) и установить й ~ — Й вЂ” 2, 17 — у, у - 7; в противном случае установить 1иэ1 1- р. Затем установить у ~ — иу и повторять эти действия до тех пор, пока не будет выполнено условие $7 = О. Наконец усгановнть1 у " я 9 " 1 ирэ ' ир ре, р> Ррг ' — 9 ар+-иу и а~ — е. 84. [Продвижение Ц Установить 1 - 1+ 1. Если 1 с и — 1, установить э~ — 0 и вернуться к шагу 82. В противном случае установить е — и„ь сделано для эээкж$я$анаса,ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБ"ЪЕКТОВ 39 89. [Посещение.[ (Текущий граф в настоящий момект имеет только две вершины, одна из которых и.) Установить а„1 - е и посетить остовное дерево а~...

а„ь (Если х = О, это первое посещаемое остовное дерево; в противном случае оно отличается от своего предшественника удалением х и вставкой е,) Установить х — е и е - и,. Повторитыпаг 85, если 1, ф О. 86. [Уменьшение 1,] Установить 1 ~ — 1 — 1. Завершить работу алгоритма, если 1 = О; в противном случае установить е — а~, и - 1, и е ~- 1„вь 87.

[Восстановление е.[ Установить | — и — 1, д — е — 1, пр — яр, Рр, "- 9 "рр " 1 ~ р„, — 1 и 1 — р1. Пока 11 ~ О, устанавливатьгуп1 - и и 1 — рг. Затем установить 1 — 1„Й вЂ” с~„; пока 1 ф О, выполнять следующее: установить и — и+ 2, выполнить иис(с(еФе (1' Ю 1), идти(е(е1е (1) и установить | — 11. Наконец, установить Н„» — к — И„. 88. [Проверка моста.[ Если е — мост, перейти к шагу 89.

(См. один из способов выполнения данной проверки в упражнении 95,) В противном случае установить х — е, 1, — зь гч ~ — е; выполнить с(е(е1е(е) и Не(еге(е ш 1). Установить Ы„- Ȅ— 1, д„— д„— 1 и перейти к шагу 82. 89. [Отмена удалений на уровне Ц Установить е - зь Пока е ф О, выполнять следующие действия: установить и «- 1„о — 1,пм 8„- Н„+ 1, И„~ — Ы„+ + 1, выполнить ит1е(е1е (е 9 1) и ити(е1е1е (е), и установить е — 1,. Вернуться к шагу 8б. 1 Вы можете выполнить шаги алгоритма вручную на небольшом графе, таком, как (48). Обратите внимание на тонкий момент, вазннкающий на шагах 83 и 87, когда список смежности н становится пустым.

Обратите также внимание на то, что возможны некоторые сокращения ценой усложнения алгоритма; такие улучшения алгоритма мы рассмотрим позже в этом разделе. еПоследовательио-параллельные графы. Задача поиска всех остовных деревьев становится особенно простой, когда данный граф имеет последовательное н/или параллельное разложение.

Последоеашельно-яеряллельнмй граф (зег1ез-рагв(1е( угарЬ) между з и 1 представляет собой граф С с двумя указанными вершинами з и Ф, ребра которого могут быть рекурсивно построены следующим образом: С либо состоит нз единственного ребра з — й либо представляет собой последовательнее сеерхребро (зена1 зпрегедбе), состоящее из к > 2 последовательно-параллельных подграфов С. между е и 1, соединенных в ряд, такой, что з = гч и 1 = з +1 для 1 < 1 < < Й, и 1ь = 1; либо представляет собой параллельное сверхребро (рвгайе) зпреге38е), состоящее из Й > 2 последовательно-параллельных подгрвфов С; между з и 1, соединенных параллельно.