Архив задач олимпиады по математике и криптографии
Живучесть сети
Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?
Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трех линий связи. Ситуация
недопустима, ибо при выходе из строя узлов B и C узел A становится недоступным. Значит, всего линий должно быть не менее [(10×3)/2]=15. Вот пример, удовлетворяющий условиям задачи с 15-ю линиями связи:
Приведем доказательство. Если вышли из строя два узла на одном пятиугольнике, то связь сохранится через другие пятиугольники. Если вышли из строя по одному узлу на разных пятиугольниках, то связь сохранится по линиям, соединяющим эти пятиугольники.