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

Версия 14:58, 21 декабря 2024

Задача зарезервирована: Urmat A 14:54, 21 декабря 2024 (UTC)

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

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

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

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

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

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

@@ Строка 6: / Строка 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 связанных компонентов] в любом графе в коллекции.
-Если граф не имеет <s>замкнутых циклов</s>петель и между любой парой узлов имеется не более одного ребра, что из следующего '''верно'''?
+Если граф не имеет <s>замкнутых циклов</s> петель и между любой парой узлов имеется не более одного ребра, что из следующего '''верно'''?
 === Ответы ===