8. В локальную сеть включено 20 компьютеров, причём каждая пара компьютеров соединена напрямую оптоволоконным кабелем. Администратор решил оптимизировать сеть, сократив число кабелей. Какое наибольшее их количество можно удалить, чтобы можно было по-прежнему передавать информацию с любого компьютера на любой другой, но, возможно, через другие компьютеры?

Изначально между каждой парой компьютеров есть кабель. Чтобы сеть оставалась связной, достаточно сохранить кабели, образующие дерево. Дерево на 20 вершинах содержит 19 рёбер, поэтому можно оставить 19 кабелей.

Всего кабелей было 20 · 19 / 2 = 190. Тогда удалить можно 190 − 19 = 171 кабель.

Ответ: 171 кабель.