Очень нужно!!!! Решите с объяснением.
Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
Ответы
Ответ дал:
0
15 вершин, полный граф, (т.е. есть всевозможные связи)
связей = n*(n-1)/2 = 15*14/2 = 105
Если связи убирать случайно
Связный граф - вершины должны быть соединены хоть раз. Для 15 вершин должно быть 15-1=14 связей
Несвязным граф точно будет если связей 13 и меньше
105 - 13 = 92 связи нужно убрать
Если связи убирать целенаправленно
То тогда нужно отсоеденить одну вершину. Всего вершин 15, и каждая связана с 14 остальными вершинами. Если мы уберем эти 14 связей, то 15 вершинный граф перестанет быть связным
Ответ 14
связей = n*(n-1)/2 = 15*14/2 = 105
Если связи убирать случайно
Связный граф - вершины должны быть соединены хоть раз. Для 15 вершин должно быть 15-1=14 связей
Несвязным граф точно будет если связей 13 и меньше
105 - 13 = 92 связи нужно убрать
Если связи убирать целенаправленно
То тогда нужно отсоеденить одну вершину. Всего вершин 15, и каждая связана с 14 остальными вершинами. Если мы уберем эти 14 связей, то 15 вершинный граф перестанет быть связным
Ответ 14
Ответ дал:
0
спасибо.
Вас заинтересует
1 год назад
2 года назад
2 года назад
8 лет назад
8 лет назад
8 лет назад