2004-gre-cs-practice-book.pdf/Q43 — различия между версиями

Версия 16:35, 21 декабря 2024

Вопрос: 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»

В оригинале — Правильный ответ «M = 7, m = 4». Но это же бред.

• Без циклов — компоненты будут остовными деревьями, «число ребер на единицу меньше числа вершин».
• Т.е. число связных компонент определяется однозначно — число вершин минус число ребер, чтобы не делать.
• Ну или я ошибаюсь?

Я уже указал, что перевод был не верный. В оригинале говорится о self-loops, то есть о петлях. Поэтому циклы допускаются и легко привести пример такого графа с 7 компонентами связности.

Думаю очевидно, что если взять больше 3 вершин и соединить их 6 рёбрами, то больше компонент связности не получится. Как и если взять по 3 вершины, будет тоже самое. Решено: Urmat A 15:12, 21 декабря 2024 (UTC)