Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 14
Текст из файла (страница 14)
[33[ Алгоритм 8 требует "прокрутить стартер", т.е. найти начальное остовное дерево на шаге 81. Объясните, как это сделать. 93. [36[ Завершите алгоритм 8, реализовав проверку моста на шаге 88. » 99. [36[ Проанализируйте приближенное время работы алгоритма 8, когда данный граф представляет собой (а) путь Р„длиной и — 1; (Ь) цикл С„длиной и.
97. [16[ Является ли граф (48) последовательно-парэллельным? 93. [16[ Какой последовательно-параллельный граф соответствует графу (53), если узел А — последовотельнмб? м 99. [36[ Рассмотрим последовательно-параллельный граф, представленный деревом, как в (53), со значениями узлов, удовлетворяющими условию (55). Эти значения определяют остовное дерево или близкое дерево, в соответствии с тем„равно ли значение ер корня р единице илн нулю.
Покажите, что описанный далее метод генерирует все прочие конфигурации корня. 1) В начале все непростые узлы являются активными, а все остальные — пассивными. й) Выбираем крайний справа активный узел р в прямом порядке обхода; если все узлы пассивны, завершаем работу. ш) Изменяем др +- га, обновляем все значения в дереве и посещаем новую конфигурацию. 1г) Активизируем все непростые узлы справа от р. ч) Если г(„пропгло по всем дочерним узлам р, поскольку р — последний ставший активным узел, делаем его пассивным. Возвращаемся к шагу (Н). сделано для мгюичп$апа1а.ога 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 61 Поясните также, как эффективно выполнить описанные шаги. Указание: для ревлпзации шага (2) введите Указатель 2„; делайте Узел Р пассивным, когда пр становнтсл Равным хр, и в этот момент сбРасывайте значение 3р, ДелаЯ его Равным пРеДыДУ- щему значению 6р.
Для реализации шагов (й) и (12) воспользуйтесь указателем ур, аналогичным используемому в алгоритмах 7.2.1.1Ь и 7.2.1.1К. 100. [46) Реализуйте "алгоритм Э двери-вертушки" для генерации всех остовных деревьев путем комбинации алгоритма 8 и идей из упражнения 99. 101. [46) Имеется ли простой способ перечисления в порядке "двери-вертушки" всех и" 2 остовных деревьев полного графа К„7 (Порядок, получаемый с использоввлием алгоритма 8, слишком сложен.) 102. [46) Орненгпироеанимм осшовнм44 деревам (онеп2ед врапшпй сгее) ориентированного графа 17, состоящего из и вершин, известным также под названием "остовной древовидности" (эрапп1пй агЬогевсепсе), является ориентированное поддерево .О, содержащее и — 1 дуг. ТЬорема о матрице, соответствующей дереву (упражнение 2.3.4.2 — 19) гласит, что ориентированные поддеревья, имеюпгие данный корень, могут быть легко подсчитаны путем вычисления детерминанта размером (и — 1) х х (и — 1).
Можно ли перечислить эти подлеревья в порядке "двери-вертушки", при котором на каждом шаге происходит удаление одной дуги и замещение ее другой? ь 103. [БМ39) (Барханы.) Рассмотрим произвольный ориентированный граф О, состоящий из вершин У0, $~1,..., 1'„с дугами ео от Ъ', к 1', где ен = О. Будем считать, что 11 имеет, как минимум, одно ориентированное остовное дерево с корнем 10, это предположение означает, что если мы соответствующим образом перенумеруем вершины, то ее+ +ей, М > О для 1 < 1 < И. Пусть 64 = Е'0+ ' +ем — общая исходящая степень вершины 90 Поместим хг ПЕСЧИНОК На ВЕршину 11 Для О < 1 < П и сыграем в следующую игру.
Если яч > 4(, для любого 1 > 1, уменьшим х1 на 61 и установим х 4 — х + 04, для всех у ф 1 (другими словами, если это возможно, перешлем по одной песчинке кз р1 по всем выходящим из нее дугам, за исключением вершины 1 = О. Назовем эту операцию "рассьшанием" У1, а последовательность рассыпаний — "лавиной". Вершина У0 особая; вместо рассыпания она собирает песчинки, которые, по сути, покццвют систему). Продолжаем до тех пор„пока не будет выполнено условие х1 < 61 для 1 < 1 < и. Такое состояние х = (х1,...,х„) назовем дстойчнем44.
а) Докажите, что каждая лавина завершается устойчивым состоянием после конечного числа рассыпаний. Более того, конечное состояние зависит только от начального состояния, но не от порядка выполнения рассыпаннй. Ь) Пусть 0 (х) — устойчивое состояние, являющееся результатом начального состояния х. Назовем устойчивое состояние рекурреюинм44, если это с (х) для некоторого х с хг > И; для 1 < 1 < и.
(Рекуррентные состояния соответствуют "барха- наЫ', которые образовались за длинный промежуток времени, после многократного случайного введения новых песчинок.) Найдите рекуррентные состояния для частного случая и = 4 и дуг П 11 ~ ге~1~~ ~ р2~12 ' гО~И2 ~ р1 Уэ ' ге Уз ~ ~4~~4 ~ 10 У4 ~ 13. сделано для въквк! п$апаса.ого 62 КОМВИНАТОРНЫЙ ПОИСК с) Пусть 4 = (4»,..., Ы„). Докажите, что х рекуррентно тогда и только тогда, когда х = >» (я+ г), где 1 — вектор 4 — а (о).
о) пусть в» вектор ( е>з» е>0-н>п>> е>(>+0» ° ° е>») д»ш 1 < 1 ц % 'гаким образом, рассыпание 1>) соответствует изменению вектора состояния х = = (х»,..., л„), который становится равен х — а;. Будем говорить, что два состояния х и в» конеррэн»лнм (записываем клк хшх'), если х — х' = гл»а» +" +п»„а„ для некоторых целых чисел та»,..., т . Докажите, что существует ровно столько же классов эквивалентности конгрузнтных состояний, сколько и ориентированных остовных деревьев в Р с корнем 1>е.
Уяезаяие: см. теорему о матрице, соответствующей дереву (упражнение 2.3.4.2-19). е) Докажите, что если хм х', а также и х, и я' рекуррентны, то х = х'. 1) Докажите, что каждый класс конгруэнтностн содержит единственное рекуррентное состояние. й) Пусть Р— сбалансированный граф в том смысле, что входящая степень каждой вершины равна ее исходящей степени.
Докажите, что в таком случае х является рекуррентным состоянием тогда и только тогда, когда х = о (я+ а), где а = = (сом...,ее ). Ь) Проиллюстрируйте зту концепцию для случая, когда Р представляет собой *'колесо" с и спицами, когда всего имеется Зп дуг, $»» — 1'е и %» > У»+» для 1 <» < и, где вершина $'„+» рассматривается как ядентичная У». Йайдите взаимно однозначное соответствие между ориентированными остовными деревьями этого ориентированного графа и рекуррентными состояниями его барханов. !) Аналогично проанализируйте рекуррентные барханы, когда Р представляет собой полный граф из и+ 1 вершин, а именно когда е; = (1 ~ Я для 0 <», » < и. Указание: см.
упражнение 6.4-31. ° 104. 1»»М21) Пусть С вЂ” граф с и вершинами (Ъ~,...,1ь), с ребрами е»» между вершинами 1'; и 1'. Обсвначим через С (С) матрицу с элементами с„» = — ео + 4»»4, где 4» = ец + "+ е;„— степень вершины Уь Будем говорить, что сторо»»амп (елресгз) С являются собственные значения С (С), т.е.
корни ае,..., о„» уравнения бег(аХ вЂ” С(С)) = О. Поскольку С(С) — симмегричная матрица, ее собственные значения являются действительными числами, и мы можем считать, что ие ~ а» < ° ° ° < а„ а) Докажите, что с»о = О. Ь) Докажите, что С имеет ровно с(С) = а»... о„»/п остовных деревьев. с) Чему равны стороны полного графа К„? 10$. [НМ87) Продолжая выполнение упражнения 104, мы хотим доказать, что часто есть простой путь определения сторон С, когда граф С построен из друп»х графов, стороны которых известны. Предположим, что С' имеет стороны ае>..., а'„. а граф С" — стороны ае,..., а'„'„,. Какими будут стороны графа С в следующих случаях? сделано для иэуъкдн$анаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОВЪЕКТОВ 63 а) С = С представляет собой дополнение С'.
(Считаем, что в нашем случае е'; < < [1з 1].) Ь) С = С'+ С" представляет собой сумму (соединение) С' и С". с) С = С'+С" представляет собой сосумму (объединение) С' и С". 6) С = С' х С'* представляет собой декартово произведение С' и С". е) С = б (С') представляет собой линейный граф С', где С' является однородным графом степени 4' (все вершины С' имеют ровно по 4' соседей, и в графе нет петель). 1) С = С'О~" представляет собой прямое произведение (конъюнкцию) С' и С", причем С' — однородный граф степени 4', а С" — однородный граф степени 4".
6) С = С'4>С" представляет собой сильное произведение однородных графов С' и Си ~ь 106. [НМ07] Найдите общее количество остовных деревьев (а) в решетке Р х Р„ размером т х и; (Ь) в цилиндре Р„„х С„размером гл х и; (с) в торе С х С„размером т х и.
Почему зтн числа имеют тенденцию состоять только из малых простых сомножителей? Указание: покажите, что стороны Р„и С„можно выразить через числа оь„= 4я1п — „. 2 Ьг 107. [М84] Определите стороны всех связных грв4юв, содержащвх п < 5 вершин и не имеющих ни петель, ни параллельных ребер. 108. [НМ40] Распространите результаты упражнений 104-106 на ориентированные графы. 109. [М46] Найдите комбинаторное пояснение тому факту, что выражение (57) представляет собой количество остовных деревьев в и-мерном кубе.
м 110. [М27] Докажите, ч тель, то он имеет с(С) > вершины у. вольный связный мультиграф без пеостовных деревьев, где 4 — степень 111. [05[ Перечислите узлы дерева (58) в обратно-прямом порядке обхода. 112. [15] Если узел р в лесу предшествует узлу с в прямо-обратном порядке и следует за ним в обратно-прямом, то что можно сказать об узлах р и с7 114. [15] Если вы хотите обойти весь лес в прямо-обратном порядке с применением алгоритма С], то с чего вы должны начать процесс? 116. [20] Проанализируйте алгоритм ф как часто выполняется каждый из шахов алгоритма в процессе полного обхода леса? сделано для ьтьтъЛп[апаса.ого м 113. [60] Как прямо-обратный н обратно-прямой порядки обхода леса Р соотносятся с прямо-обратным н обратно-прямым порядкамя обхода сопряженного леса Рл (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
