Глава 17, Свойства и типы графов. дой вершины. Добавьте в общедоступную функцию-элемент degree,которая возвра­щает степень заданной вершины.

дой вершины. Добавьте в общедоступную функцию-элемент degree, которая возвра­щает степень заданной вершины.

17.43. Выполните упражнение 17.43 для представления графа в виде списков смежных вершин.

> 17.44. Включите в таблицу 17.1 строку, соответствующую задаче определения числа изолированных вершин графа. Дайте обоснование вашего ответа в виде реализаций функции для каждого из трех представлений, указанных в таблице.

о 17.45. Включите в таблицу 17.1 строку, соответствующую задаче, определяющей, со­держит ли заданный орграф вершину с полустепенью захода V и полустепенью выхо­да 0. Дайте обоснование вашего ответа в виде реализаций функции для каждого из трех представлений, указанных в таблице. Примечание: Вхождение для представления фа-фа в виде матрицы смежности должно составлять V.

17.46. Воспользуйтесь двухсвязными списками смежных вершин с перекрестными
связями, в соответствии с изложенным в тексте, для реализации функции remove, вы­
полняющей операцию remove edge (удалить ребро) за постоянное время на АТД графа,
для представления которого используются списки смежных вершин (программа 17.9).

17.47. Добавьте функцию remove, выполняющую операцию remove vertex (удалить вер­
шину) в класс двухсвязного графа, представленного в виде списков связных вершин,
в соответствии с изложенным в предыдущем упражнении.

о 17.48. В соответствии с изложенным в тексте, внесите изменения в решение задачи 17.16, позволяющие пользоваться динамическими хеш-таблицами, с тем, чтобы опера­ции insert edge (вставить ребро) и remove edge (удалить ребро) выполнялись за постоян­ное время.

17.49. Добавьте в класс графа, использующего для своего представления списки смеж­
ных вершин (программа 17.9), таблицу символов, позволяющую игнорировать дубли­
каты ребер, с тем, чтобы он представлял графы, а не мультиграфы. Воспользуйтесь ди­
намическим хешированием при реализации таблицы символов с тем, чтобы
полученные вами реализации занимали пространство памяти, пропорциональное Е, и
выполняли операции, осуществляющие вставку, поиск и удаление ребра за постоян­
ное время (в среднем, с амортизацией расходов на реализацию).

17.50. Разработайте класс мультиграфа на основе представления мультиграфов в виде
векторов таблицы символов (по одной таблице символов на каждую вершину, содер­
жащую список смежных ребер). Воспользуйтесь динамическим хешированием при ре­
ализации таблицы символов с тем, чтобы полученная реализация использовала про­
странство памяти, пропорциональное Е, и выполняла операции вставки, поиска и
удаления ребра за постоянное время (в среднем, с амортизацией расходов на реали­
зацию).

17.51. Разработайте АТД графа, ориентированный на статические графы, основанные
на использовании конструктора, который принимает вектор ребер в качестве аргумен­
та и использует базовый АДТ графов для построения графов. (Подобного рода реа­
лизация может оказаться полезной при сравнении по производительности с реализа­
циями, построенными в упражнениях 17.52-17.55.)

17.52. Разработайте реализацию конструктора, описанную в упражнении 17.51, кото­
рая использует компактное представление графа, основанное на следующих структу­
рах данных: