Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 33
Текст из файла (страница 33)
Х, 23 (1973), 298-305) принадлежит авторство упражнения 105 (6); им же доказаны интересные результаты о стороне оы которую он назвал "алгебраической связностью" графа С. Герман Креверас (Оегттп Кгеиегяя) в Х СотЬшаяона( ТЬеогу, В24 (1978), 202 — 212, пересчитал останные деревья решеток, цилиндров н торов, а также ориентированные останные деревья ориентированных торов, таких, как О х О„. Отличный обзор сторон графов опубликован Бояном Махаром (Во1ап МоЬаг) в Сгарй ТЬеогу, СотЬ1пявонсв апд Аррйсаяолв (%11еу, 1991), 871 — 898; Р1ясгеяе Маяй., 10Э (1992), 171-183. Исчерпывающее обсуждение важных семейств собственных значений графов и их свойств, включая полную библиографию, можно найти в книге Р.М.
Стеякот1б, М. РооЬ ахк1 Н. ЕасЬя, Ересяга ог" Сгарйя, ЯЬ|п1 еб. (1995). 10Э. Вероятно, имеется также пояснение, связанное с барханами из упражнения 103. сделано для ьуьуьк! пГапага.ого 7.2.1 136 ОТВЕТЫ К УПРАЖНЕНИЯМ 110. Доказательство по индукции. Предположим, что имеется й > 1 параллельных ребер между и и и. Тогда с(С) = /сс(Сг)+с(Св), где Сг — это граф С со склеенными вершинами и и о, а Св — граф С, из которого удалены эти Й ребер. Пусть гге хе ге+ а и д„= Ь+6. Случай 1.
Св — связный граф. Тогда аЬ > О, так что можно записать а = х+ 1 г=г+г ка (е~ Е+гТТ (о) Гя, ° по всем остальным и — 2 вершинам; легко убедиться, что Слрчой 3. Не существует таких вершин и и о, для которых Св — связный граф. Тогда каждое мультиребро С представляет собой мост; другими словами, С вЂ” свободное дерево, за исключением наличия параллельных ребер. В этом случае рпвультат тривиален, если существует вершина степени 1. В противном случае предположим, что и — конечная точка, и ее степень равна г( = Ь ребер и — н. Если где > юг+ 1, то с(С) = гес(Сг) > аlгтггх, где г(„= Ь + 1+ х, и легко проверить„что при х > О г~ г г 'О-г)(гго е а-г.
г (а)= l в = гг > )( й — 1) . Наконец, если г1„= Й+ 1, примем гго = и, иг = р и рассмотрим единственный путь ог — ов — — п„где г > 1 и сг имеет степень„большую 2; каж- даЯ паРа веРшин пг и ов+г (1 < У' < г) соединена одним РебРом. Гипотеза индУкции выполняется. (Другие нижние границы количества остовных деревьев получены в работе Л.Ч.
Кгмвос1г(га, Вллдош Ввгисвигев апгг Л)бонйгпв, 6 (1995), 269-274.) 111. 2 1 5 4 11 7 9 8 6 10 16 12 14 13 3. 112. Либо р находится на четном уровне и является предком 9, либо д находится на нечетном уровне и является предком р. 113. ргеровеогбег(г и) = ровгргеогг(ег(Р) н рсмвргеогг(ег(г ~) = ргеровгогг(ег(Р')~.в 114. Наиболее элегантный подход, учитывающий, что лес может быть пустым, заключается в такой инициализации, что СН17.0(Л) указывает на корень крайнего слева дерева, если таковое имеется.
Затем первое посещение обеспечивается установками ев — Л и Ь вЂ” — 1, после чего выполняется переход к шагу б)6. 115. Предположим, что имеется и, узлов иа четных уровнях и пе на нечетных и что и', узлов на четных уровнях не являются листьями. Тогда шаги (41,..., (В7 выполняются соответственно (и, + и, и, и'„п„п'„и, + 1, и,) раз, включая одно выполнение шага (46 в соответствии с ответом к упражнению 114. 116. (а) Этот результат следует из алгоритма (4. ((г) В действительности все узлы, не являющиеся обычными, строго чередуются между везучими и невезучими, начиная и заканчивая везучими узлами.
Докввагпельсглво: рассмотрите лес Р", получающийся из Р путем удаления крайнего слева листа, и воспользуйтесь индукцией по и. 11'7. Такие леса — это те, которые в представлении с левым сыном и правым братом дают вырожденное бинарное дерево (см. упражнение 31). Таким образом, окончательный ответ — 2" '. Ергероегогбег означает прямо-обратный порядок обхода, а роегргеогдег — обратно. прямой.— ггрпмеч. яер.
сделано для вчиърдн$анаса,ого отввты к упрАжнвниям 137 7.2.1 118. (а) г" ~, Й > 1; везение встречается только возле крайних листьев, (Ь) Получающееся интересное рекуррентное соотношение приводит к решению (Рь + 1 — ((г + 1) шоб 3)/2. 119. Помегим каждый узел х значением с(л) = 2'(2" ! Ь вЂ” метка дуги на пути от корня к х). Тогда значения узлов в прямо-обратном порядке обхода представляют собой бинарный код Грея Г„, поскольку в упражнении 113 показано, что они удовлетворяют рекуррентному соотношению 7.2,1.1-(5). (Если мы применим тот же способ пометок к обычному бнномнальному дереву Т„и обойдем его в прямом порядке, то получим просто целые числа О, 1,..., 2 — 1.) 120.
Ложно. Только четыре нз "полых" вершин на приведенной иллюстрации могут следовать за "квадратными" вершинами в гамильтоновом цикле; следовательно, одной пустой паре не повезло. (См. Н. г'!е1эсЬпег апд НХ. Кгопй, Молагвйегге Гпг МасйетаЯс, 76 (1972), 112-117.] 121. Более того, гамильтонов путь от и к с в Тз существует тогда и только тогда, когда выполняются подобные условия, описанные далее. Мы оставляем и и/или и в ТР!, если они имеют степень 1, и требуем, чтобы путь в условии (!) содержался в пути от и к и (исключая сами и и е). Условие (й) также усиливается посредством замены 'вершины степени 4' на "опасные вершины', где вершина ТР> называется опасной, если она либо имеет степень 4, либо имеет степень 2 и равна и или п.
Наименьший невозможный случай — Т = Р4, где и и г выбраны так, чтобы онн не являлись конечными точками. (СллорЫ рго РелГогйМ МасетаГРйу, 89 (1964), 323 — 338.) Следовательно, Т содержит гамильтонов цикл тогда н только тогда, когда Т является гусеницей (сасегр(!1вг), т.е. свободным деревом, производная которого представляет собой путь. (См. Ггапй Нагагу апд А.З. Яснев!г, Магйешагйа, 18 (1971), 138-140.) 122. (а) Можно представить выражение в виде бинарного дерева, в котором операторы представлены внутренними узлами, а цифры — внешними. Если бинарное дерево реализовано так, как в алгоритме В, то главное ограничение, налагаемое грамматикой, состоит в том, что если г, = й > О, то оператором в узле у будет + или — тогда и только тогда, когда оператором в узле й будет х или /.
Следовательно, общее количество возможных деревьев с и листьями равно 2"Я„м где ߄— число Шредера; при п = 9 это значение равно 10 646 016. (См. упражнение 66, только замените в нем 'лево' на 'право' н наоборот.) Мы можем быстро сгенерировать их все и убедиться, что всего имеется 1640 решений. Без умножений обходится только одно решение, ! + 2/((3 — 4)/(5 + 6) — (7 — 8)/9); пять пар скобок требуют 20 решений„таких, как (((1 — 2)/((3/4) х 5 — 6)) х 7+ 8) х 9; совсем без скобок обходятся только 15 решений.
(Ь) В этом слУчае сУществУет 1+ ~„~, (т)2ь+'Яь = 23463169 возможных деРевьев и 3 365 решений. Кратчайшее решение (длина которого равна 12) было найдено Дьюдени !ТЬе )йееИу Пира!ей (18 Зппе 1899)) и имеет вид 123 — 45 — 67+ 89; однако сделано для тхггквкиИаааса.ого 7.2.1 138 Отнеты к упРАжнениям сам Дьюдени в то время не был уверен, что оно наилучшее, Самое длинное решение имеет длину 27; как упоминалось выше, таких решений 20. (с) При этом количество возможных случаев резко возрастает — до 2+~ ~ь (~~)4ь+'Яь = 8157017474; количество решений равно 96504. Нанболеедлинное решение единственное, оно имеет длину 40: (К(,1/ (.2+ 3)) /,4) /.5) / ( 6 — 7)) / / ( 8 — .9).
Есть пять занимательных примеров наподобие .1+ (2 + 3+ 4 + 5) х 6+ 7+ + 8+ .9 с семью плюсами, а также 10 решений наподобие (1 — .2 — .3 — 4 — .5 — 6) х х (7 — 8 — 9) с семью минусами. Есть только небольшое правило, н нет и» одного точного способа показать, что мм получили наилучшее возможное решение. — Генри Э. Дьюденн ~Непгу Е. Оиг/енеу) Примечания. В перном издании Шиэгг1еггеэ Яр!е!Ьисй Гиг МИсйеп Мари Леске (Маг1е Ьеэ1се) (1864) содержится первое известное упоминание этой задачи; в 11-м издании (1899) приведено решение 100 = 1+ 2+3+4+ 5+6+ 7+ 8 х 9.
См. также ссылку из упражнения 7.2.1.1-111. Ричард Беллман (Н1сЬап( Вейшап) [АММ„ 69 (1962), 640-643[ пояснил„ как решается частный случай (а), когда операторы ограничены сложением н умножением и нельзя использовать скобки. Его метод динамического программирования можно также использовать и при решении общей задачи длн снижения количества рассматриваемых случаев. Идея состоит в определении действительных чисел, получаемых для каждого подинтервала цифр (1,..., и) для данного оператора в качестве корня дерева. Можно также сэкономить на вычислениях, отбрасывал случаи, которые для подинтервалов (1,...,8) и (2,...,9) не могут привести к целым решениям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
