Часть 5. Алгоритмы на графах. новероятен). Определите, какое значение к следует выбрать, чтобы ожидаемое число ребер было равно Е

новероятен). Определите, какое значение к следует выбрать, чтобы ожидаемое число ребер было равно Е. Проведите тестирование полученной программы в соответствии с изложенным в упражнении 17.65.

о 17.72. Напишите программу, которая строит случайные графы путем соединения вер­шин, упорядоченных в виде решетки размером √ V на √ V, с соседними вершинами, при этом каждое ребро появляется с вероятностью р (см. рис. 1.2). Определите, какое значение р следует выбрать, чтобы ожидаемое число ребер было равно Е. Проведите тестирование полученной программы в соответствии с изложенным в упражнении 17.65.

о 17.73. Расширьте программу из упражнения 17.72 путем добавления R дополнитель­ных случайных ребер, вычисленных методом, реализованным программой 17.12. Для больших R сожмите решетку настолько, чтобы общее число ребер оставалось пример­но равным V.

• 17.74. Напишите программу, которая генерирует V случайных точек на плоскости,
после чего строит граф, состоящий из ребер, соединяющих все пары точек, удален­
ных друг от друга на расстояние, не превышающее d (см. рис. 17.13 и программу 3.20).
Определите, какое значение d следует выбрать, чтобы ожидаемое число ребер было
равно Е. Проведите тестирование полученной программы в соответствии с изложен­
ным в упражнении 17.65 (для низких уровней насыщенности) и в соответствии с из­
ложенным в упражнении 17.66 (для высоких уровней насыщенности).

• 17.75. Напишите программу, которая генерирует V случайных интервалов в единич­
ном интервале, каждый длиной d, затем постройте соответствующий интервальный
граф. Определите, какое значение d следует выбрать, чтобы ожидаемое число ребер
было равно Е. Проведите тестирование полученной программы в соответствии с из­
ложенным в упражнении 17.65 (для низких уровней насыщенности) и в соответствии
с изложенным в упражнении 17.66 (для высоких уровней насыщенности). Указание:
Воспользуйтесь BST-деревом (Binary Search Tree — дерево двоичного поиска).

• 17.76. Напишите программу, которая случайным образом выбирает V вершин и E ре­
бер из реального графа, который вы найдете в упражнении 17.64. Проведите тестиро­
вание полученной программы в соответствии с изложенным в упражнении 17.65 (для
низких уровней насыщенности) и в соответствии с изложенным в упражнении 17.66
(для высоких уровней насыщенности).

о 17.77. Один из способов описания транспортной системы предусматривает использо­вание множества последовательностей вершин, при этом каждая такая последователь­ность определяет путь, соединяющий соответствующие вершины. Например, последо­вательность 0-9-3-2 определяет ребра 0-9, 9-3, 3-2. Напишите программу, которая строит граф по данным из входного файла, содержащего в каждой строке одну пос­ледовательность, с использованием символических имен. Подготовьте ввод, который позволил бы вам использовать эту программу для построения графа, соответствующего схеме парижского метро.

17.78. Обобщите ваше решение упражнения 17.77 на случай, когда заданы координаты вершин и выполнены условия, сформулированные в упражнении 17.60, что позволи­ло бы вам работать с графическими представлениями графов.

о 17.79. Примените преобразования, описанные в упражнениях 17.34-17.37, к различ­ным графам (см. упражнения 17.63—17.76) и сведите в таблицу число вершин и ребер, удаленных при каждом таком преобразовании.