Главная страница
Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Глава 17. Свойства и типы графов. о 17.80.Постройте реализацию конструктора для программы 17.1, которая позволяет клиентам строить граф разделения без необходимости вызова функции для каждого
о 17.80. Постройте реализацию конструктора для программы 17.1, которая позволяет клиентам строить граф разделения без необходимости вызова функции для каждого неявного ребра. То есть, количество вызовов функции, необходимых клиенту, чтобы построить граф, должно быть пропорционально сумме размеров групп. Разработайте эффективную реализацию этого модифицированного АТД (основанного на структурах данных с использованием групп, но без использования неявных ребер).
17.81. Определите строгую верхнюю границу числа ребер любого графа разделения для N различных групп с к человек в каждой группе.
> 17.82. Сделайте чертеж графа в стиле рис. 17.16, который содержит V вершин, пронумерованных от 0 до V— 1, и ребра, соединяющие вершину i с вершиной [i/2] для V= 8, 16 и 32.
17.83. Внесите изменения в интерфейс АТД из программы 17.1, который позволил бы клиентам использовать символьные имена вершин и имена ребер в виде пар экземп ляров обобщенного типа Vertex. Полностью скройте представление, использующее ин дексацию именами вершин и АТД с таблицей символов, от клиентских программ.
17.84. Добавьте в интерфейс АТД функцию из упражнения 17.83, которая поддержи вает операцию объединить (join) на графах, и постройте реализации, генерирующие представления графов в виде матрицы смежности и списков смежных вершин. При мечание: Любая вершина или ребро любого графа должны быть указаны в операции join, но вершины, которые фигурируют в обоих графах, в операции join должны быть указаны только один раз, кроме того, вы должны удалить параллельные ребра.
|