Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 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.16, с тем, чтобы она могла распечатывать трас
сировки, аналогичные показанным на рис. 17.17, используя для этой цели глобальную
переменную.
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 только в том слу
чае, когда он содержит ребро, инцидентное v, удаление которого не нарушает связ
ности графа (если не учитывать возможности, что после этого вершина v станет изо
лированной).
• 17.97. Воспользуйтесь упражнением 17.96, чтобы разработать эффективный рекурсив
ный метод поиска эйлерова цикла в графе, в котором есть такой цикл. Помимо ба
зовых функций АТД графа, вы можете воспользоваться классами, рассматриваемы
ми в данной главе, которые определяют степени вершин (см. программу 17.11) и
проверяют, существует ли путь между двумя заданными вершинами (см. программу
17.16). Постройте реализацию и протестируйте полученную программу как на разре
женных, так и на насыщенных графах.
> 17.98. Приведите пример, в котором граф, оставшийся после первого обращения к
функции path из программы 17.19, будет несвязным (в графе, содержащем эйлеров
цикл).
> 17.99. Опишите, какие изменения следует внести в программу 17.19, с расчетом, что
бы ее можно было использовать для определения за линейное время, имеется ли в за
данном графе эйлеров цикл.
17.100. Дайте полное доказательства методом индукции утверждения, что алгоритм поиска эйлерова пути, выполняемый за линейное время, который описан в тексте книги и реализован в программе 17.19, правильно находит эйлеров цикл.
о 17.101. Найдите число графов с V вершинами, которые содержат эйлеров цикл, для максимального числа V, для которого вы способны выполнить реальные вычисления.
• 17.102. Выполните эксперименты для различных графов с тем, чтобы эмпирическим
путем определить среднюю длину пути, найденного при первом вызове функции path
в программе 17.19 (см. упражнения 17.63-17.76). Вычислите вероятность того, что этот
путь является циклом.
о 17.103. Напишите программу, которая вычисляет последовательность из 2" + п — 1 бит, в которой никакие две последовательности из п следующих подряд битов не совпадают. (Например, для п = 3 последовательность 0001110100 обладает таким свойством.) Примечание: Найти эйлеров цикл в орграфе Де-Бруйна.
> 17.104. Покажите в стиле рис. 17.19 трассу рекурсивных вызовов (и пропущенные
вершины), когда программа 17.16 находит гамильтонов цикл в графе
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,
либо показать, что такового не существует.