2004-gre-cs-practice-book.pdf/Q43 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Пусть ''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'' и ''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 связанных компонентов] в любом графе в коллекции. | ||
| − | Если граф не имеет | + | Если граф не имеет [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%82%D0%BB%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)#:~:text=%D0%9F%D0%B5%CC%81%D1%82%D0%BB%D1%8F%CC%81%20%D0%B2%20%D0%B3%D1%80%D0%B0%D1%84%D0%B5%20%E2%80%94%20%D1%80%D0%B5%D0%B1%D1%80%D0%BE%2C%20%D0%B8%D0%BD%D1%86%D0%B8%D0%B4%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B5%20%D0%BE%D0%B4%D0%BD%D0%BE%D0%B9%20%D0%B8%20%D1%82%D0%BE%D0%B9%20%D0%B6%D0%B5%20%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5.&text=%D0%92%20%D0%BD%D0%B5%D0%BA%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D1%85%20%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B0%D1%85%20%D0%B3%D1%80%D0%B0%D1%84%20%D0%BF%D0%BE,%D0%B1%D0%B5%D0%B7%20%D0%BF%D0%B5%D1%82%D0%B5%D0%BB%D1%8C%20%E2%80%94%20%D1%8D%D1%82%D0%BE%20%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9%20%D0%B3%D1%80%D0%B0%D1%84. петель] и между любой парой узлов имеется не более одного ребра, что из следующего '''верно'''? |
=== Ответы === | === Ответы === | ||
Текущая версия на 19:27, 23 декабря 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»
Для максимизации компонент — максимально пакуем ребра в полный граф, и одиночки отдельно.
Для минимизации компонент — используем максимум «потенциала ребра», не допускаем циклов, делаем только любые варианты остовных деревьев, результат будет один и тот же