Часть 5. Алгоритмы на графах. > 19.98.Приведите пример леса DFS и обратной топологической сортировки, которые получаются в результате выполнения стандартного поиска в глубину с неявным

> 19.98. Приведите пример леса DFS и обратной топологической сортировки, которые
получаются в результате выполнения стандартного поиска в глубину с неявным обра­
щением на представлении в виде списков смежных вершин (с нумерацией при обхо­
де в обратном порядке) следующего графа DAG:

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

(см. программу 19.7).

• 19.99. Пусть задан некоторый DAG, существует ли топологическая сортировка, ко­
торую нельзя получить путем применения алгоритма, построенного на базе поиска в
глубину, независимо от порядка выбора вершин, смежных с заданной? Обоснуйте свой
ответ доказательством.

> 19.100. Покажите в стиле рис. 19.26 процесс топологической сортировки графа DAG

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

с помощью алгоритма, использующего очередь истоков (программа 19.8).

> 19.101. Приведите пример топологической сортировки, которая получается, когда в примере, представленном на рис. 19.25, в качестве структуры данных используется стек, а не очередь.

• 19.102. Пусть задан некоторый граф DAG, существует ли топологическая сортиров­
ка, которую нельзя получить путем применения алгоритма, построенного на базе по­
иска в глубину, независимо от дисциплины, реализуемой очередью? Обоснуйте свой
ответ доказательством.

19.103. Измените алгоритм топологической сортировки на базе очереди истоков с та­ким расчетом, чтобы можно было пользоваться обобщенной очередью. Воспользуйтесь модифицированным алгоритмом с очередью LIFO (Last In First Out - последним при­был, первым обслужен), со стеком и рандомизированной очередью.

> 19.104. Воспользуйтесь программой 19.8 для построения реализации класса, осуще­ствляющего проверку наличия циклов в заданном графе DAG (см. упражнение 19.75).

о 19.105. Преобразуйте алгоритм топологической сортировки с использованием очереди истоков в алгоритм, использующий очередь стоков для выполнения обратной тополо­гической сортировки.

19.106. Напишите программу, которая обобщает все возможные топологические упо­
рядочения заданного графа DAG либо, если число таких упорядочений превышает
границу, заданную в качестве аргумента, печатает это число.

19.107. Напишите программу, которая преобразует любой орграф с V вершинами и
Е ребрами в графе DAG путем выполнения топологической сортировки на основе по­
иска в глубину и изменения ориентации любого встреченного обратного ребра. Дока­
жите, что эта стратегия всегда приводит к созданию DAG.

•• 19.108. Напишите программу, которая осуществляет построение любого DAG с V вер­шинами и Е ребрами с равной вероятностью (см. упражнение 17.70).

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