Упражнения. > 19.10.Покажите структуру списков смежных вершин, построенных программой 17.9 для орграфа

> 19.11. Напишите программу, генерирующую случайные разреженные орграфы для та­
кого специально выбранного набора значений V и E, что их можно использовать для
подходящих эмпирических тестов на орграфах, построенных на базе модели со слу­
чайными ребрами.

> 19.12. Напишите программу, генерирующую случайные разреженные графы для та­кого специально выбранного набора значений V и Е, что их можно использовать для подходящих эмпирических тестов на графах, построенных на базе модели со случай­ными ребрами.

о 19.13. Напишите программу, которая генерирует орграфы путем соединения вершин, упорядоченных в решетку размера √ Vx√ V, с соседними вершинами, при этом на­правления ребер выбираются случайным образом (см. рис. 19.11).

о 19.14. Расширьте возможности программы из упражнения 19.13, добавив R дополни­тельных случайных ребер (все возможные ребра выбираются с равной вероятностью). Для больших значений R уменьшите решетку таким образом, чтобы общее число ре­бер оставалось примерно равным К Проверьте полученную программу способом, описанным в упражнении 19.11.

о 19.15. Внесите такие изменения в вашу программу из упражнения 19.14, чтобы допол­нительное ребро выходило из вершины s в вершину t с вероятностью, обратно про­порциональной евклидову расстоянию между s и t.

о 19.16. Напишите программу, которая генерирует в единичном интервале V случайных интервалов длиной d каждый, после чего строит орграф с ребром из интервала s в интервал t тогда и только тогда, когда, по меньшей мере, одна из граничных точек s попадает в t (см. упражнение 17.75). Определите, как выбрать Этаким, чтобы ожида­емое число ребер было равным Е. Протестируйте свою программу методом, описан­ным в упражнении 19.11 (для разреженных орграфов), и методом, описанным в уп­ражнении 19.12 (для насыщенных орграфов).

• 19.17. Напишите программу, которая выбирает V вершин и Е ребер из реального орг­
рафа, который вам удалось найти при выполнении упражнения 19.1. Протестируйте
свою программу, как описано в упражнениях 19.11 (для разреженных орграфов) и
19.12 (для насыщенных орграфов).

• 19.17. Напишите программу, которая с одинаковой вероятностью строит любой из
возможных орграфов с V вершинами и с E ребрами (см. упражнение 17.70). Протес­
тируйте свою программу, как описано в упражнениях 19.11 (для разреженных оргра­
фов) и 19.12 (для насыщенных орграфов).

> 19.19. Реализуйте класс, который предоставляет клиентским программам возможность
определить полустепени захода и исхода любой заданной вершины орграфа за посто­
янное время после предварительной подготовки в конструкторе, на что должно тра­
титься линейное время. Затем добавьте функции-элементы, которые возвращают число
истоков и стоков за постоянное время.

о 19.20. Воспользуйтесь программой из упражнения 19.19 с тем, чтобы найти среднее число истоков и стоков в орграфах различных типов (см. упражнение 19.11 — 19.18).

> 19.21. Покажите структуру списков смежных вершин, которая получается, когда вы
используете программу 19.1 для построения обращения орграфа

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