2019-gate-computer-science-and-it-practice.pdf/Q17-alg5

Вопрос: Q17-alg5-31d68c

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

I

Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

II

DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

Какие из данных утверждений верны?

Ответы

• Правильный ответ: Только I
• Только II
• Оба
• Ни одно

Объяснение

Если в графе есть обратные ребра, то в нем есть цикл.

Второе утверждение неверно, так как можно привести пример ориентированного графа с тремя вершинами, степени вершин которого равны 2, 1 и 0. В таком случае обратных ребер найдено не будет.

DFS с вершины «a» не найдет ни одного обратного ребра:

Исходники — вопрос 17 на 244 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.