Переключательные схемы

16

ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ

Р. В. Фрейвалд

На V Всесоюзной математической оптимизации*) была предложена следующая задача:

Переключитель (рис. 1) с двумя входами и двумя выходами может находиться в двух различных состояниях.

На рисунке 2 изображена схема телефонной связи с трех входами и трех выходами, которая обладает таким свойством «универсальности»:

Рис. 1. Рис. 2. Рис. 3.

меняя состояние переключителя, можно осуществить любое из шести соединений трех входов с трех различными выходами, то есть

(Проверьте это. Заметьте, что общее число различных состояния этой схемы равно 2³=8, поскольку каждый из переключителей может находиться в двух состояниях.)

a) Построите схему с четырьмя входами и четырьмя выходами, которая была бы «универсальной», то есть осуществлена бы любое из 24 возможных соединений входов и выходов.

b) Какое минимальное число переключителей нужно для такой схемы?

b) Наозовем схему с n входами и n выходами n-универсальной, если

*) Подробнее о пяной оптимизации см. «Квант» № 11 за 1971 г., стр. 35—42.

18

Делить по блокам $A$ и $B$ так, чтобы 4 связи проходили через $A$ и 4 — через $B$. При этом мы должны следить, чтобы две связи не проходили через один и тот же вход или один и тот же выход блоков $A$ и $B$.

Рассмотрим первый и пятый вход нашей схемы. Каждый из них может быть подключен либо к первому входу блока $A$ либо к первому входу блока $B$. Следовательно, один из этих входов должен быть подключен к блоку $A$, другой — к блоку $B$, иначе две связи будут подключиты к одному и тому же входу неокоторого блока. К разным блокам должны быть подключиты также следующие пары входов: 2-й и 6-й, 3-й и 7-й, 4-й и 8-й. Легко видеть, что такое условие распределения связи по блокам не только необходимо, но и достаточно для того, чтобы в схеме разные связи не проходили через один и тот же вход блоков $A$ и $B$. Чтобы формировать такое же условие для в ходов в блоков $A$ и $B$, полезно обратить внимание на симметрию расположение входов и выходов схемы. Заключаем, что следующие пары выходов схемы должны подключиты к разным блокам: 1-й и 5-й, 2-й и 6-й, 3-й и 7-й, 4-й и 8-й.

Изображим на рисунке эти отношения между различными связями одного и того же соединения. Каждый отдельную связь изобразим прямоугольником, внутри которого записано, какой вход с каким выходом данная связь соединяет. Если две связи обязательно должны проходить через разные блоки, то соответствующие им прямогольники соединяются линейной. При этом проведем линейную красного цвета, если на 4 отличиях входы, и синено — если на 4 отличиях выходы.

Например, соединение

$$\begin{array}{c c c c c c c c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ 3 & 8 & 1 & 6 & 2 & 7 & 5 & 4 \end{array}$$

таким способом изобразено на рисунке 7.

Каково бы ни было соединение, из каждого прямогольника выходить в точности одна синяя и в точности одна красная линяя. Поэтому рисунок всегда состоит из одного или нескольких «колец». При этом в каждом «колец» красные и синые линей чередуются, иначе из неокоторого прямогольника выходили бы две линей одного цвета. Следовательно, каждое «колец» содержит чесло примогольников.

Пользовать таким рисунком, легко распределить связи по блокам так, чтобы выполнялись все указанные выше ограничения. Для этого нужно следить, чтобы связи, которые соответствуют прямогольники, соединенные линейной, проходили через блоки. Поэтому в каждом «колец» рисунка нужно выбрать произвольным образом по одному примогольнику и соответствующую этому примогольнику связь осуществить через блок $A$, далее, связь, соответствующую соответствующую примогольнику, осуществить через блок $B$, потом связь, соответствующую

19

шую следующему прямогольнику, через $A$ и так далее, пока «кольцо» замкнется. Связи, соответствующие первому и последнему прямогольникам, при этом будут осуществляться через разные блоки, так как число прямогольников в «кольце» четно. 8-унверсальное схемы (см. рис. 3) доказана. Заметим только, что распределение связи по блокам всегда можно проведети так, чтобы один из переключителей (например, левый нижний) находился в каком-то заранее заданном состоянии. (Другими словами, этот переключитель можно из схемы удалить, а схема не перестановить быть универсальной.) Тогда в «кольце», содержащем связь, проходящую через выделенный переключитель, распределение связи по блокам нужно начать именно с этой связи.

Для оценки сверху числа переключителей в минимальной $n$-унверсальной схеме будем строить $n$-унверсальные схемы с возможного меньшим числом переключителей. Приведенное выше доказательство 8-унверсальной схемы (см. рис. 3) легко обобщить на случай любого числа входов. Этот способ дает возможность, имея 8-унверсальную схему, строить довольно экономную 16-унверсальную схему, потом 32-унверсальную схему и так далее. Можно подсчитать, что если $n=2^k$ и в качестве блоков 4-унверсальной схемы использовать схему (рис. 4), то такая схема имеет $2k \cdot 2^k - \frac{11}{4} \cdot 2^k = 2n \cdot \log_2 n - \frac{11}{4} \cdot n$ переключителей. Если $n$ не равно целой степени двойки, то можно использовать схему, являющийся универсной для большого числа входов, равного полной степени двойки. Так как близкая сверху полная степень двойки преосходит данное число $n$ не более чем в два раза, получается, что для любого $n$ существует $n$-унверсальная схема, содержащая не более $4n \cdot \log_2 n$ переключителей.

(Окончание см. на стр. 27.)