В здании находится восемь серверов. Они расположены в вершинах куба. Эти серверы объединены в сеть, причем два сервера соединены линией связи "напрямую" в том и только том случае, когда они соответствуют двум соседним вершинам куба. Кроме того, два из этих серверов соединены дополнительно по радиоканалу.
Какое наименьшее число основных линий связи придется вывести из строя злоумышленнику, для того что бы потерялась связность сети (т.е. станет невозможно доставить информацию с одного из серверов на другой, даже через серверы-посредники)
Так как неизвестно расположение радиоканала, после удаления проводных линий сеть должна разбиться не менее чем на три фрагмента (т.н. компоненты связности). Это легко сделать, удалив все линии связи у двух серверов, расположенных в соседних вершинах куба. Потребуется вывести из строя 5 линий.
Осталось показать, что четырьмя линиями обойтись нельзя. Так как компонент не менее трех, а всего вершин восемь, компонента с наименьшим числом вершин содержит одну или две вершины. В первом случае для изолирования одного сервера надо вывести из строя все три ведущие к нему проводные линии. Легко видеть, что оставшуюся часть сети удалением одной линии разделить на две части невозможно. Во втором случае для изолирования компоненты из двух серверов уже надо удалить четыре проводных линии. При этом, оставшаяся часть сети не распадется на две компоненты.