AOP_Tom1 (1021736), страница 164
Текст из файла (страница 164)
Те циклы, в которых все знаки одинаковы; Се, Св, С,"в, Сы, С(вэ, Све. 3. Для этого, например, можно использовать три вершины А, В и С с дугами от А к В и от А к С. 4. Если в графе С нет ориентированных циклов, алгоритм 2.2.3Т позволяет выполнить его топологическую сортировку. А если ориентированный цикл существует, топологиче- скую сортировку, очевидно, выполнить нельзя, (В зависимости от интерпретации этого упражнения ориентированные циклы с длиной 1 можно было бы вообще не рассматривать.) б.
Пусть Ь вЂ” такое наименьшее целое число, что бв(ес) = !пй(еу) для некоторого у < Ус. Тогда (ем..., ее) — ориентированный цикл. 6. Нет (формвльно говоря) именно потому, что может существовать несколько различных дуг от одной вершины к другой. 7. Да, оно справедливо для конечных ориентированных графов. Если начать с произвольной вершины 1' и совершать обход только единственно возможного ориентироваммого пути, то ни одна вершина на этом пути никогда не встретится дважды. В конце концов мы обязательно достигнем вершины й (т. е единственной вершины без наследника). Для бесконечных ориентированных графов это утверждение, очевидно, неверно, так как в нем могут быть вершины В, Р), ! л Ъз,...
и дуги от Ъ; к Ъ;.ес для у > 1. 9. Все дуги направлены вверх. с з к ь 10. С1. Установить усу- Р[)], Р[)] с- О. С2. Если Ус = О, прекратить выполнение алгоритма, в противном случае установить т +- Р[Ь], Р[Ь] е- у, у +- Ус, Ь с- т и гювторить шаг С2. ) 11. Данный алгоритм основан на алгоритме 2,3.3Е и методе, описанном в предыдупсем упражнении, поэтому все ориентированные деревья имеют дуги, которые соответствуют дугам в ориемтированмом графе, Здесь Я[)] — вспомогательная таблица, в которой указано направление дуги либо от у к Р[А (Я[)] = +1), либо от Р[)] к у (Я[)] = — 1), В исходном состоянии Р[1] = = Р[п! = О.
Для обработки каждой дуги (а, Ь) можно выполнить такие действия. С1. Установить у +- а ус с р[у] р[)] О С2. Если Ь = О, перейти к шагу СЗ; в противном случае установить т +- Р [ус], у е — Яус], Р[ус] е — у', Яус] с — -е, с с — у, у +- Ь, Ь с- т и повторить шаг С2. СЗ. (Теперь а становится корнем этого дерева.) Установить у +- Ь, а затем, если Р[)] л О, повторно задавать значение у +- Р[у] до тех пор, пока не выполнится условие Р[у] = О.
С4. Если у' = а, перейти к шагу Со; в противном случае установить Р[а] с- Ь, о [а] +- +1, распечатать (а, Ь) как дугу, которая относится к свободному поддереву, и прекратить выполнение алгоритма. Сб. Напечатать сначала "СУСЬйс, а затем — "(а, Ь)". Сб. Если Р[Ь] = О, прекратить выполнение алгоритма. В противном случае, если Я[Ь] = +1, напечатать "+(Ь, Р[Ь])", а если нет, то напечатать "-(Р[Ь], Ь)"; установить Ь +- Р[Ь] и повторить шаг Сб. ) Замечание. Если использовать допущение Мак-Илроя из ответа к упр. 2.3.3 — 10, для выполнения этого алгоритма потребуется осуществить О(т!ойп) этапов.
Но есть и более удачное решение, для которого потребуется выполнить только О(т) этапов. Используйте поиск преимущественно в глубину для построения "пальмы" (ра)гп Сгее) с одним фундаментальным циклом для каждого "листа" [Я. Е, Тагуап, 31СОМР 1 (1972), 146 — 150]. 12. Степень узла дерева равна степени входа, а степень выхода каждой вершины может быть равна только 0 или 1.
13. Определим последовательность ориентированных поддеревьев графа С следующи»» образом: Со содержит лишь одну вершину й; С»+» содержит С» и любую вершину 1' графа С, не принадлежащую графу С», но лля которой существует дуга от Г к»", где Г прннадлеэмит графу С», а также еще одна такая дуга е[1'] для каждой такой вершины. Отсюда по индукпии немедленно следует, что С» — ориентированное дерево для всех й > 0 и что если есть ориентированный путь длиной Й от И к й в С, то»' принадлежит графу С». Следовательно, С вЂ” это множество всех Г и е[Г) в любом С» и оно является искомым ориентированным поддеревом графа С.
14. В лексикографическом порядке они выглядят следующим образом: Р (ещ, ею, еео, еш, еш, ееп епп ею, ем), (еш, езо, еоо, ео», ею, егм ем, ею, ео~ ), Р (еп езо ее» е»о,еоа,еопеш,ею,ем), (еш,ею ет еш ею,езыею,еоо,ео») (е»мею езе еее,ео» еш,еомеппем), (епнетмего еее,еомещ ем,е»е,ее~) (еш,сапего,еш,е»о,еее,еш,ею~ем) (спесям его,есме(мезыеш,еоо,ео») Восемь вариантов получены в результате перебора независимых пар ребер, в каждой из которых одно из ребер может предшествовать другому: еео или ее„ею или еш, е»о или еть 15.
Да, справедливо, так как если связный и сбалансированный граф имеет более одной вершины, то он содержит цепь Эйлера, которая проходит через все вершины. 16. Рассмотрим ориентированный граф С с вершинами 1'и ..., Кз и с дугой от Ъ; к 1» для каждого я в стопке у.
Выигрыш такой игры эквивалентен обходу цепи Эйлера в этом ориентированном графе (действительно, если игра является выигрышной, то заключительная перевернутая карта должна быть взята из центральной стопки; следовательно, этот граф является сбалансированным). Теперь, если игра выигрышная, указанный диграф является ориентированным поддеревом согласно лемме Е.
И наоборот, если указанный диграф является ориентированным деревом, то по теореме П игра является выигрышной. 17. —,' . Такой ответ можно получить посредством трудоемкого перечисления ориентированных деревьев особого типа, применения производящих функций и т. д., основанных на результатах из раздела '2.3.4.4. (Именно таким образом автор впервые получил данный результат.) Кроме того, его можно получить из следующего очень простого прямого доказательства. Определим порядок переворачивания всех карт из колоды. Будем раскладывать пасьянс по приведенным выше правилам до тех пор, пока ситуация не станет неразрешимой, а затем смошенничаем, перевернув первую доступную карту (найдем первую стопку, которая не является пустой, передвигаясь по часовой стрелке от стопки 1) и продолжив раскладывать пасьянс, как и прежде, до тех пор, пока в конце концов не будут перевернуты все карты.
Карты при таком порядке перееорачиеанил будут упорядочены совершенно случайным образом (поскольку значение карты потребуется узнать только после ее переворачивания). Поэтому проблел»а заключается только в подсчете вероятности того, что в полностью перетасованной колоде карт последней картой является "король". В более общей формулировке вероятность того, что й карт остаются повернутыми лицевой стороной вверх по завершении игры, равна вероятности того, что за последней картой с изображением короля в перетасованной колоде карт следует еще я карт, а именно— 4!( ) †;. Следовательно, играя честно, без мошенничества, в среднем за игру придется ~ м»-»»»в! перевернуть в точности 42.4 карты. Замечание, Аналогично можно показать, что вероятность того, что игрок смошенничает Й раз в ходе описанного выше процесса в точности равна числу Стирлинга [»~~»]/13! (см.
уравнение 1.2.10-(9) и упр. 1.2.10-7; более общий случай рассматривается в упр. 1.2.10 — 18). 18. (а) Если существует цикл (1'е, Ъ»,..., Р»), в котором обязательно 3 < /с < и, сумма я строк матрицы А, соответствующих й ребрам этого цикла с соответствующими знаками, 2.3.4.2 644 ОТВЕТЫ К УПРЛжНЕНИЯМ будет строкой нулей. Поэтому, если граф С не является свободным деревом, детерминант матрицы Ао равен нулю. Но, если граф С является свободным деревом, его можно рассматривать как упорядоченное дерево с корнем !ге, а строки и столбцы матрицы Ае переупорядочить так, чтобы столбцы располагаэись в прямом порядке и к-я строка соответствовала ребру от !г-й вершины (столбца) к ее родителю.
Тогда матрица будет треугольной с элементами х! по диагонали и ее детерминант будет равен х1. (Ь) По формуле Бине-Коши (см. упр. 1.2.3-4б) получим (де1 Ач,,„)~, самее АеАа = 1<ч«" * <и где Ач э„— матрица из строк !м...,1„матрицы Ае (таким образом, соответствующая некоторому выбору п ребер графа С). Тогда ответ следует иэ (а). (См.
Я. Ойада апд Н. Опобега, Вп!!. Уашаба!а !7в!г. 2 (1952), 89-П7.) 19. (а) Условия аее = О и а„= 1 представляют собой условия (а) и (Ь) иэ определения ориентированного дерева. Если С не является ориентированным деревом, то существует ориентированный цикл (согласно результату упр. 7), а строки матрицы Ае, соответствующие вершинам ориентированного цикла в сумме дадут строку нулей; следовательно, бес Ае = О. Если С вЂ ориентированн дерево, зададим произвольный порядок для детей каждой семьи и рассмотрим С как упорядоченное дерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
