Упражнения. > 19.75.Постройте реализацию класса DFS, предназначенную для использования кли­ ентскими программами с целью проверки на наличие в графе DAG циклов.

> 19.75. Постройте реализацию класса DFS, предназначенную для использования кли­
ентскими программами с целью проверки на наличие в графе DAG циклов.

о 19.76. Напишите программу, которая генерирует случайные графы DAG путем пост­роения случайных орграфов, выполняя поиск в глубину из случайной исходной точ­ки и отбрасывание обратных ребер (см. упражнение 19.40). Проведите эксперименты с целью выбора подходящих значений параметров, обеспечивающих получение графов DAG с Е ребрами при заданном числе V.

> 19.77. Сколько узлов содержит дерево и граф DAG, соответствующие рис. 19.18 и
представляющие методы вычисления F_N, N-ro числа Фибоначчи.

19.78. Постройте DAG, соответствующий примеру динамического программирования, для модели рюкзака из главы 5 (см. рис. 5.17).

о 19.79. Разработайте АТД для двоичных графов DAG.

• 19.80. Может ли каждый DAG быть представлен как двоичный DAG (см. свойство 5.4)?

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

> 19.82. В стиле рис. 19.20 постройте trie-дерево существования и соответствующий дво­
ичный DAG для ключей 01001010 10010101 00100001 11101100 01010001 00100001
00000111 01010011.

19.83. Постройте реализацию АТД, основанную на построении trie-дерева существо­вания на базе некоторого набора 32-битовых ключей, сжимающих его до двоичного DAG, с последующим использованием этой структуры данных для поддержки запро­сов о существовании.

о 19.84. Начертите схему BDD для таблицы истинности для функции от четырех пере­менных проверки на нечетность, которая принимает значение 1 в том и только том случае, когда число переменных, принимающих значение 1 будет нечетным.

19.85. Напишите функцию, которая принимает в качестве аргумента 2" -разрядную таб­
лицу истинности и возвращает соответствующую схему BDD. Например, для заданного
ввода 1110001000001100 программа должна вернуть представление двоичного графа
DAG (см. рис. 19.20).

19.86. Напишите функцию, которая принимает в качестве аргумента 2" -разрядную таб­
лицу истинности, вычисляет каждую перестановку аргументов ее переменных и,
пользуясь решением упражнения 19.85, возвращает перестановку, которая приводит
к наименьшей схеме BDD.

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

• 19.87. Проведите эмпирические исследования с целью определения эффективности стратегии упражнения 19.85 для различных булевых функций, как стандартных, так и случайных.

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

о 19.89. Начертите неизоморфные графы DAG с двумя, тремя, четырьмя и пятью вер­шинами.

•• 19.90. Сколько существует различных графов DAG с V вершинами Е ребрами?

•••19.90. Сколько существует различных графов DAG с V вершинами Е ребрами, если мы считаем два DAG различными только в тех случаях, когда они не изоморфны?