Упражнения. > 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. Постройте реализацию очереди с приоритетами, пользуясь интерфейсом, оп­
ределенным в программе 9.12, в программе 20.7 (так что возможно использование лю­
бой реализации этого интерфейса).

20.43. Воспользуйтесь функцией priority__queue из библиотеки STL для реализации ин­
терфейса очереди с приоритетами, который применяется в программе 20.7.

20.44. Предположим, что вы используете реализацию очереди с приоритетами, кото­
рая поддерживает сортированные списки. Каким будет время выполнения в худшем
случае для графа с V вершинами и с Е ребрами с точностью до постоянного множи­
теля? В каких случаях этот метод будет полезен, если вообще будет когда-либо поле­
зен? Обоснуйте ответ.

о 20.45. Ребро минимального остовного дерева, удаление которого из графа приводит к увеличению веса дерева MTS, называется критическим ребром. Покажите, как най­ти все критические ребра в графе за время, пропорциональное E lgV

Часть 5. Алгоритмы на графах