![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. новероятен). Определите, какое значение к следует выбрать, чтобы ожидаемое число ребер было равно Е
о 17.72. Напишите программу, которая строит случайные графы путем соединения вершин, упорядоченных в виде решетки размером √ V на √ V, с соседними вершинами, при этом каждое ребро появляется с вероятностью р (см. рис. 1.2). Определите, какое значение р следует выбрать, чтобы ожидаемое число ребер было равно Е. Проведите тестирование полученной программы в соответствии с изложенным в упражнении 17.65. о 17.73. Расширьте программу из упражнения 17.72 путем добавления R дополнительных случайных ребер, вычисленных методом, реализованным программой 17.12. Для больших R сожмите решетку настолько, чтобы общее число ребер оставалось примерно равным V. • 17.74. Напишите программу, которая генерирует V случайных точек на плоскости, • 17.75. Напишите программу, которая генерирует V случайных интервалов в единич • 17.76. Напишите программу, которая случайным образом выбирает V вершин и E ре о 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) и сведите в таблицу число вершин и ребер, удаленных при каждом таком преобразовании.
|