18. Подсеть на рис. 1.22, б проектировалась таким образом, чтобы выстоять во время ядерной войны. Сколько бомб потребуется, чтобы разбить сеть на две изолированные части, если одна бомба разрушает узел со всеми линиями, подходящими к нему.
Сначала разберем предысторию рисунка 1.22, б. На предыдущем рисунке 1.22, а в книге изображен пример организации телефонной сети:
В свою очередь, эти телефонные коммутационные станции на рисунке соединены линиями со станциями более высокого уровня, обозначенными черными квадратиками, а те, в свою очередь, соединены со станцией еще более высокого уровня, обозначенной черным шестиугольником.
Очевидно, что если противник уничтожит (разбомбит, к примеру) одну из станций более высокого уровня, то сразу множество обычных телефонных коммутационных станций окажется отсоединенным от основной телефонной сети и абоненты этих станций окажутся без связи.
В 1960-х годах американский инженер и изобретатель Пол Бэран предлагал изменить вышеизложенную архитектуру телефонной сети с целью сделать ее более устойчивой к уничтожению отдельных ее звеньев следующим образом.
Во-первых, вообще убираем из сети все станции высоких уровней, а также провода, идущие к ним от рядовых телефонных коммутационных станций. Освободившиеся провода используем для соединения рядовых телефонных коммутационных станций между собой. Этот процесс проиллюстрирован ниже с помощью трех рисунков:
Крайний справа рисунок из этих трех и обозначен в книге как 1.22, б. Очевидно, что уничтожение противником любой одной из рядовых телефонных коммутационных станций при такой архитектуре телефонной сети не приведет к разделению этой телефонной сети на две изолированные части. Все «выжившие» рядовые телефонные коммутационные станции останутся связанными в обход уничтоженной станции.
В задании не сказано, сколько минимум может быть коммутационных станций в одной изолированной части. Предположим, мы хотим изолировать какую-то одну любую коммутационную станцию на рисунке 1.22, б. Я немного подумал над этим рисунком и понял следующее: чтобы изолировать любую коммутационную станцию на рисунке, нужно уничтожить все станции, от которых идут линии к целевой станции. А значит, для этого бомб нужно будет сбросить столько, сколько к целевой станции подходит линий.
На следующем рисунке я привел примеры трех станций, которые можно изолировать от общей сети соответственно двумя, тремя и четырьмя бомбами (количество бомб равно количеству линий, подходящих к целевой станции):
Предположим, требуется изолировать от остальной сети любые две примыкающие друг к другу станции. Сколько для этого потребуется бомб? Как это вычислить? Очень просто. Объединяем эти две станции в одну, для этого можно перерисовать наш рисунок. А далее действуем так же, как и было описано выше: количество бомб для отделения одной станции мы уже умеем определять.
На рисунке ниже я привел два примера (А и Б) отделения от основной сети изолированной части из двух станций. В примере Б всё должно быть понятно: после объединения станций в одну станцию к ней подходят три линии, поэтому для изолирования этих двух станций от основной сети потребуется три бомбы. В примере А, однако, линий к нашей объединенной станции на первый взгляд подходит четыре, а бомбы требуется только три. Почему так? На самом деле, линии под номерами 2 и 3 после объединения наших двух станций тоже должны объединиться в одну, так как они выходят из одной станции и входят в одну (объединенную) станцию. Поэтому линий будет три и бомбы потребуется тоже три.
