Глава 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 должны быть
указаны только один раз, кроме того, вы должны удалить параллельные ребра.