Рассмотрим следующий ориентированный граф. Для данного n вершины графа соответствуют целым числам от 1 до n. Существует направленное ребро от вершины i до вершины j, если я делю j. Нарисуйте график для n = 12. Выполните DFS из приведенного выше графа с n = 12. Запишите время обнаружения и время окончания каждой вершины в соответствии с вашей DFS и классифицируйте все ребра графа как дерево, назад, вперед и поперечные края. Вы можете выбрать любую начальную вершину (вершины) и любой порядок посещения вершин.
Я не вижу, как можно пройти этот граф из-за включенных условий. Невозможно получить задний край, потому что деление меньшего числа на большее число не дает целое число и никогда не будет действительным.
Скажем, мы go по этой логике c и создадим ориентированный граф с учетом инструкций. Вершина 1 может перемещаться в вершину 2, потому что 2/1 - это целое число. Однако невозможно добраться до вершины 3, так как вершина 2 может перемещаться только к вершине 4, 6, 8 или 10. Поскольку вы не можете разделить на большее число, никогда не будет возможности посетить более низкую вершину, взяв одну из этих пути и, следовательно, невозможно достичь вершины 3.