Question

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

Answer 1

Ответ:

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

Объяснение:

Из теоремы

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

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

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

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

#SPJ1