2004-gre-cs-practice-book.pdf/Q65 — различия между версиями

Текущая версия на 07:12, 16 декабря 2024

Пусть 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 должно быть истинным?

Исходники — вопрос 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

@@ Строка 27: / Строка 27: @@
 * ''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''
+* «''w'' - LCA(u,v)» → ''w = u''
 {{question-ok|[[Участник:StasFomin|StasFomin]] 07:12, 16 декабря 2024 (UTC)}}
 [[Категория:Алгоритмы на графах]]