2004-gre-cs-practice-book.pdf/Q65 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q65-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q65-4c9f66 == | == Вопрос: Q65-4c9f66 == | ||
| − | + | Пусть ''T'' — дерево [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83 поиска в глубину] связного неориентированного графа ''G''. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Для каждой вершины ''v'' из ''T'' пусть: | |
| − | + | * ''pre(v)'' — количество посещенных узлов (до ''v'' включительно) во время [https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0#%D0%9F%D1%80%D1%8F%D0%BC%D0%BE%D0%B9_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4_(NLR) прямого обхода] ''T'' | |
| − | ( | + | * ''post(v)'' — количество посещенных узлов (до ''v'' включительно) включительно во время [https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0#%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D1%8B%D0%B9_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4_(LRN) обратного обхода ''T'']. |
| + | * [https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%BF%D1%80%D0%B5%D0%B4%D0%BE%D0%BA Наименьшим общим предком] вершин ''u'' и ''v'' в ''T'' является вершина ''w'' из ''T'', такая, что ''w'' является предком как ''u'', так и ''v'', и ни один дочерний элемент ''w'' не является предком, как ''u'', так и ''v'' | ||
| − | + | Пусть ''(u, v)'' — ребро в ''G'', которого нет в ''T'', такое, что ''pre(u) < pre(v)''. | |
| − | + | Какое из следующих утверждений относительно ''u'' и ''v'' должно быть истинным? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | # ''post(u) < post(v)'' |
| − | + | # ''u'' является предком ''v'' в ''T'' | |
| − | + | # Если ''w'' является наименьшим общим предком ''u'' и ''v'' в ''T'', то ''w = u'' | |
| + | === Ответы === | ||
| + | * Только 1 | ||
| + | * Только 2 | ||
| + | * Только 3 | ||
| + | * 1 и 2 | ||
| + | * Правильный ответ: 2 и 3 | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|42|65}} | |
| − | {{cstest-source|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'' | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 07:12, 16 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Алгоритмы на графах]] | |
Версия 07:12, 16 декабря 2024
Вопрос: 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 должно быть истинным?
- post(u) < post(v)
- u является предком v в T
- Если 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