Рубрики

ВОРОТА | GATE 2017 MOCK II | Вопрос 20

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

S1: DFS ориентированного графа всегда создает одинаковое количество ребер в обходе, независимо от начальной вершины.
S2: Если удаляются все задние ребра, найденные во время обхода DFS на ориентированном графе, результирующий граф является ациклическим.

Какие из следующих утверждений выше действительны?

(A) S1 и S2 действительны
(B) Только S1 действителен
(C) Только S2 действителен
(D) Ни s1, ни S2 не действительны

Ответ: (C)
Пояснение: Заявление S1: рассмотрим график

Начиная с A (исходная вершина), мы получим 2 ребра
Начиная с B получит только 1 преимущество
Начиная с C мы не получим никакого преимущества

Поэтому DFS на ориентированном графе может не давать одинаковое количество ребер.

Утверждение S2: Задние ребра — это ребра (u, v), соединяющие вершину u с предком u в
дерево в глубину Self-петли считаются задними гранями. Задние края описывают отношения потомка к предку, поскольку они ведут от «высоких» к «низким» узлам.
Предположим, что есть задний край (u, v). Тогда вершина v является предком вершины u в лесу глубины первой. Таким образом, в G есть путь от v к u, и задний край (u, v) завершает цикл. Удаление заднего края нарушит цикл.

Поэтому удаление всех задних ребер сделает граф ацикличным. Так что утверждение верно.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE 2017 MOCK II | Вопрос 20

0.00 (0%) 0 votes