Предмет: Геометрия, автор: sytyugina08

ДАЮ 25 БАЛЛОВ!!
Какое наименьшее число ребер нужно удалить из полного графа на 100 вершинах чтобы он стал несвязным


Удачник66: Чувствую, что нужно удалить 99 ребер, идущих к любой одной вершине, но доказать не могу

Ответы

Автор ответа: pushpull
2

Ответ:

нужно удалить 99 ребер.

Объяснение:

Из теоремы

  • если из полного графа на n вершинах удалить не более n − 2 ребер, то граф останется связным.

следует, что количество ребер, которое необходимо удалить из полного графа, чтобы сделать его несвязным, больше n−2.

Наименьшее число х = n - 2 + 1 = n-1 ребро.

Т.е. для нашего графа нужно удалить х = 100-1=99 ребер.

#SPJ1

Похожие вопросы
Предмет: Математика, автор: Vitedge