Упражнения. > 19.46.Что собой представляет транзитивное замыкание орграфа, который состоит только из направленного цикла с V вершинами?

> 19.46. Что собой представляет транзитивное замыкание орграфа, который состоит
только из направленного цикла с V вершинами?

19.47. Сколько ребер содержит транзитивное замыкание орграфа, который состоит только из простого ориентированного пути с V вершинами?

> 19.48. Постройте транзитивное замыкание неориентированного графа

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

• 19.49. Покажите, как можно построить орграф с V вершинами и Е ребрами, облада­ющий тем свойством, что число ребер в транзитивном замыкании пропорционально t, для любого t, принимающего значения в диапазоне между Е и V². Как обычно, пред­полагаем, что Е > V.

Глава 19. Орграфы и ориентированные ациклические графы

19.50. Выведите формулу числа ребер в транзитивном замыкании орграфа, представ­
ляющего собой ориентированный лес, как функцию структурных свойств леса.

19.51. Представьте в стиле рис. 19.15 процесс вычисления транзитивного замыкания
орграфа

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4

путем многократного возведения в квадрат.

19.52. Представьте в стиле рис. 19.16 процесс вычисления транзитивного замыкания
орграфа

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4

с применением алгоритма Уоршалла.

о 19.53. Найдите семейство разреженных орграфов, для которых прогон усовершен­ствованной версии алгоритма Уоршалла для вычисления транзитивного замыкания (программа 19.3) производится за время, пропорциональное VN.

о 19.54. Найдите разреженный орграф, ддя которого прогон усовершенствованной вер­сии алгоритма Уоршалла для вычисления транзитивного замыкания (программа 19.3) производится за время, пропорциональное V³.

о 19.55. Разработайте базовый класс, из которого вы можете получить производные классы, которые реализуют как алгоритм Уоршалла, так и алгоритм Флойда. (Это уп­ражнение представляет собой версию упражнения 19.56 для тех, кто лучше знаком с абстрактными типами данных, чем с абстрактной алгеброй).

• 19.56. Воспользуйтесь аппаратом абстрактной алгебры для разработки родового алго­
ритма, который заключает в себе как алгоритм Уоршалла, так и алгоритм Флойда.
(Данное упражнение есть версия упражнения 19.55 для тех, кто лучше ознакомлен с
абстрактной алгеброй, чем с абстрактными типами данных).

о 19.57. Представьте в стиле рис. 19.16 разработку матрицы всех кратчайших путей для примера графа, изображенного на этом рисунке, для чего воспользуйтесь алгоритмом Флойда.

19.58. Является ли произведение двух симметричных булевых матриц симметричным?
Сопроводите ваш ответ доказательством.

19.59. Введите в программы 19.3 и 19.4 общедоступные функции-элементы, позволя­
ющие клиентским программам использовать объекты tc для определения числа ребер
в транзитивном замыкании.

19.60. Разработайте способ подсчета числа ребер в транзитивном замыкании и его мо­
дификации при добавлении и удалении ребер. Покажите, какие затраты влекут за со­
бой добавления и удаления ребер в соответствии с вашей схемой.

> 19.61. Введите в программы 19.3 и 19.4 общедоступную функцию-элемент, которая возвращает вектор, индексированный именами вершин, показывающий, какие верши­ны достижимы из данной вершины.

о 19.62. Проведите эмпирические исследования с целью определить число ребер в тран­зитивном замыкании различных типов орграфов (см. упражнения 19.11—19.18).

• 19.63. Выполните исследование представления графа в виде битовой матрицы, опи­
сание которой дано в упражнении 17.23. Какой из методов вы можете ускорить в В