Главная » Просмотр файлов » Д. Кнут - Искусство программирования том 1

Д. Кнут - Искусство программирования том 1 (1119450), страница 105

Файл №1119450 Д. Кнут - Искусство программирования том 1 (Д. Кнут - Искусство программирования том 1) 105 страницаД. Кнут - Искусство программирования том 1 (1119450) страница 1052019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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>.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее