2004-gre-cs-practice-book.pdf/Q43 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
Urmat A (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
graph G{ | graph G{ | ||
1 2 3 4 5 6 7 8 9 10 | 1 2 3 4 5 6 7 8 9 10 | ||
| − | 1--2--3--4-- | + | 1--2--3--4 |
| + | 1--3 | ||
| + | 1--4 | ||
| + | 2--4 | ||
} | } | ||
</neato> | </neato> | ||
Версия 15:05, 21 декабря 2024
Задача зарезервирована: Urmat A 14:54, 21 декабря 2024 (UTC)
Вопрос: 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 компонентами связности.