Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 31
Текст из файла (страница 31)
а„1 при четном и, то время работы должно быть Й (пэ), поскольку Й (и) проверок мостов требуют времени Й (и) каждая. (Ь) Здесь аь изначально представляет собой е»» для и > Ь > 1, где е1— дуга и — 1. Посещенные остовные деревья при и > 4 представляют собой соответственно е»-э ° ° е1е»1 е~-э ° ° ° е!е»-м е»-э ° ° еэе~-1е» е»-з ° ° ° еэе~-1с~е1 е» 1е»е~ ...е» э. Вслед за деревом е» э...еь,эе» 1е»е~...еь вычисления опусюются на уровень и — Ь вЂ” 3 и вновь поднимаются для 0 < Ь < и — 4; все проверки мостов эффективны. Таким образом, общее время работы квадратично (в авторской версии — 35.5пх + 7.5п — 145 обращений к памяти при и > 5).
Кстати, в обозначениях 81эл(огс) Стар)гВаэе Р„представляет собой Ьоагд(п, О, О, О, 1, О, 0), а С» — Ьоагд(п, О, О, О, 1, 1, 0); вер1пины в 81ап1огд ОгарЬВаэе нумеруются от 0 до и — 1. 97. Да, когда (э,ь) равно (1, 2), (1,3), (2, 3), (2, 4) или (3,4), но не (1,4). ь 98. А'; это так называемый»дувльный планарный граф" планаре ного графа А. (Близкие деревья А' комплементарны остовным деревьям А и наоборот.) 99.
Этот метод работает (в чем можно убедиться по индукции по размеру дерева), по сути, по тем же причинам, по которым он работает для и-кортежей в разделе 7.2.1.1, но с дополнительным условием, как именно мы должны обозначать каждый дочерний узел непростого узла. сделано для иэпп!я$анаса.ого 130 ОТВЕТЫ К УПРАЖНЕНИЯМ Листья всегда пассивны, и они не являются ни простыми, ни непростымн; поэтому мы считаем, что внутренние узлы пронумерованы от 1 до пг в прямом порядке обхода. Пусть у'„= р для всех внутренних узлов, за исключением тех случаев, когда р — пассивный непростой узел, у которого ближайший непростой узел справа является активным; в этом случае ур должен указывать на ближайший активный непростой узел слева.
(Для такого определения мы представляем наличие искусственных узлов О и т, + 1 слева и справа; оба этн узла непростые и активные.) Р1. (Инициализация.) Установить ~р — р для 0 < р < гп; установить также 1е — 1, еэ О и установить все з„так, чтобы г,, = пр. Р2. «Выбор узла р.) Установить д - т; затем, пока 1е —— ою устанавливатыу +- 4 — 1. Установить р — Уч и Д вЂ” 9; завершить работу апгоритма, если р = О.
РЗ. [Изменение д .) Установить э — д„, э' — г„й — ер и 4г — э'. (Сейчас Й = е, ~ Ф еэ") Р4. (Обновление значений.) Установить д — э и ее - й Ю 1. Пока сЦ ~ О, устанавливать е 1- 4ч и еэ — Й ® 1. (Теперь д является листом, который входит в конфигурацию, если й = О, и покидает ее, если и = 1.) Аналогично установить е — э' и ее — к. Пока 4е ф О, устанавлявать о — д и вэ — /сЮ1. (Теперь е является листом, который покидает конфигурацию, если Й = О, и входит в нее, если й = 1.) Рб. (Посещение.! Посетить текушую конфигурацию, представленную всеми значениями листьев. Рй. (Пассивирование р?) (Все непростые узлы справа от р в настоящий момент активны.) Если 4э ф яю вернуться к шагу Р2.
В противном случае установить зэ — э, 9 — Р— 1; пока 1е = ию Устанавливать д +- д — 1. (ТепеРь 9 пРедставлЯег собой первый непростой узел слева от р; мы сделаем р пассивным.) Установить ,гр —,Ую Уе — д и вернуться к шагу Р2, ! Хотя шаг Р4 может преобразовывать непростые узлы в простые и яаоборот, обновлять указатели у не требуется, поскольку они остаются корректно установленными. 100. Завершенную программу под названием СВАУВРЯРАЫ можно найти на сайте автора. Доказательство ее асимптотической эффективности использует результат, полученный в упражнении 110.
102. Если это так, то обычные остовные деревья могут быть перечислены в сшроеом порядке двери-вертушки, при котором ребра, на каждом шаге входящие в остовное дерево и покидающие его, являются смежными, Интересные алгоритмы для генерации всех ориентированных остоиных деревьев с заданным корнем приведены в работах Наго!4 Х. СаЬоэг атп1 Епйепе %. Муегв, 81СОМР, 7 (1978), 280-287 и 8, Кароог аш1 Н. ВашевЬ, А)8огйЬт!са, 27 (2002), 120-130, 108.
(а) Рассыпание лексикографически увеличивает (хе, хм..., х„), но не изменяет значение хэ+ +х . В каком бы порядке мы ни рассыпали 1; и Ъ', результат будет один и тот же. сделано для эуэлкиИанаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 131 (Ь) Добавление песчинки изменяет 16 устойчивых состояний следующим обра- Дано: 0000 0001 0010 ООП 0100 0101 ОПО ОП1 1000 1001 1010 10П ПОО П01 П10 ПП +0001 0001 0010 00П 0001 0101 ОПО ОП1 0101 1001 1010 10П 1001 П01 П10 ПП П01 +0010 ОО1О ООП Оан ООЮ ОПО ОШ ОЮ1 ОПО ЮЮ ЮП 1001 ЮЮ ШО ПП ПО1 ШО +0100 0100 0101 ОПО ОП1 1000 1001 1010 1011 ПОО П01 П10 Ш1 0100 0101 ОПО ОП1 +1000 1000 1001 1010 10П ПОО П01 П10 ПП 0100 0101 ОПО ОП1 1000 1001 1010 10П РекУРРентными состоЯнимми Явлиютса Девить слУчаев с хс + хз > 0 и хз + хс > > О.
Заметим, что многократное добавление 0001 приводит к бесконечному цяклу 0000 — 0001 — 0010 — 0011 — 0001 — 0010 — °, однако состояния 0001, 0010 и 0011 ие являются рекуррентными. (с) Если х = а (х+ 1), то также для всех Ь > О справедливо х = и (х+ Н). Все компоненты 1 положительны; таким образом, х = а (х+ пзах (4,..., с(„)) — рекуррентное состояние. И наоборот, предположим, что х = а (с(.с- р), где все ус > О; тогда с1 + у + с рассыпается до состояния х + 1, а оно рассыпается до а (с() + у + 1 = с(+ у.
Следовательно, а (х + 1) = сг (с1+ р) = х. (с() ИмеетсЯ Ас = с)ег (ас ) классов, посколькУ злементаРные опеРации со стРоками (упр. 4.6.1-19) приводят матрицу к треугольному виду„сохраняя конгрузнтность. (е) Имеются неотрицательные целые числа тм..., т„, т'„..., т,'„такие, что х+ тсас+ + т„а„= х + т,ас + + т„а„и равно, скажем, у. Для достаточно большого сс вектор у+хс рассыпается за тс+ .+т„шагов до х+Ьг, а за тс+ . + т'„шагов — до х + х1. Следовательно, х = а (х + хс) = а (х' + хс) = х'.
(Е) Приведение к треугольному виду в ответе (с() показывает, что х ш х+ Асу для произвольных вехторов у. Рассыпание сохраняет конгруэнтность; следовательно, каждый класс содержит рекуррентное состояние. (6) Поскольку в сбалансированном ориентированном графе а = ас + .. ° + а„, мы получаем х гв х + а, Если х — рекуррентное состояние, мы видим, что фактически каждая вершина рассыпается только один раз, если х+ а сокращается до х, так как векторы (ап..., а„) линейно независимы. И наоборот: если а (х + а) = х, мы должны доказать, что состояние х рекуррентно.
Пусть х = сг (та); должны существовать некоторые положительные й и т, для которых хь, = х . Тогда каждая вершина рассыпается Й раз, пока х + )са соКращавтея дО Х . СЛЕдазатЕЛЬНО, Сущветаушт ВЕКтОрЫ ру = (усы..., р,„) С уз > С(1, такие, что (т+ )с) а рассыпается до уу. Отсюда следует, что х+ п(т+ Ус) а рассыпается до х + ус + ° . + у„и а (х + ус + ° ° + у„) = а (х + и (т+ 1с) а) = х. (Ь) Рассматривая индексы циклически, останные деревья с дугами ру — ре для ,1 = см..., ц, имеют п — Й других дуг: ъ; — ру 1 для Ь < у < сс + рс и ъ' — 1" +, для Ь + ас < 1 < сс+с. Аналогично: рекуррентные состояния имеют х = 2 для у = см...,сь и х; = 1 для ц < у < сс+м за исключением х = О при у( = 11+ рс и ас > О.
(1) В зтом случае состояние х = (хс,...,х„) рекуррентно тогда и только тогда, когда (п — хп..., п — х„) является решением задачи о парковке, приведенной в указании, поскольку 1 = (1,...,1), а последовательность незапарковавшихся машин оставляет "дыру", которая останавливает рассыпание х + 1 в х. сделано для ьръррк!ВГапара.ого 132 ОТВЕТЫ К УПРАЖНЕНИЯМ Примечание: зта модель, разработанная Дипаком Дхаром (Веера!с 11Ъвг) (Рйуэ. Вег!ея' Бе!сего, 64 (1990), 1613-1616], привела к появлению массы статей в физических журналах.
Дхар заметил, что если внести случайным образом М песчинок, то при М - оо все рекуррентные состояния становятся равновероятными. Данное упражненне основано на материалах работы В. Соп' апд В. Воээ!п, Еигоревп Х СошЪшасог!сэ, 21 (2000), 447-459.
Теория барханов доказывает, что каждый ориентированный граф 12 порождает абелеву группу, элементы которой некоторгям образом соответствуют ориентированным остовным деревьям П с корнем го. В частности, это истинно в случае, когда П вЂ” обычный граф с дугами и — о и и — и для смежных узлов и н о. Таким образом, например, можно "сложить" два остовных дерева, а некоторое остовное дерево может рассматриваться как "нуль", Элегантное соответствие между остовными деревьями и рекуррентнымн состояниями в частном случае, когда П представляет собой обычный граф, найдено Р.
Кори (В. Соп) и И. Ле Варне (У. 1е Вогйпе) [Адгапсеэ !и Аррйе4 Маей., 30 (2003), 44-52). Однако для ориентированного графа П в общем случае простое соответствие неизвестно. Предположим, например, что п = 2 и (еш,еп езо, еы) = (р, Ч, г, э); тогда имеется рг + рэ + дг ориентированных деревьев н рекуррентные состояния соответствуют обобщенным двухмерным торам, как в упражнении 7 00. Но даже в "сбалансированном" случае, когда р+ д > э и г+ э > д, по-внднмому, нет простого отображении остовных деревьев на рекуррентные состояния.
104, (а) Если бег(а1 — С) = О, существует вектор х = (хп..., х„), такой, что Сх = ах н шах(хп, ..,х„) = х = 1 для некоторого т. Тогда а = ах = с — е зхэ > с — 2,.о с 1 = О. (Кстати„действительная симметричная матрица, собственные значенйя которой неотрицательны, называется положишельно полуопреоелепной (роэ(Ф!те зеппдебп!1е). Наше доказательство устанавливает хорошо известный факт, что этим свойством обладает любая симметричная матрица, у которой с „> ~ ~ ,'у~,„е 1~ для 1 < гп < и.) Таким образом, ао > 0; а поскольку С (1,..., 1) = (О,..., 0), ао = О. (Ъ) сне! (х1 — С (С)) = х (х — а~)... (х — а„1); а согласно теореме о матрице, соответствующей дереву, коэффициент при х равен ( — 1)" п, умноженному на количество остовных деревьев.
(с) де! (а1 — С (К„)) = де! ((а — и) 1+ Х) = (а — п) а в соответствии с упражнением 1.2.3-36; здесь,1 — матрица, все элементы которой равны 1. Таким образом, сторонами полного графа являются О, и,..., п. 105. (а) Если еб — — о+ Ье';, то С(С) = па1 — а1+ ЬС(С').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
