2019-gate-computer-science-and-it-practice.pdf/Q13-alg5

Вопрос: Q13-alg5-31d68c

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

I

Диграф — это граф, имеющий ровно 2 вершины.

II

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

III

Алгоритм сортировки ребер для решения задачи коммивояжера всегда дает оптимальный результат.

Какие утверждения верные, а какие нет?

Ответы

• I, II
• II, III
• I, III
• Правильный ответ: Только II

Объяснение

Второе утверждение верно, так как по определению остовного дерева, оно должно покрывать все вершины графа. Поэтому как минимум ребер будет содержаться в таком дереве в случае, когда каждое ребро дерева покрывает уникальную пару вершин графа. Остальные утверждения неверные по определению диграфа и решения задачи коммивояжера с помощью сортировки ребер.

Исходники — вопрос 13 на 243 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.