11. Достаточно доказать, что когда п > 1 и минимальное значение с{г, п) равно с(п - 1, п), то существует по крайней мере одно дерево с минимальной ценой, в котором вывод Tn-i соединен с Т„. (Действительно, для любого дерева с минимальной ценой, в котором имеется п > 1 концевых узлов, и с выводом T„-i, соединенным с выводом Тп, должно существовать и дерево с минимальной ценой с п - 1 концевыми узлами, если рассматривать выводы Т„ 1 и Т„ как "один обобщенный вывод", используя упомянутое в этом алгоритме соглашение.)

Для доказательства приведенного выше выражения предположим, что имеется дерево с минимальной ценой, в котором вывод T„-i "не спаян" с Тп- Если добавить связующее звено Т„~1 - Г„, то получится цикл, причем в нем можно удалить любое другое связующее звено. Удалив связующее звено, которое касается вывода Т„, получим другое дерево, общая цена которого не выше исходной цены и в котором содержится связующее звено Г„-1 - Тп-

12. Создайте две вспомогательные таблицы a(i) и b{i) для 1 < г < п, в которых Tb(i) - самое дешевое соединение между выводом Ti и выбранным выводом, а a(t) - его стоимость. В исходном состоянии а(г) = c(j, п) и b{i) = п- Затем вьшолните следующие операции п-1 раз: найдите такое значение г, что а{г) - mini<j<„ a(j); соедините Tj с Тау, для 1 < j < п, если с(г, j) < a(j), установите a(j) 4- c(j,j) и fe(j) 4- г; установите а{г) 4- оо. Здесь с(г, j) означает c(j, г), когда j < i.

(В определенной степени эффективнее было бы использовать не оо, а однонаправленный связанный список для таких j, которые еще не были отобраны. С учетом или без учета этого прямолинейного подхода для выполнения алгоритма потребуется около О(п) операций.) См. также работы Е. W. Dijkstra, Proc. Nederl. Akad. Wetensch. A63 (1960), 196-199; D. E. Knuth, The Stanford GraphBase (New York: ACM Press, 1994), 460-497. Более совершенные алгоритмы поиска дерева с минимальной ценой рассматриваются в разделе 7.5.4.

13. Если не существует никакого пути от вершины Vi до вершины Vj для некоторого г ф j, то никакое произведение транспозиций не сможет переместить i на место j- Поэтому, если генерируются все перестановки, граф должен быть связным. И наоборот, если граф является связным, при необходимости удаляйте ребра до тех пор, пока не получите дерево. Затем перенумеруйте вершины так, чтобы вершина У„ была смежной только для одной другой вершины, а именно-для Vn-i (см. доказательство теоремы А). Теперь все транспозиции, кроме (п-1 п), образуют дерево с п-1 вершинами. Поэтому по методу индукции, если тг является перестановкой .{1, 2,..., п} с фиксированным расположением п, тг можно представить в виде произведения этих транспозиций. Если тг перемещает п в положение j, то тг(У п-1)(п-1 п) = р фиксирует положение п. Следовательно, тг = р(п-1 n)(j п-1) можно представить как произведение заданных транспозиций.

РАЗДЕЛ 2.3.4.2

1. Пусть (ei,..., е„) - ориентированный путь от V к Vс минимально возможной длиной. Если теперь init(ej) = init(efc) для j < к, то (ei,..., ej i, е*,..., е) будет кратчайшим путем, и аналогичный аргумент можно использовать, если fin(ej) = fin(e*;) для j < к. Следовательно, путь (ei,..., вп) является простым.

2. Те циклы, в которых все знаки одинаковы: Со, Cs, С1з, Сп, Clg, С20-

3. Для этого, например, можно использовать три вершины А, В и С с дугами от А к В и от А к С.

4. Если в графе G нет ориентированных циклов, алгоритм 2.2.3Т позволяет выполнить его топологическую сортировку. А если ориентированный цикл существует, топологиче-

скую сортировку, очевидно, выполнить нельзя. (В зависимости от интерпретации этого упражнения ориентированные циклы с длиной 1 можно было бы вообще не рассматривать.)

5. Пусть к - такое наименьщее целое число, что fin(ejt) = init(ej) для некоторого j < к. Тогда (cj,..., Cfc) - ориентированный цикл.

6. Нет (формально говоря) именно потому, что может существовать несколько различных дуг от одной верщины к другой.

7. Да, оно справедливо для конечных ориентированных графов. Если начать с произвольной верщины V и соверщать обход только единственно возможного ориентированного пути, то ни одна верщина на этом пути никогда не встретится дважды. В конце концов мы обязательно достигнем верщины R (т. е. единственной вершины без наследника). Для бесконечных ориентированных графов это утверждение, очевидно, неверно, так как в нем могут быть вершины R, Vi, V2, V3, . и дуги от Vj к Vj+i для j > 1.

9. Все дуги направлены вверх. <?

10. Gl. Установить к 4- P[j], P[j] 4- 0.

G2. Если к = О, прекратить выполнение алгоритма; в противном случае установить т 4- Р[к], Р[к] ~ i, j ~ к, к <г- mw повторить шаг G2.

11. Данный алгоритм основан на алгоритме 2.3.3Е и методе, описанном в предыдущем упражнении, поэтому все ориентированные деревья имеют дуги, которые соответствуют дугам в ориентированно.м графе. Здесь S[j] -вспомогательная таблица, в которой указано направление дуги либо от j к P[j\ {S[j\ = +1), либо от P[j] к j {S[i] = -1). В исходном состоянии Р[1] = ... = Р[п] - 0. Для обработки каждой дуги (а, 6) можно выполнить такие действия.

С1. Установить j +- а, fc РЦ], P[j] 4- О, s 4- S[j].

С2. Если fc = О, перейти к шагу СЗ; в противном случае установить т +- Р[к], t +- S[k], Р[к\ ч- i, S[k] <--s, s<r-t, j<r-k,k<r-myL повторить шаг C2.

СЗ. (Теперь а становится корнем этого дерева.) Установить j <- 6, а затем, если P[j] Ф О, повторно задавать значение j r- P[j] до тех пор, пока не выполнится условие P[j] = 0.

С4. Если j = а, перейти к шагу С5; в противном случае установить Р[а] ч- Ь, S[a] i-hi, распечатать (а, b) как дугу, которая относится к свободному поддереву, и прекратить выполнение алгоритма.

С5. Напечатать сначала "CYCLE", а затем- "(а,6)".

Сб. Если Р[Ь] = О, прекратить выполнение алгоритма. В противном случае, если S[b] = +1, напечатать "+(Ь, РЩ)", а если нет, то напечатать "-(Р[Ь], Ь)"; установить b *- Р[Ь] и повторить шаг Сб.

Замечание. Если использовать допущение Мак-Илроя из ответа к упр. 2.3.3-10, для выполнения этого алгоритма потребуется осуществить O(mlogn) этапов. Но есть и более удачное решение, для которого потребуется выполнить только 0{т) этапов. Используйте поиск преимущественно в глубину для построения "пальмы" (palm tree) с одним фундаментальным циклом для каждого "листа" [R. Е. Tarjan, SICOMP 1 (1972), 146-150].

12. Степень узла дерева равна степени входа, а степень выхода каждой вершины может быть равна только О или 1.

13. Определим последовательность ориентированных поддеревьев графа G следующим образом: Go содержит лишь одну вершину R\ Gk+i содержит Gk и любую вершину V графа G, не принадлежащую графу Gk, но для которой существует дуга от V к V, где V принадлежит графу Gk, а также еще одна такая дуга е[У] для каждой такой вершины. Отсюда по индукции немедленно следует, что G* - ориентированное дерево для всех /с > О и что если есть ориентированный путь длиной к от V к Къ G, то V принадлежит графу Gk-Следовательно, Goo-это множество всех V и e[V] в любом Gk и оно является искомым ориентированным поддеревом графа G.

14. В лексикографическом порядке они выглядят следующим образом:

(ei2, 620, Соо, Col, ею, боь 612, 622, 621), (612,620,600, 6о1, 612, 622, б21, ею, 601), (612,620,601,610,600,601,612,622,621), (б12,б20, 61, б12, 622,621, 610,600, 601),

(612,622,620, боо, бо1, ею, бо1,612,621), (б12, б22, е2о, боо, edi, 612,621, бю, 601), (б12,б22,б2о,бш,е1о,еоо,ео1,е12,б21), (612,622,620,601,612,621,610,600,601).

Восемь вариантов получены в результате перебора независимых пар ребер, в каждой из которых одно из ребер может предшествовать другому: боо или ejji, ею или 612, 620 или 622.

15. Да, справедливо, так как если связный и сбалансированный граф имеет более одной вершины, то он содержит цепь Эйлера, которая проходит через все вершины.

16. Рассмотрим ориентированный граф G с вершинами Vi, ..., V13 и с дугой от Vj к Vk для каждого к в стопке j. Выигрыш такой игры эквивалентен обходу цепи Эйлера в этом ориентированном графе (действительно, если игра является выигрышной, то заключительная перевернутая карта должна быть взята из центральной стопки; следовательно, этот граф является сбалансированным). Теперь, если игра выигрышная, указанный диграф является ориентированным поддеревом согласно лемме Е. И наоборот, если указанный диграф является ориентированным деревом, то по теореме D игра является выигрышной.

17. -j. Такой ответ можно получить посредством трудоемкого перечисления ориентированных деревьев особого типа, применения производящих функций и т. д., основанных на результатах из раздела 2.3.4.4. (Именно таким образом автор впервые получил данный результат.) Кроме того, его можно получить из следующего очень простого прямого доказательства. Определим порядок переворачивания всех карт из колоды. Будем раскладывать пасьянс по приведенным выше правилам до тех пор, пока ситуация не станет неразрешимой, а затем смошенничаем, перевернув первую доступную карту (найдем первую стопку, которая не является пустой, передвигаясь по часовой стрелке от стопки 1) и продолжив раскладывать пасьянс, как и прежде, до тех пор, пока в конце концов не будут перевернуты все карты. Карты при таком порядке переворачивания будут упорядочены совершенно случайным образом (поскольку значение карты потребуется узнать только после ее переворачивания). Поэтому проблема заключается только в подсчете вероятности того, что в полностью перетасованной катоде карт последней картой является "король". В более общей формулировке вероятность того, что к карт остаются повернутыми лицевой стороной вверх по завершении игры, равна вероятности того, что за последней картой с изображением короля в перетасованной колоде карт следует еще к карт, а именно - 4!(~*)57. Следовательно, играя честно, без мошенничества, в среднем за игру придется перевернуть в точности 42.4 карты. Замечание. Аналогично можно показать, что вероятность того, что игрок смошенничает к раз в ходе описанного выше процесса в точности равна числу Стирлинга [,Д]/13! (см. уравнение 1.2.10-(9) и упр. 1.2.10-7; более общий случай рассматривается в упр. 1.2.10-18).

18. (а) Если существует цикл {Vo, V\,..., Vk), в котором обязательно 3 < fc < п, сумма к строк матрицы А, соответствующих fc ребрам этого цикла с соответствующими знаками.