Глава 18. Поиск на графе. 18.35.Докажите, что каждая вершина любого графа принадлежит в точности одной реберно-связной компоненте.

18.35. Докажите, что каждая вершина любого графа принадлежит в точности одной реберно-связной компоненте.

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

> 18.37. Рассмотрим граф

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

Вычертите дерево стандартного DFS на списках смежных вершин. Воспользуйтесь им для поиска точек сочленения и двусвязных компонент.

> 18.38. Выполните предыдущее упражнение с применением дерева стандартного DFS
на списках смежных вершин.

18.39. Докажите, что каждое ребро графа есть либо мост, либо оно принадлежит в точ­ности одной двусвязной компоненте.

• 18.40. Докажите, что любой граф без точек сочленения является двусвязным. Указа­
ние: Если задана пара вершин s и t и путь, который их соединяет, воспользуйтесь тем
фактом, что ни одна из вершин этого пути не есть точка сочленения при построении
двух непересекающихся путей, соединяющих вершины s и t.

18.41. Пользуясь программой 18.2, постройте класс для определения, является ли граф двухсвязным, воспользовавшись алгоритмом решения " в лоб", который выполняется за время, пропорциональное V(V+E). Указание: Если перед началом поиска отметить ту или иную вершину как уже просмотренную, ее можно эффективно удалить из графа.

о 18.42. Распространите свое решение на упражнение 18.41 с тем, чтобы построить класс, который определяет, является ли заданный граф 3-связным. Выведите форму­лу, позволяющую получить приближенное значение числа раз, когда ваша программа исследует ребро графа, как функцию от V и Е.

18.43. Покажите, что корень дерева DFS есть точка сочленения тогда и только тог­да, когда у него имеется два или большее число (внутренних) потомков.

• 18.44. Пользуясь программой 18.2, постройте класс, который выполняет распечатку
двусвязных компонент графа.

18.45. Чему равно минимальное число ребер, которое должно содержаться в любом
двусвязном графе с К вершинами?

18.46. Внесите изменения в программу 18.7 с тем, чтобы упростить задачу определе­
ния, обладает ли заданный граф свойством реберной связности (возврат, как только
она обнаружит мост, если граф не реберно-связный), и снабдите ее инструментальны­
ми средствами, позволяющими отслеживать число исследованных ребер. Проведите
эмпирическую проверку с целью определения связанных с этим затрат на примерах
графов различных размеров, в основу которых положены различные модели графов
(упражнения 17.64-17.76).

о 18.47. На основе программы 18.2 постройте производный класс, позволяющий кли­ентским программам создавать объекты, которым известны числа точек сочленения, мостов и двусвязных компонентов графа.

• 18.48. Выполните эксперимент с целью определения эмпирическим путем средних зна­
чений количественных оценок, описанных в упражнении 18.47, для графов различных раз­
меров, в основу которых положены различные модели графов (упражнения 17.64-17.76).

Часть 5. Алгоритмы на графах

18.49. Определите реберную совместимость и вершинную совместимость графа 0-1 0-2 0-8 2-1 2-8 8-1 3-8 3-7 3-6 3-5 3-4 4-6 4-5 5-6 6-7 7-8.