admin

  Оценка. Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трёх линий связи (если узел А соединён с двумя узлами В и С, то при выходе из строя узлов В и С узел А становится недоступным). Таким образом, всего линий связи должно быть не менее  10·3 : 2 = 15.
  Пример: каркас пятиугольной призмы (10 вершин – узлы, а рёбра – линии связи). Если вышли из строя два узла на одном пятиугольнике – основании призмы, то связь сохранится через другой пятиугольник. Если вышли из строя по одному узлу на разных пятиугольниках, то связь тоже сохранится.

Индукция по n. База. При n = 5 требуемый граф представлен на рис. слева.
Шаг индукции. Рассмотрим n + 1 точку. Пусть n из них уже соединены – получился граф с n вершинами. Можно считать, что каждые две из этих n точек соединены стрелкой: иначе проведём все недостающие стрелки (направив их в любую сторону), условие тем более будет выполняться. Обозначим (n+1)-ю точку через C и рассмотрим два случая.

1) n чётно. Разобьём n точек на пары. Пусть  {A_k, B_k}  – одна из пар  (1 ≤ k ≤ ⁿ/₂)  и из A_k идёт стрелка в B_k. Тогда проведём из C стрелку в A_k и из B_k проведём стрелку в C (рис. в центре). Так проделаем для каждой пары. Новый граф с  n + 1  вершиной построен. Пусть X, Y – две любые различные его вершины.
  Если и X и Y не совпадают с C, то из X в Y можно пройти (не более чем за два «хода») по индукционному предположению.
  Пусть X или Y совпадает с C. Тогда другая из этих точек (Y или X) входит в какую-то пару из тех, на которые мы разбили первые n точек. Таким образом, X и Y – это какие-то две из трёх точек, изображенных на центральном рисунке. Глядя на этот рисунок, легко перебрать все возможные варианты и убедиться, что требование выполняется.
  2) n нечётно. Выберем любую вершину A₁. Она соединена стрелками со всеми остальными вершинами: A₂, …, A_n. Из A₁ выходят не менее чем две стрелки или в A₁ входят не менее чем две стрелки (так как  n > 4).
  Пусть из A₁ выходят не менее чем две стрелки (второй случай аналогичен) – в вершины A₂, A₃. Остальные вершины разобьем на пары. Теперь соединим стрелками новую вершину с тройкой A₁, A₂, A₃ – как показано на рис. справа, а со всеми парами – как показано на рис. в центре. Как и в случае а), легко доказать, что полученный граф удовлетворяет условию задачи.

Пусть удалена дорога, ведущая из А в В. Рассмотрим произвольные два города C и D, отличные от А и В.
1) До удаления дороги АВ из C в D можно было проехать по одной или двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому удаление дороги АВ не повлияет на проезд из C в D.
2) После удаления дороги АВ по условию остался путь из A в B. Пусть E – последний город на этом пути перед B. Как показано выше, из C в E можно проехать не более чем по двум дорогам. Значит, из C в B можно проехать не более чем по трём дорогам.
Аналогично доказывается, что из А можно проехать в D не более чем по трём дорогам.
3) До удаления дороги АВ из A в E можно было не более чем по двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому после удаления дороги АВ из А в В можно проехать не более чем по трём дорогам (по маршруту АEВ).

Пусть n – число сторон данного многоугольника, а k – число вершин, в которые входит по две стрелки. Всего стрелок – n, из них 2k стрелок входят в данные k вершин, остальные n – 2k стрелок входят еще в n – 2k вершин (в каждую – по одной). Остаётся n – k – (n – 2k) = k вершин, в которые не входит ни одной стрелки, то есть из которых выходит по две стрелки.