![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Упражнения. > 19.10.Покажите структуру списков смежных вершин, построенных программой 17.9 для орграфа
> 19.10. Покажите структуру списков смежных вершин, построенных программой 17.9 для орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Часть 5. Алгоритмы на графах
> 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.17. Напишите программу, которая с одинаковой вероятностью строит любой из > 19.19. Реализуйте класс, который предоставляет клиентским программам возможность о 19.20. Воспользуйтесь программой из упражнения 19.19 с тем, чтобы найти среднее число истоков и стоков в орграфах различных типов (см. упражнение 19.11 — 19.18). > 19.21. Покажите структуру списков смежных вершин, которая получается, когда вы 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. Глава 19, Орграфы и ориентированные ациклические графы о 19.22. Опишите обращение карты. 19.23. Разработайте класс орграфа, который предоставляет клиентам возможность не 19.24. Постройте альтернативную реализацию класса, построенного в упражнении > 19.25. Опишите семейство сильно связанных орграфов с V вершинами, не содержащих (простых) направленных циклов длиной больше 2. о 19.26. Получите сильные компоненты и ядро DAG орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. о 19.27. Получите ядро DAG решеточного орграфа, показанного на рис. 19.3. 19.28. Какое число графов имеют V вершин, каждая из которых имеет степень исхода, равную k? • 19.29. Какое значение принимает ожидаемое число различных представлений случайного орграфа в виде списков смежных вершин? Указание: Разделите общее число возможных представлений на общее число орграфов.
|