Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 47

Рассмотрим поиск в глубину неориентированного графа с 3 вершинами P, Q и R. Пусть время обнаружения d (u) представляет момент времени, когда вершина u впервые посещается, а время окончания f (u) представляет время момент, когда вершина u в последний раз посещается. При условии
d (P) = 5 единиц f (P) = 12 единиц
d (Q) = 6 единиц f (Q) = 10 единиц
д (р) = 14 ед. ф (р) = 18 ед.
какое из следующих утверждений является истинным в отношении графа
(A) Есть только один подключенный компонент
(B) Есть два соединенных компонента, и P и R связаны
(C) Есть два подключенных компонента, и Q и R связаны
(D) Есть два соединенных компонента, и P и Q связаны

Ответ: (D)
Пояснение: поскольку d (q) = d (p) +1 и f (q) <f (p), что означает, что p и q связаны, а r отделен, поэтому d является ответом

Тест на этот вопрос
Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте

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

ВОРОТА | GATE IT 2006 | Вопрос 47

0.00 (0%) 0 votes