Упражнения. 19.30. Начертите лес DFS, который получается при применении поиска в глубину к орграфу

19.30. Начертите лес DFS, который получается при применении поиска в глубину к
орграфу

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

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

19.31. Начертите лес DFS, который получается при применении поиска к орграфу

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4, представленному в виде матрицы смежности.

Глава 19. Орграфы и ориентированные ациклические графы

о 19.32. Опишите семейство орграфов с V вершинами и E ребрами, для которых стан­дартный поиск в глубину, ориентированный на представление графа в виде смежных вершин, требует для обнаружения циклов время, пропорциональное Е.

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

> 19.34. Покажите все возможные леса орграфа

0-1 0-2 0-3 1-3 2-3,

и сведите в таблицу число древесных, обратных, поперечных и прямых ребер для каж­дого леса.

19.35. Если обозначить числа древесных, обратных, поперечных и прямых ребер, со­ответственно, через t, b, с и d, то получим t + b + с + t =E и t< V для любого поис­ка в глубину на любом орграфе с V вершинами и Е ребрами. Какие другие отноше­ния между этими переменными можно обнаружить? Какие из этих значений зависят только от свойств графов и какие из них зависят от динамических свойств поиска в глубину?

> 19.36. Докажите, что каждый исток в конкретном орграфе должен быть корнем не­
которого дерева в лесе, соответствующем любому поиску в глубину на этом орграфе.

о 19.37. Постройте связный DAG, который есть подграф графа, изображенный на рис. 19.1, за счет удаления пяти ребер (см. рис. 19.11).

19.38. Реализуйте класс орграфа, который предоставляет клиенту возможность про­верки того, что заданный орграф на самом деле есть DAG, и постройте реализацию, основанную на поиске в глубину.

о 19.39. Воспользуйтесь найденным вами решением упражнения 19.38 для (эмпиричес­кой) оценки вероятности того, что случайный орграф с V вершинами и Е ребрами представляет собой DAG, для различных типов орграфов (см. упражнения 19.11-19.18).

19.40. Проведите эмпирические исследования с целью определить относительное про­
центное содержания деревьев, обратных, поперечных и прямых ребер, когда мы про­
водим поиск в глубину на различных типах орграфов (см. упражнения 19.11—19.18).

19.41. Опишите, как построить последовательность ориентированных ребер V вершин,
для которых не существует ни поперечных, ни прямых ребер и для которых число об­
ратных ребер пропорционально V² при стандартном поиске в глубину, ориентирован­
ном на представление графа в виде списков смежных вершин.

о 19.42. Опишите, как построить последовательность ориентированных ребер V вершин, для которых не существует ни обратных, ни прямых ребер и для которых число по­перечных ребер пропорционально V² при стандартном поиске в глубину, ориентиро­ванном на представление графа в виде списков смежных вершин.

19.43. Опишите, как построить последовательность ориентированных ребер V вершин, для которых не существует ни обратных, ни поперечных ребер и для которых число прямых ребер пропорционально V² при стандартном поиске в глубину, ориентирован­ном на представление графа в виде списков смежных вершин.

о 19.44. Сформулируйте правила, соответствующие обходу Тремо лабиринта, в котором все коридоры являются односторонними.

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

• 19.12. Распространите полученные решения на упражнения 17.56 —17.60 с таким рас­четом, чтобы учитывались стрелки на ребрах (в качестве примеров используйте иллю­страции, приводимые в данной главе).