Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. > 17.61. в тех случаях, когда для построения случайных графов со степенью насыщенности а V мы используем программу 17.12
|
|
> 17.61. в тех случаях, когда для построения случайных графов со степенью насыщенности а V мы используем программу 17.12, какую часть генерируемых ребер составляют петли?
РИСУНОК 17.16. ГРАФЫ ДЕ-БРУЙНА
Орграф Де-Бруйна порядка п содержит 2" вершин, ребра исходят из вершины i в вершины 2/ mod п и (2/ + 1) mod 2" для всех i На рисунке показаны служащие основой орграфов Де-Бруйна неориентированные графы порядка 6, 5, 4 и 3 (сверху вниз).
Глава 1 7. Свойства и типы графов
• 17.62. Вычислите ожидаемое число построенных параллельных ребер при условии, что
для генерации случайных графов с V вершинами и насыщенностью а мы используем
программу 17.12. Воспользуйтесь результатами этих вычислений для построения кри
вых, показывающих в виде функции от насыщенности а, какую часть от общего чис
ла ребер составляют параллельные ребра при V= 10, 100 и 1000.
17.63. Воспользуйтесь функцией mapиз библиотеки STL для разработки реализации класса ST, альтернативной реализации, представленной программой 17.15.
• 17.64. Найдите большой неориентированный граф в какой-нибудь динамической пред
метной области, возможно, граф, основанный на данных о связности узлов сети, либо
граф со степенями разделения, определенный соавторами на множестве библиофафи
ческих списков или актерами на множестве кинофильмов.
> 17.65. Напишите программу, которая генерирует разреженные случайные графы для
правильно выбранных значений V и E и печатает, какое пространство памяти исполь
зуется для представления графа и какое время потребовалось для его построения. Про
ведите тестирование разработанной программы с использованием класса разреженно
го графа (программа 17.9) и генератора случайных графов (программа 17.12) с тем,
чтобы вы могли применять обоснованные эмпирические критерии к графам, постро
енным на базе этой модели.
> 17.66. Напишите программу, которая генерирует разреженные случайные графы для
удачно подобранных множеств значений V и Е и печатает, какое пространство памя
ти используется для представления графа и какое время потребовалось для его пост
роения. Проведите тестирование программы с использованием класса насыщенного
графа (программа 17.7) и генератора случайных графов (программа 17.13) с тем, чтобы
вы могли применять обоснованные эмпирические критерии к графам, построенным
на базе этой модели.
• 17.67. Вычислите среднеквадратическое отклонение числа ребер, построенных программой 17.13.
• 17.68. Напишите программу, которая строит каждый возможный граф с точно такой
же вероятностью, что и программа 17.13, но в то же время затрачивает время и про
странство памяти, пропорциональное У+Е, но не V 2. Проведите тестирование полу
ченной программы в соответствии с изложенным в упражнении 17.65.
о 17.69. Напишите программу, которая строит с равной вероятностью каждый возможный граф с точно такой же вероятностью, что и программа 17.12, но в то же время затрачивает время и пространство памяти, пропорциональное Е, даже если степень насыщенности графа близка к 1. Проведите тестирование полученной программы в соответствии с изложенным в упражнении 17.66.
• 17.70. Напишите программу, которая строит с равной вероятностью каждый возмож
ный граф с V вершинами и Е ребрами (см. упражнение 17.9). Проведите тестирова
ние полученной программы в соответствии с изложенным в упражнении 17.65 (для
низких уровней насыщенности) и в соответствии с изложенным в упражнении 17.66
(для высоких уровней насыщенности).
о 17.71. Напишите программу, которая строит случайные орграфы путем соединения вершин, упорядоченных в виде решетки размером √ V на √ V, с соседними вершинами (см. рис. 1.2), при этом к дополнительных ребер соединяют каждую вершину со случайно выбранной вершиной назначения (выбор любой вершины назначения рав-