2004-gre-cs-practice-book.pdf/Q43 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
* M = 10, m = 10 | * M = 10, m = 10 | ||
* M = 10, m = 1 | * M = 10, m = 1 | ||
| − | * Правильный ответ: M = | + | * Правильный ответ: M = 4, m = 4 |
* M = 6, m = 4 | * M = 6, m = 4 | ||
* M = 6, m = 3 | * M = 6, m = 3 | ||
| Строка 17: | Строка 17: | ||
{{cstest-source|2004-gre-cs-practice-book.pdf|31|43}} | {{cstest-source|2004-gre-cs-practice-book.pdf|31|43}} | ||
| − | * Без циклов — компоненты будут остовными деревьями, | + | В оригинале — Правильный ответ «M = 7, m = 4». |
| − | * | + | Но это же бред. |
| + | * Без циклов — компоненты будут остовными деревьями, «число ребер на единицу меньше числа вершин». | ||
| + | * Т.е. число связных компонент определяется однозначно — число вершин минус число ребер, чтобы не делать. | ||
| + | * Ну или я ошибаюсь? | ||
| + | |||
| + | <neato> | ||
| + | graph G{ | ||
| + | 1 2 3 4 5 6 7 8 9 10 | ||
| + | 1--2--3--4--5--6--7 | ||
| + | } | ||
| + | </neato> | ||
<neato> | <neato> | ||
| Строка 24: | Строка 34: | ||
1 2 3 4 5 6 7 8 9 10 | 1 2 3 4 5 6 7 8 9 10 | ||
1--2 | 1--2 | ||
| − | 3--4 | + | 1--3 |
| + | 1--4 | ||
| + | 1--5 | ||
| + | 1--6 | ||
| + | 1--7 | ||
| + | } | ||
| + | </neato> | ||
| + | |||
| + | <neato> | ||
| + | graph G{ | ||
| + | 1 2 3 4 5 6 7 8 9 10 | ||
| + | 1--2--3 | ||
| + | 4--5--6 | ||
| + | 7--8 | ||
| + | 9--10 | ||
} | } | ||
</neato> | </neato> | ||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:18, 15 декабря 2024 (UTC)}} | ||
| − | + | [[Категория:Алгоритмы на графах]] | |
| + | [[Категория:Разобраться]] | ||
Текущая версия на 14:18, 15 декабря 2024
Вопрос: Q43-4c9f66
Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами.
Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции.
Если граф не имеет замкнутых циклов и между любой парой узлов имеется не более одного ребра, что из следующего верно?
Ответы
- M = 10, m = 10
- M = 10, m = 1
- Правильный ответ: M = 4, m = 4
- M = 6, m = 4
- M = 6, m = 3
Объяснение
Исходники — вопрос 43 на 31 странице книги «2004-gre-cs-practice-book.pdf»
В оригинале — Правильный ответ «M = 7, m = 4». Но это же бред.
- Без циклов — компоненты будут остовными деревьями, «число ребер на единицу меньше числа вершин».
- Т.е. число связных компонент определяется однозначно — число вершин минус число ребер, чтобы не делать.
- Ну или я ошибаюсь?