Д. Кнут - Искусство программирования том 1 (1119450), страница 105
Текст из файла (страница 105)
О. гМ21] Справедливо ли следующее утверждение: "Ориентированный граф, который является корневым и не содержит циклов н ориентировагпэых циклов, является ориентированным деревом"? 7. [М22] Справедливо ли следующее утверждение: "Ориентированный граф, удовлетворяющий условиям (а) и (Ь) из определения ориентированного дерева и не имеющий ориентированных циклов, является ориентированным деревом"? 8. [НМЕО] Изучите свойства группы авшаиарфиэмпв (аи1агпагрЛгэт дгаирэ) ориентира- ванных деревьев, т е.
групп, состоящих из всех перестановок я вершин и Луг, для которых 1п11(ек) = 1п!1(е)л, Йп(ек) = Йп(е)к. 9. [18] Указывая направления ребер, нарисуйте схему ориентированного дерева, которое соответствует свободному. дереву, показанному на рис. 30, где С вЂ э корень. 10.
[22] Ориентированное дерево с вершинами И,, .., У„можно представить в компьютере с помощью таблицы Р[Ц,..., Р[п] следующим образам. Если У) — корень, та Р[А = О; в противном случае Р[1] = Л, если дуга е[\гэ] проходит от г; к )гы (Таким образом, Р[Ц,..., Р[п[ —.это такая же таблица, как "родительская" таблица, используемая в алгоритме 2.3.3Е.) В настоящем разделе показано, как свободное дерево может быть преобразовано в ориентированное с помощью выбора произвольной вершины в качестве корня.
Следовательно, ориентированное дерево с корнем й можно, пренебрегая направлениями дуг, преобразовать в свободное дерева, а затем задать для них новые направления, получив в итоге ориентированное дерево с корнем в некоторой произвольно выбранной вершиной. Создайте алгоритм, который выполняет такое преобразование заданной таблицы Р[Ц,..., Р[п], представляющей ориентированное дерева, в результате которого таблица Р будет представлять это же свцбоднае дерево, но с корнем в вершине 1'з.
где у — заранее заданное целое число, 1 ( у' ( и. ь 11. [22] Используя условия упсс. 2.3.4.1-6. но с учетом того, что (ас,бь) — это дуга от У „ к 1'ь,, создайте алгоритм, который распечатывал бы содержимое не только свободного поддерева, но и фундаментальных циклов. [Указанне. Можно использовать алгоритм из ответа к упр. 2.3.4.1-6 в сочетании с алгоритмом из предыдущего упражнения.] 12.
[М10] В еоответствии с предложенным здесь определением ориентированного дерева и его определением, данным в начале раздела 2.3, можно ли отождествить степень узла дерева со степенью входа или сспепенью выхода соответствующей вершины? ° 13. [М24] Докажите, что если Я вЂ” корень, возможно, бесконечнвга ориентированного графа С, то С содержит ориентированное поддерево с теми же вершинами и корнем Я. (Отсюда следует, что в блок-схемах, аналогичных блок-схеме на рис. 32 из раздела 2.3.4.1, всегда можно выбрать свободное поддерево, которое действительно является ориентированным. Илсенно такое поддерево было бы показано на этой схеме, если бы мы выбрали н н Р е,з, е,'э, езо и ест вместо есз, е,э, езз и еш.) 14. [21] Пусть С вЂ” сбалансированный диграф. показанный на рис.
36, а С' — ориентированное псрдерево с вершинами 1'о, !с, 1'з и дузими еес, езс. Найдите, начиная с дуги еш, все пути Р, которьсе удовлетворяют условиям теоремы П. 15. [М20] Справедливо ли следующее выражение: "Ориентированный, связный и сбалансированный граф является строго связнымеэ ь 16. [М24] В популярном пасьянсе "Часы" обычная колода из 52 карт располагается лицевой стороной вниз в 13 стопках по четыре карты в каждой; причем 12 стопок располагаются по кругу, а стопка 13 — в центре, что, в общем, напоминает циферблат часов. Затем пасьянс раскладывается следующим образом: карта в центральной стопке переворачивается и, если ее значение равно 15 размещается возле стопки?с.
(Значения 1,2,...,13 соответствуют тузу, 2, ..., 10, валету, даме, королю.) Раскладывание нродалжается таким образом: верхняя карта из стопки 1 переворачивается и располагается рядом с ее стопкой и т. д. до тех пор, пока не будет достигнут момент, когда продолжать игру уже невозможна, так как в очередной указанной стопке больше нет карт, которые можно было бы перевернуть. (Игрок не обладает правом выбора варианта продолжения игры, так как эти правила полностью диктуют хад игры.) Игра считается выигранной, если к этому моменту все карты повернуты лицевой стороной вверх.
[См. Е. 1>. СЛепеу, Рлпелсе (Возсап; Ьее 5с БЛерагс1,.1870), 62 — 65; как говорится в книге М. ЖЛссшоге 3опез, Сашез о? Райепсе (Ьопс(оп: Ь. Прсосс 0111, 1900), СЛарсег 7, в Англии этот пасьянс называется "Пасьянсом путешественника".] Покажите, что игра выиграна тогда и только тогда, когда следующий ориентированный граф является ориентированным деревом: сгс, 1',, 11з.— вершины, ес, ез,, е ш— дуги, где е, проходит от 1з к рь, если?с — самая нижняя карта в стопке у после сдачи карт. (В частности, если самой нижней картой в стопке у является карта "у" для у ф 13, то легко видеть, что игра, определенно, будет проигрышной, так как эта карта никогда не сможет быть повернута лицевой стороной вверх.
Доказанный в настоящем упражнении результат позволяет гораздо быстрее раскладывать такой пасьянс!) 17. [МЯ2] Какова вероятность выигрыша при раскладывании пасьянса "Часы" (который описан в упр. 16) при условии, что колода тщательно перетасована? Какова вероятность того, что в точности?с карт остаются повернутыми лицевой стороной вниз в момент прекращения игры'? 18. [МЭО] Пусть С вЂ” граф с тс+ 1 вершинамн 1ш1/с,..., 1г„и пс ребрами ес,..., е . Преобразуем граф С в ориентированный граф, задав произвольное направление для каждого ребра, а затем построим матрицу А размера т х (п+ 1) +1, если ш!1(е,) = 1); а,1 = -1, если бп(е;) = г'; О в противном случае.
Пусть Ао †матри А размера т х и с удаленным О-и столбцом. а) При т = и покажите, что детерминщзт матрицы .4о равен О, если С не является свободным деревом, и равен х1, если С яеллетсл свободным деревом. Ь) Для произвольного т покажите, что детерминант матрицы АогАо равен числу свободных подлеревьев графа С (а именно. количеству вариантов выбора и ребер из гп ребер таким образом, чтобы полученвъ~й граф был свободным деревом). [Указание. Используйте условие (а) и результат упр.
1.2.3-46.] 19. [МЗ1) (Теорема о матрице, соотеетстврющеб дереву.) Пусть С вЂ” ориентированный граф с и + 1 вершинами Уо, Ъп ..., 1г . Пусть А — матрица размера (п + 1) х (и+ 1) с элементами -1с, если 1 фу и существует 1с луг от И к 1): ао = если 1 = 1 и существует 1 дуг от 1»1 к другим вершинам. (Отсюда следует, что а о+ ац + + а» = О для О < 1 < п ) Пусть Ао — это та же матрица, в которой удалены О-я строка и О-й столбец. Например, если С является ориентированным графом, который показал на рис. Зб., получим »= < — 3 — 2), а) Покажите, что если аоо = О и а„= 1 для 1 < 1 < и н если С не имеет луг, начинающихся и заканчивающихся в одной и той же вершине, то бес Ло = [С— ориентированное дерево с корнем 1о). Ь) Покажите, что в общем случае бес Ао равно количеству ориентированных поддеревьев графа С с корнем 1о (т.
е. количеству способов выбора и дуг из всех дуг графа С, поэтому полученный в результате ориентированный граф является ориентированным деревом с корнем Уо). [Указаное. Используйте метод индукции по количеству дуг] 20. [М91) Если С вЂ” неориентированный граф с и 4 1 вершинами (го,,Им пусть В— матрица размера и х п, которая для 1 < 1,1 < п определяется следующим образом: если 1 = 1 и есть Г ребер, которые соприкасаются с вершиной Ь", б„= -1, если 1 ~ 1 и вершина И смежна с вершиной 1'И о ж ~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ ~ ~ И О в противном случае.
Например, если С вЂ” граф, показанный на рис. 29, с (Уо, (ч, Ум Ъз, 12) = (.4. В, С, В, Е), то получим — 1 — 1 3 — 1 Покажите, что количество свободных поддеревьев графа С равно бес В. [Указание. Используйте упр. 18 или 19.) 21. [ВМЗ8] (Задача Т.
ван Аардене-Эренфест и Н, П де Брейна.) На рис. Зб приведен пример ориентированного графа, который является не только сбалансированным, но и регулярным (геуи1аг). Это означает, что все вершины имеют одинаковые степени входа и выхода. Пусть С вЂ” регулярный диграф с и+ 1 вершинами Ке, У!,..., У„, каждая вершина которого имеет степень входа и выхода, равную ш. (Следовательно, в общем, существуег (и+ 1)т дуг.) Пусть С', граф с (и+ 1)гп вершинами, которые соответствуют дугам графа С, и пусть У!ь — вершина графа С*, соответствующая дуге от 1'! к 1'! в графе С.
Дуга проходит от У!! к 1! и в графе С тогда и только тогда, когда й ы !'. Например, если С вЂ” ориентированный граф, показанный на рис. Зб, то граф С* представлен на рис. 37. Цепь Эйлера в графе С является цепью Гамильтона в графе С', и наоборот.
Докажите, что количество ориентированных поддеревьев графа С' в т!" +Ю~ ! раз больше количества ориентированных поддеревьев графа С. (Указоное. Используйте результат упр. 19.) Рис. 37. Диграф с дугами, который соответствует рис.
Зб (см. упр. 21). и 22. (Мйб) Пусть С вЂ” сбалансированный, ориентированный граф с вершинами 1'!, 1'г, ..., У без изолированных вершин. Пусть а равно степени выхода вершины г!. Покажите, что количество цепей Эйлера для графа С равно где Т вЂ” количество ориентированных поддеревьев графа С с корнем У!. Замечание. Множитель (о! + .. + о„), который равен количеству луг графа С, можно опустить, если цепь Эйлера (е!,,е ) считается равной (ею...,е,„,е!,...,е! !).) ь 23. (МЯЯ] (Задача Н.
Г. де Брейна.) Для каждой последователыюсти неотрицательных целых чисел х!,...,хю меньших, чем гл, допустим, что 1(х!,...,хь) — неотрицательное целое число, меггьшее, чем пз. Определим бесконечную последовательность таким образом: Хг = Хз,= ' ' ' = Хь = О; Х ег+г = ~(Хзеы..., Х„з.г ), где и > О. Для какого количества из этих т возможных функи(зй,г" пОследоватЕЛЬнпеть будет периодичной с<b>Текст обрезан, так как является слишком большим</b>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
