2004-gre-cs-practice-book.pdf/Q43

Ссылки сюда (1) →

Вопрос: Q43-4c9f66

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами.

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции.

Если граф не имеет замкнутых циклов и между любой парой узлов имеется не более одного ребра, что из следующего верно?

Ответы

• M = 10, m = 10
• M = 10, m = 1
• Правильный ответ: M = 7, m = 4
• M = 6, m = 4
• M = 6, m = 3

Объяснение

Исходники — вопрос 43 на 31 странице книги «2004-gre-cs-practice-book.pdf»

• Без циклов — компоненты будут остовными деревьями, число ребер на единицу меньше числа вершин.
• Для максимизации компонент — например, 5 изолированных вершин + дерево «5 вершин с 6 реберами», ну или любой вариант с перекидыванием ребер из большого дерева к изолированным.

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

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

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