Tl,... ,Td располагается корень дерева Т, получим в результате применения этого алгоритма f{Ti),..., f{Td), а затем и /(корень(Т)), что и требовалось доказать. Аналогично можно доказать корректность алгоритма F для лесов.

17. G1. Опустошить стек и установить Р указываюш;им на корень данного дерева (послед-

ний узел в обратном порядке). Вычислить /(NODE(P)).

G2. Поместить в стек DEGREE(P) копий /(NODE(P)).

G3. Если Р является первым узлом в обратном порядке, прекратить выполнение алгоритма. В противном случае установить Р указывающим на его предшественника в обратном порядке (например, для (9) это значит просто установить Р <- Р - с). G4. Вычислить /(nODE(P) ) с помощью значения верхнего элемента стека, которое равно /(N0DE(PARENT(P))). Удалить это значение из стека и вернуться к шагу G2. Замечание. Алгоритм, аналогичный данному, может быть основан не на обратном, а на прямом порядке, как в упр. 2. На самом деле для этого можно использовать также фамильный порядок или порядок уровней, причем в последнем случае вместо стека можно использовать очередь.

18. Таблицы INF01 и RLIM, а также описанный в данном разделе способ вычисления LTAG позволяют получить эквивалентное бинарное дерево в обычном представлении. Теперь для достижения цели нужно совершить обход этого дерева в обратном порядке, попутно подсчитывая степени.

Р1. Пусть R, D и I-стеки, которые в исходном состоянии пусты. Тогда следует установить R i= п -f 1, D i= О, j +- О, /с 0.

Р2. Если (Bepx)R > j-fl, перейти к шагу Р5. (Если бы существовало поле LTAG, можно было бы вместо этого условия использовать условие LTAG[j] = 0.)

РЗ. Если стек I пуст, прекратить выполнение алгоритма; в противном случае установить i<=l,k-h-k + l, INF02[fc] 4- INFO[j], DEGREE[fc] <= D.

P4. Если RLIM[j] = 0, перейти к шагу РЗ; в противном случае удалить верхний

элемент стека R (который равен RLIM [г] ). Р5. Установить верх(В) +- верх(В) -f 1, j <- j + 1, I j, D 0. Если RLINK[j] ф О,

установить R RLIM[j] и перейти к шагу Р2.

19. (а) Это эквивалентно утверждению, что связи SCOPE не пересекаются. (Ь) Первое дерево леса содержит di -f 1 элементов. Доказательство можно продолжить методом индукции, (с) Условие (а) выполняется для минимальных значений.

Замечания. Из упр. 2.3.2-20 следует, что did2 .. .dn также может интерпретироваться на основании инверсии: если к-й узел в обратном порядке является pfc-м узлом в прямом порядке, то dk-это количество элементов > к, которые располагаются слева от к в pip2 Рп-

Аналогичная схема, в которой перечисляется количество наследников каждого узла в обратном порядке для данного леса, приводит к последовательности чисел ciC2...Cn, которые характеризуются свойствами (i) О < cj, < fc и (ii) fc > j > к - Ck, из чего следует j - Cj > k - ck Алгоритмы на основе таких последовательностей были исследованы Ж. М. Палло (J. М. Pallo) в работе Сотр. J. 29 (1986), 171-175. Обратите внимание, что Ck является размером левого поддерева fc-ro узла в симметричном порядке обхода соответствующего бинарного дерева, dk также можно интерпретировать как размер правого поддерева fc-ro узла в симметричном порядке обхода соответствующего бинарного дерева, а именно - бинарного дерева, которое соответствует данному лесу согласно методу из упр. 2.3.2-5.

Отношение < dj, для 1 < fc < п определяет интересное решеточное упорядочение лесов и бинарных деревьев, которое впервые было предложено Д. Тамари (D. Tamari) [These (Paris, 1951)] с помощью другого способа (см. упр. 6.2.3-32).

РАЗДЕЛ 2.3.4.1

1. {В, А, С, D, В), (В, А, С, D, Е, В), (В, D, С, А, В), (В, D, Е, В), (В, Е, D, В), {B,E,D,C,A,B).

2. Пусть (Vo, Vl,..., Vn) - путь с минимально возможной длиной от вершины V к вершине V. Если бы Vj = Vk для некоторого j < к, то путь {Vo,... ,Vj, Vk+i, ,Vn) был бы еще короче.

3. (Фундаментальный путь проходит один раз через ребра ез и 64, а цикл Сг проходит через них -1 раз, что в сумме дает нуль.) Путь проходит через такие ребра: ei, ег, ее, ет, eg, ею, еп, ei2, ен.

4. Если утверждение задачи не выполняется, то допустим, что G" является таким подграфом для графа С, который получен в результате удаления каждого ребра ej, для которого Ej = 0. Тогда G" является конечным графом без циклов и с минимум одним ребром. Поэтому согласно теореме А существует по крайней мере одна такая вершина V, что она является смежной в точности для одной вершины V. Пусть ej - ребро, соединяющее вершины V и V, тогда уравнение Кирхгофа (1) для вершины V выглядит как Ej = О, что противоречит определению G".

5. А = 1 + Es, В = 1 + - Е2, С = 1 + D = 1 + Ei - Еъ, Е = 1 + Еп - Е21, F = 1 -Ь Я/з + Eu-E2i,G=l+ ЕЧз, H = Eu-E2i,J = En, К = E/g + Е20, L = En + Elg + E20 -E2i,P En + E20 -E2i,Q E20, R = ЕП-Е21, S =z £25- Замечание. В этом случае с помощью переменных А, В,..., S можно выразить также значения Е2, Еъ, , Е25-Следовательно, имеется девять независимых решений, и именно поэтому из упр. 1.3.3-(8) были исключены шесть переменных.

6. (Следующее решение основано на идее о том, что распечатывать можно каждое ребро, которое не образует цикл с предыдущими ребрами.) Используйте алгоритм 2.3.3Е, в котором каждая пара (а,, Ь,) представляет соотношение а; = bi в обозначениях этого алгоритма. Единственное внесенное изменение заключается в печати пар {ai,bi), если j ф к на, шаге Е4.

Чтобы показать справедливость данного алгоритма, нужно доказать, что (а) алгоритм не выводит на печать ребра, которые образуют цикл, (Ь) если граф G содержит по крайней мере одно свободное поддерево, то данный алгоритм распечатает п-1 ребер. Определим отношение j = к, если существует путь от вершины Vj до вершины Vk или если соблюдается условие j = к. Очевидно, что это отношение эквивалентности, причем j к тогда и только тогда, когда оно может быть выведено из отношений эквивалентности аi = bi, ..., am =bm-Утверждение (a) справедливо, потому что алгоритм не выводит на печать ребра, которые образуют цикл с прежде распечатанными ребрами, а утверждение (Ь) справедливо, потому что PARENT [fc] = О только для одного fc, если все вершины являются эквивалентными.

Более эффективный алгоритм, однако, должен быть основан на поиске в глубину (см. алгоритм 2.3.5А и раздел 7.4.1).

7. Фундаментальные циклы: Со = ео + ei + е4 + eg (фундаментальным путем будет ei+e4 + eg); Съ - еь + ез + ег; Се = ее - ег -f 64; Ст = ет - 64 - ез; Cg = eg - eg - 64 - ез. На основании этого получим Ei = 1, Е2 = Еъ - Ев, Ез = Еъ - Ет - Е, Е4 = l + Ee - ET - Es,

Ед = 1- Eg.

8. На каждом шаге процедуры приведения объединяются две стрелки е; и Cj, которые выходят из одного и того же блока, а потому достаточно доказать, что эти действия можно обратить. Таким образом, если состояние ребер е, + ej после их объединения известно, необходимо указать состояние для ребер и Cj до объединения. При этом могут существовать три разных случая.

Случай 1 Состояние до

Состояние после

Случай 2

Случай 3

Здесь А, В и С - вершины или супервершины, а а и /3-другие потоки, отличные от потока е; 4- ej. Эти потоки могут быть распределены среди нескольких ребер, хотя здесь показана только одна вершина. В случае 1 (ребра е; и ej направлены к одному и тому же блоку) можно произвольным образом выбрать ребро е,, и тогда ej 4- (cj 4- Cj) - е;. В случае 2 (е, и ej направлены к разным блокам) обязательно получим cj 4- /3 - а, ej 4- /3" - а". В случае 3 (ребро является циклом, а ej - нет) обязательно получим Cj -i- /3 - а, ei <- (cj 4- Cj) - ej. Таким образом, процедура объединения обращена во всех трех случаях.

Результат выполнения этого упражнения доказывает, что количество фунда.менталь-ных циклов в приведенной блок-схеме равно минимальному количеству потоков вершин, измерив которые, можно определить все потоки. В рассматриваемом примере приведенной блок-схемы достаточно вычислить только три потока вершин (например, а, с, d), тогда как исходная схема из упр. 7 имеет четыре независимых потока ребер. Всякий раз, когда возникает случай 1, одно измерение можно сэкономить.

Аналогичная процедура приведения может быть основана на объединении стрелок, которые направлены на данный блок, а не из него. Можно показать, что подобным образом получаем такую же приведенную блок-схему, но с другими именами супервершин.

Данное построение основано на идеях Армена Нахапетяна (Armen Nahapetian) и Ф. Стивенсона (F. Stevenson). Более подробно этот вопрос рассматривается в работе [D. Е. Knuth and F. Stevenson, BIT 13 (1973), 313-322].

9. Каждое ребро, выходящее из вершины и сразу же замыкающееся на ней, называется совершенно отдельным фундаментальным циклом. Если существует /с 4- 1 ребер е, е,..., е* между вершинами V и V, построим к фундаментальных циклов е ± е, ..., е* ± е (выбирая "4-" или "-" в зависимости от того, совпадает ли направление обхода ребра с направлением стрелки), а затем продолжим работу так, как будто существует только ребро е.

Действительно, эту ситуацию можно существенно упростить, если определить граф таким образом, чтобы в нем допускалось наличие нескольких ребер между одинаковыми вершинами, а также определить ребра, концы которых могут замыкаться на одном узле, причем пути и циклы определять на основе ребер, а не вершин. Такая формулировка позволяет дать определение ориентированного дерева, которое приводится в разделе 2.3.4.2.

10. Если все выводы соединены в единую сеть, то соответствующий ей граф должен быть связным. При этом сеть с минимальным количеством соединений не будет включать циклов, а потому получится свободное дерево. По теореме А свободное дерево содержит п - 1 соединений, а граф с п вершинами и п - 1 ребрами является свободным деревом тогда и только тогда, когда он является связным.