Question

15 баллов. какое наименьшее число ребер нужно удалить из полного графа на 100 вершинах чтобы он стал несвязным.

Answer 1

Ответ:

99 рёбер

Объяснение:

Нужно применить:

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

Решение. Так как по условию граф полный и n = 100, то нужно удалить    больше чем 100-2 = 98 рёбер, чтобы он стал несвязным. Отсюда следует, что наименьшее число ребер которых нужно удалить из полного графа на 100 вершинах чтобы он стал несвязным - это 99 рёбер.

#SPJ1