На полигоне расположены 300 узлов связи, некоторые из которых соединены проводами (провода прямые, один провод соединяет ровно 2 узла, между любыми двумя узлами проходит не более одного провода). Система узлов связна, то есть из любого узла можно передать сигнал в любой другой (возможно, через промежуточные узлы). Будем называть узел значимым, если его ликвидация приводит к тому, что система оставшихся узлов перестает быть связной. При ликвидации узла все провода, которые вели непосредственно к нему, перестают функционировать.
а) Может ли в системе быть ровно 2 значимых узла?
б) Может ли каждый значимый узел быть соединен только с незначимым?
в) Какое наибольшее количество узлов могут быть значимыми?
а) Да. Пусть 298 узлов соединены между собой попарно, узел 299 соединен только с узлом 1, узел 300 соединен только с узлом 2. Тогда узлы 1 и 2 значимы, а все остальные нет.
б) Да. Пусть узлы соединены только с узлом 1. Тогда он значим, а остальные нет — условие выполняется.
в) Если соединены узлы 1 и 2, 2 и 3, ..., 299 и 300, то все узлы, кроме 1 и 300, значимы. Их 298. Докажем, что есть как минимум два незначимых узла. Рассмотрим граф, вершинами которого являются узлы, а ребрами — связи между ними. Если в графе есть цикл, то мысленно закроем одно ребро в нем, связность от этого не пропадет (вместо прохода по этому ребру можно пройти по оставшейся части цикла). Будем так делать до тех пор, пока циклов не останется (это обязательно произойдет, поскольку число ребер уменьшается). Теперь возьмем любую вершину и пойдем из нее по ребрам, пока можно. Заметим, что вершины на пути не повторятся (циклов нет). Значит, рано или поздно мы окажемся в тупике — вершине, из которой можно уйти только назад. Если же мы начнем теперь с нее, то окажемся во втором тупике. Ясно, что тупиковая вершина незначима — без нее можно пройти из любой другой вершины в любую другую (поскольку заходить в тупиковую на таком пути вообще незачем).
Ответ: а) да; б) да; в) 298.