Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 17. Свойства и типы графов. разделе 17.8, и более подробных исследований, выполняемых в части 8, следует, что мы должны признать то
разделе 17.8, и более подробных исследований, выполняемых в части 8, следует, что мы должны признать то, что представляется нам непреодолимым барьером между задачами, для решения которых, по-видимому, требуется экспоненциальное время (такие как задача поиска гамильтонова пути и многие другие реальные задачи), и задачами, о которых нам известно, что алгоритмы их решения гарантированно выполняются за полиномиальное время (такие как задача поиска эвклидова пути и многие другие практические задачи). В данной книге основной нашей целью является разработка эффективных алгоритмов решения задач второго из указанных выше классов. Упражнения > 17.85. В стиле упражнения 17.17 покажите трассировку рекурсивных вызовов (и пропущенные вершины), когда программа 17.16 производит поиск пути из вершины 0 в вершину 5 в графе 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. 17.86. В соответствии с изложенным в тексте, внесите изменения в рекурсивную фун 17.87. Выполните упражнение 17.86, добавив аргумент рекурсивной функции, позво о 17.88. Используя метод, описанный в тексте, постройте реализацию класса sPATH, обеспечивающего выполнение общедоступной функции-элемента, которая вызывает клиентскую функцию для каждого ребра на пути из v в w, если такой путь существует. о 17.89. Внесите такие изменения в программу 17.16, которые позволили бы ей принимать третий аргумент d и проверять существование пути, соединяющего вершины и и v, длина которого больше d. В частности, значение search(v, v, 2) должно быть ненулевым в том и только том случае, когда v содержится в некотором цикле. • 17.90. Проведите эксперименты с целью определения эмпирическим путем вероятности того, что программа 17.16 найдет путь между двумя наудачу выбранными вершинами в различных графах (см. упражнения 17.63-17.76) и вычислите среднюю длину пути, найденного для различных типов графов. о 17.91. Рассмотрим графы, заданные следующими четырьмя наборами ребер: 0-1 0-2 0-3 1-3 1-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8 0-1 0-2 0-3 1-3 0-3 2-5 5-6 3-6 4-7 4-8 5-8 5-9 6-7 6-9 8-8 0-1 1-2 1-3 0-3 0-4 2-5 2-9 3-6 4-7 4-8 5-8 5-9 6-7 6-9 7-8 4-1 7-9 6-2 7-3 5-0 0-2 0-8 1-6 3-9 6-3 2-8 1-5 9-8 4-5 4-7 Какие из этих графов содержат эйлеровы циклы? Какие из них содержат гамильтоновы циклы? о 17.92. Сформулируйте такие необходимые и достаточные условия, что ориентированный граф, удовлетворяющий этим условиям, содержит (ориентированный) эйлеров цикл. 17.93. Докажите, что каждый связный неориентированный граф содержит двухпроходный эйлеров цикл. Часть 5. Алгоритмы на графах 17.94. Внесите изменение в доказательство свойства 17.4 с тем, чтобы оно работало и в случае графов с параллельными ребрами и петлями. > 17.95. Покажите, что если добавить еще один мост, то задача о Кенигсбергских мостах получит решение. • 17.96. Докажите, что в связном графе имеется эйлеров путь из v в w только в том слу • 17.97. Воспользуйтесь упражнением 17.96, чтобы разработать эффективный рекурсив
> 17.98. Приведите пример, в котором граф, оставшийся после первого обращения к > 17.99. Опишите, какие изменения следует внести в программу 17.19, с расчетом, что 17.100. Дайте полное доказательства методом индукции утверждения, что алгоритм поиска эйлерова пути, выполняемый за линейное время, который описан в тексте книги и реализован в программе 17.19, правильно находит эйлеров цикл. о 17.101. Найдите число графов с V вершинами, которые содержат эйлеров цикл, для максимального числа V, для которого вы способны выполнить реальные вычисления. • 17.102. Выполните эксперименты для различных графов с тем, чтобы эмпирическим о 17.103. Напишите программу, которая вычисляет последовательность из 2" + п — 1 бит, в которой никакие две последовательности из п следующих подряд битов не совпадают. (Например, для п = 3 последовательность 0001110100 обладает таким свойством.) Примечание: Найти эйлеров цикл в орграфе Де-Бруйна. > 17.104. Покажите в стиле рис. 17.19 трассу рекурсивных вызовов (и пропущенные 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. о 17.105. Внесите в программу 17.17 изменения с тем, чтобы она могла распечатать гамильтонов цикл, если она его найдет. • 17.106. Найдите гамильтонов цикл в графе 1-2 2-5 4-2 2-6 0-8 3-0 1-3 3-6 1-0 1-4 4-0 4-6 6-5 2-6 6-9 9-0 3-1 4-3 9-2 4-9 6-9 7-9 5-0 9-7 7-3 4-5 0-5 7-8, либо показать, что такового не существует.
|