![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Упражнения. > 20.35.Проведите анализ рабочих характеристик реализации алгоритма Прима в лоб, о которой шла речь в начале данного раздела при обсуждении
> 20.35. Проведите анализ рабочих характеристик реализации алгоритма Прима " в лоб", о которой шла речь в начале данного раздела при обсуждении графа с V вершинами. Указание: При решении этой задачи может пригодиться комбинаторная сумма: о 20.36. Выполните упражнение 20.35 применительно к графам, у которых все вершины имеют одни и те же степени с фиксированным значением /. о 20.37. Выполните упражнение 20.35 применительно к разреженным графам общего вида, содержащих V вершин и Е ребер. Поскольку время выполнения зависит от весов ребер и степеней вершин, проведите анализ худшего случая. Приведите в качестве примера семейство графов, для которого ваши предположения относительно граничного значения для худшего случая подтверждаются. 20.38. Представьте в стиле рис. 20.8 результаты построения дерева MST с помощью алгоритма Прима для сети, определение которой дано в упражнении 20.26. • 20.39. Опишите семейство графов с V вершинами и E ребрами, для которого оценка времени выполнения алгоритма Прима, использующего поиск по приоритетам, подтверждается для худшего случая. ••20.40. Разработайте походящий генератор случайных графов с V вершинами и Е ребрами, такой, что время выполнения алгоритма Прима, использующего поиск по приоритетам (программа 20.7), будет нелинейным. о 20.41. Внесите такие изменения в программу 20.7, чтобы она работала так же, как и программа 18.8, в части хранения в бахроме всех ребер, инцидентных вершинам дерева. Проведите эмпирические исследования с целью сравнить полученную вами реализацию с программой 20.7 на примере различных взвешенных графов (см. упражнения 20.9-20.14). 20.42. Постройте реализацию очереди с приоритетами, пользуясь интерфейсом, оп 20.43. Воспользуйтесь функцией priority__queue из библиотеки STL для реализации ин 20.44. Предположим, что вы используете реализацию очереди с приоритетами, кото о 20.45. Ребро минимального остовного дерева, удаление которого из графа приводит к увеличению веса дерева MTS, называется критическим ребром. Покажите, как найти все критические ребра в графе за время, пропорциональное E lgV Часть 5. Алгоритмы на графах
> 20.47. Проведите эмпирические исследования на различных взвешенных графах с целью оценки эффекта от использования в программе 20.7 реализации очереди с приоритетами в виде турнира индексно-сортирующего дерева (см. упражнение 9.53) вместо программы 9.12 (см. упражнения 20.9-20.14). 20.48. Проведите эмпирические исследования на различных взвешенных графах с це 20.49. Проведите эмпирические исследования на различных взвешенных графах с це 20.50. Проведите эмпирические исследования на различных взвешенных графах с це 20.51. Проведите эмпирические исследования с целью анализа зависимости результатов 20.52. Напишите клиентскую программу, которая выполняет графическую анимацию
|