2004-gre-cs-practice-book.pdf/Q43 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q43-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q43-4c9f66 == | == Вопрос: Q43-4c9f66 == | ||
| − | + | Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами. | |
| − | + | ||
| − | + | Пусть ''M'' и ''m'', соответственно, являются максимальным и минимальным количеством [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 связанных компонентов] в любом графе в коллекции. | |
| − | + | ||
| + | Если граф не имеет замкнутых циклов и между любой парой узлов имеется не более одного ребра, что из следующего '''верно'''? | ||
=== Ответы === | === Ответы === | ||
| − | + | * M = 10, m = 10 | |
| − | + | * M = 10, m = 1 | |
| + | * Правильный ответ: M = 4, m = 4 | ||
| + | * M = 6, m = 4 | ||
| + | * M = 6, m = 3 | ||
| − | + | === Объяснение === | |
| − | + | {{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> | |
| − | < | + | graph G{ |
| − | { | + | 1 2 3 4 5 6 7 8 9 10 |
| + | 1--2 | ||
| + | 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> | ||
| − | + | {{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». Но это же бред.
- Без циклов — компоненты будут остовными деревьями, «число ребер на единицу меньше числа вершин».
- Т.е. число связных компонент определяется однозначно — число вершин минус число ребер, чтобы не делать.
- Ну или я ошибаюсь?