Предмет: Геометрия,
автор: sytyugina08
ДАЮ 25 БАЛЛОВ!!
Какое наименьшее число ребер нужно удалить из полного графа на 100 вершинах чтобы он стал несвязным
Удачник66:
Чувствую, что нужно удалить 99 ребер, идущих к любой одной вершине, но доказать не могу
Ответы
Автор ответа:
2
Ответ:
нужно удалить 99 ребер.
Объяснение:
Из теоремы
- если из полного графа на n вершинах удалить не более n − 2 ребер, то граф останется связным.
следует, что количество ребер, которое необходимо удалить из полного графа, чтобы сделать его несвязным, больше n−2.
Наименьшее число х = n - 2 + 1 = n-1 ребро.
Т.е. для нашего графа нужно удалить х = 100-1=99 ребер.
#SPJ1
Похожие вопросы
Предмет: Другие предметы,
автор: продвиz5
Предмет: Русский язык,
автор: 1234123411
Предмет: Русский язык,
автор: olga338
Предмет: Информатика,
автор: JuliaErrr
Предмет: Математика,
автор: Vitedge