Глава 18. Поиск на графе. 18.23.Дайте описание семейства графов с V вершинами, для которого на выполне­ние стандартного DFS на матрице смежности с целью обнаружения циклов

18.23. Дайте описание семейства графов с V вершинами, для которого на выполне­ние стандартного DFS на матрице смежности с целью обнаружения циклов затрачи­вается время, пропорциональное V².

> 18.24. Постройте реализацию класса определения связности из программы 18.4 как
производного от класса поиска на графе, подобного программе 18.3.

> 18.25. Укажите, какие изменения следует внести в программу 18.5, чтобы она была
способна вычислить двусторонний эйлеров цикл, который совершает обход взад и
вперед прямых, а не обратных ребер.

• 18.26. Внесите в программу 18.5 такие изменения, чтобы она всегда могла вычислить двухпроходной эйлеров цикл, который, аналогично показанному на рис. 18.14, может быть начерчен таким образом, что не пересекает сам себя ни в одной вершине. На­пример, если бы поиск, представленный на рис. 18.14, должен был пройти по ребру 4-3 перед тем, как пройти по ребру 4-7, то цикл пересек бы сам себя; ваша задача заключается в том, чтобы добиться того, чтобы алгоритм избегал подобного рода си­туаций.

18.27. Разработайте версию программы 18.5, которая сортирует все ребра в порядке
двухпроходного эйлерова цикла. Ваша программа должна возвратить вектор ребер, ко­
торый соответствует двухпроходному эйлерову циклу.

18.28. Покажите, что граф принадлежит к числу раскрашиваемых двумя цветами тогда
и только тогда, когда он не содержит нечетных циклов. Указание: Докажите методом
индукции, что программа 18.6 способна определить, является ли любой заданный граф
раскрашиваемым двумя цветами.

о 18.29. Объясните, почему подход, использованный в программе 18.6, не допускает обобщения, которое позволило бы получить эффективный метод определения, явля­ется ли конкретный граф раскрашиваемым тремя цветами.

18.30. Большая часть графов не относится к категории раскрашиваемых двумя цве­
тами, причем поиск в глубину во многих случаях быстро обнаруживает этот факт. Про­
ведите эмпирические испытания с целью определения числа ребер, исследованных
программой 18.6, на графах различных размеров и построенных по различным моде­
лям (см. упражнения 17.64—17.76).

о 18.31. Докажите, что в каждом связном графе имеются вершины, удаление которых не нарушает связности графа, и напишите функцию DFS, которая обнаруживает та­кие вершины. Указание: Рассмотрите листья дерева DFS.

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