Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 5

Рассмотрим DAG с V = {1, 2, 3, 4, 5, 6}, как показано ниже. Что из перечисленного НЕ является топологическим порядком?


(А) 1 2 3 4 5 6
(Б) 1 3 2 4 5 6
(С) 1 3 2 4 6 5
(D) 3 2 4 1 6 5

Ответ: (D)
Объяснение: В опции D, 1 появляется после 2 и 3, что невозможно при топологической сортировке .

В данном DAG непосредственно видно, что существует исходящее ребро от вершины 1 до вершины 2 и 3, следовательно, 2 и 3 не могут предшествовать вершине 1, поэтому ясно, что вариант D является неправильной топологической сортировкой.
Но для вопросов, в которых он не виден напрямую, мы должны знать, как найти топологический вид DAG.

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

ВОРОТА | GATE-CS-2007 | Вопрос 5

0.00 (0%) 0 votes