Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. > 17.17.Постройте представления трех графов, изображенных на рис
|
|
> 17.17. Постройте представления трех графов, изображенных на рис. 17.2, в виде мат
риц смежности.
о 17.18. Постройте реализацию функции show для независимого от представления графа пакета io из программы 17.4, которая выполняет распечатку двухмерную матрицу нулей и единиц, подобную той, что приводится на рис. 17.8. Примечание: Вы не должны зависеть от итератора, который порождает вершины в порядке следования их индексов.
17.19. Пусть задан некоторый граф; исследуйте другой граф, идентичный первому за исключением того, что имена (соответствующие целочисленные значения) вершин заменены местами. Как матрицы смежности этих двух графов соотносятся друг с другом?
> 17.20. Добавьте функцию edge в АТД графа, которая позволит клиентам проверять, существует ли ребро, соединяющие две заданные вершины, и постройте реализацию, ориентированную на представление графа в виде матрицы смежности.
о 17.21. Добавьте в АТД графа функции, которые предоставляют клиентам возможность включать и удалять вершины, и постройте реализацию, ориентированную на представление графа в виде матрицы смежности.
> 17.22. Внесите изменения в программу 17.7, расширенную в соответствии с условия
ми, сформулированными в упражнении 17.20, с целью снижения требований, предъяв
ляемых этой программой к пространству памяти, примерно наполовину, благодаря
тому, что в массив не включаются вхождения a[v][w], для которых w больше, чем у.
17.23. Внесите изменения в программу 17.7, расширенную в соответствии с условиями, сформулированными в упражнении 17.20, с тем, чтобы на компьютере, слово которого состоит из В битов, граф с V вершинами был представлен примерно V2/B (вместо V2) словами. Проведите эмпирические испытания с целью оценки влияния, оказываемого подобного рода упаковкой битов в слова, на время выполнения операций АТД.
Часть 5, Алгоритмы на графах
| 17.24. Опишите, что произойдет, если в момент вызова конструктора, используемо го в программе 17.7, имеет место недостаток памяти для размещения матрицы смеж ности, и внесите в программные коды необходимые изменения, позволяющие спра виться с возникающей при этом ситуацией. 17.25. Разработайте версию программы 17.7, которая использует единственный век тор, содержащий V2 элементов. о 17.26. Предположим, что имеется группа из к вершин, индексы которых представляют собой последовательные целые числа. Как по виду матрицы смежности определить, образует ли эта группа вершин клику? Напишите функцию клиентского АТД, которая за время, пропорциональное V2, находит максимальную группу вершин с последовательными индексами, которые образуют клику. 17.4. Представление графа в виде списка |