2019-gate-computer-science-and-it-practice.pdf/Q17-alg5 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
} | } | ||
</graph> | </graph> | ||
| − | |||
| − | |||
<graph> | <graph> | ||
digraph G{ | digraph G{ | ||
| + | rankdir=LR | ||
a -> b -> c | a -> b -> c | ||
} | } | ||
</graph> | </graph> | ||
| + | DFS с вершины «a» не найдет ни одного обратного ребра: | ||
{{cstest-source|2019-gate-computer-science-and-it-practice.pdf|244|17}} | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|244|17}} | ||
Текущая версия на 16:18, 25 декабря 2024
Вопрос: 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»