2004-gre-cs-practice-book.pdf/Q65

Ссылки сюда (2) →

Вопрос: Q65-4c9f66

Пусть T — дерево поиска в глубину связного неориентированного графа G.

Для каждой вершины v из T пусть:

• pre(v) — количество посещенных узлов (до v включительно) во время прямого обхода T
• post(v) — количество посещенных узлов (до v включительно) включительно во время обратного обхода T.
• Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v

Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v). Какое из следующих утверждений относительно u и v должно быть истинным?

1. post(u) < post(v)
2. u является предком v в T
3. Если w является наименьшим общим предком u и v в T, то w = u

Ответы

• Только 1
• Только 2
• Только 3
• 1 и 2
• Правильный ответ: 2 и 3

Объяснение

Исходники — вопрос 65 на 42 странице книги «2004-gre-cs-practice-book.pdf»

• post(u) < post(v) — в DFS-дереве, т.к. pre(u) < pre(v) — значит «u» мы посетили раньше, и он предок «v», и на обратном обходе «u» соответственно мы посетим позже, т.е. post(u) > post(v).
• «u является предком v в T» — ну да.
• «w - LCA(u,v)» → w = u

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

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

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