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

12

С. Овчинников

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

Что такое переключательная схема, легко понять из рисунка 1. Имеются две группы по $n$ полюсов — группа входов и группа выходов (на рис. 1 $n = 4$). Каждый полос входа соединен связью с одним и только с одним полосом выхода. Читатели, знакомые с понятием графа, могут заметить, что переключательная схема представляется собой граф специального вида. Такие графы называются семями.

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

Рис. 1.

Рис. 2.

13

изображена схема, реализующая симметрию $n$ чисел: $i$-й вход соединин с $(n-i+1)$-м выходом. Для этой схемы необходимо $n$ слое, так как каждой пара связи должна лежать в разных слоях.

Сформулируем теперь строго условия задачи и доказем основную теорему.

Пусть нам задана переключителяная схема с $n$ входами и $n$ выходами; занутерум их целыми числами 1, 2, …, $n$. Каждая такая схема задает взаимно однозначное отображение на себя множество чисел $\{1, 2, ..., n\}$; иными словами, схема задает перестановку $P$ множество чисел $\{1, 2, ..., n\}$, ставящую в соответствии номеру входа номер соедининого с ним выхода. Например, переключителяной схема на рисунке 1 соответствует перестановка $1 \rightarrow 2, 2 \rightarrow 4, 3 \rightarrow 1, 4 \rightarrow 3$. Очевидно, что каждой перестановке, в свою очередь, соответствует некоторая переключителяная схема. Поэтому в дальнейшем мы не будем различать переключителяные схемы и соответствующие им перестановки.

Число $n$ называется степенью перестановки $P$. Связь, соединяющего вход $i$ с выходом $j$, будем обозначать $(i, j)$. Тогда перестановка $P$ может быть определена как множество $\{(i, j)\}$ всех связей.

Рассмотрим некоторые примеры. Схема на рисунке 1 соответствует перестановка степеня 4, которое можно записать в виде множества связей:

$$P_1 = \{(3, 1), (1, 2), (4, 3), (2, 4)\}.$$

Перестановки степеня $n$, соответствующие схемам на рисунках 3 и 4, записываются так:

$$P_2 = \{(1, 1), (2, 2), ..., (n, n)\},$$
$$P_3 = \{(n, 1), (n-1, 2), ..., (1, n)\}.$$

Заддача 1. Докажите, что две связи $(i, j)$ и $(p, q)$ пересекаются тогда и только тогда, когда $(i-p)(j-q) < 0$.

Подмножество связей называется «слоем перестановки $P$, если никакие две связи из этого подмножества не пересекаются. На рисунке 2 изображены два слоя перестановки $P_1$. Перестановка $P_2$ сама является слоем, а для перестановки $P_3$ каждый слой состоитровно из одной связи.

Толщиной перестановки $P$ называется минимальное число слое, на которых ее можно разложить. В наших примерах толщина $P_1$ равна 2, толщина $P_2$ равна 1, а толщина $P_3$ равна $n$. Очевидно, что толщина люборей перестановки не превыходит ее степеня $n$.

Заддача 2. Докажите, что для любого целого $p \leq n$ существует перестановка $P$ степеня $n$ и толщины $p$.

Перестановки толщины 2 называются 2-реализуемыми (их можно разложитьровно на два слоя) и обладают следующим свойствам. Наозем связи $(i, j)$ правой, если $i \geq j$, и левой, если $i < j$ (на рисунке 5 изображена перестановка, правые связи которой выделены красным цветом, а левые — синим). Оказываться, что множество всехлевых связей 2-реализуемой перестановки является слоем. (Докажите это.)

Например, перестановка на рисунке 5 не 2-реализуема: ее левые

14

Рис. 5.

связи (2, 5) и (3, 4) пересекаются. Противоположим по смыслу понятие слоя является понятие пучка. Подмножество связей называется пучком, если любые две связи из этого подмножества пересекаются. Толщиной пучка называется число входящих в него связи. Каждую связыва мы будем считать пучком толщины 1.

Вернемся к нашим примерм. У перестановки $P_1$ (см. рис. 1) имеется три пучка толщины 2:
$\{(3, 1), (1, 2)\}, \{(3, 1), (2, 4)\}$ и $\{(4, 3), (2, 4)\}$.

Все пучки перестановки $P_2$ (рис. 2) имеют толщину 1. У перестановки $P_3$ (рис. 3) любое подмножество связыва является пучком. В частности, сама перестановка $P_3$ является пучком.

Среди пучков данной перестановки особый интерес представляют пучки максимального толщины. Такие пучки называем максимальным.

Задача 3. Докажите, что максимальный пучок произвольной перестановки не может состоять из одних только левых ее связыва.

Между толщиной перестановки и толщиной ее максимального пучка существует очевидная зависимость: чем более толстые пучки имеются у перестановки, тем она сама толще. Следующая теорема конкретизирует эту зависимость.

Теорема 1. Толщина перестановки равна молщине ее максимального пучка.

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

меньше толщины пучка. Поэтому для доказательства теоремы достаточно построить такое разложение данной перестановки, число словев которого равно числу связыва в максимальном пучке. Иными словами, в каждом слое такое разложения должна лежатьровно одна связыва из максимального пучка.

Прежде, чем доказывает теорему 1, установим одно важное свойство максимального пучка.

Лемма. Пусть
$(i_1, j_1), (i_2, j_2), \dots, (i_p, j_p)$
— связыва, входящие в максимальный пучок, причем
$j_1 < j_2 < \dots < j_p$.

Если некоторая связыва $(i, j)$ пересекаем связыва $(i_1, j_1)$, то $i < i_1$.

Доказательство. Предположив противное, из результата задачи 1 получим, что $j < j_1$. Но тогда связыва $(i, j)$ пересекает все связыва Dannого пучка, а это противоречит его максимальной.

Будем говорить, что связыва $(i, j)$ начинается в полное $j$. тогда доказанное свойство геометрической изначает, что любая связыва начинающаяся левее максимального пучка, не пересекает самой левой его связыва. Аналогично, всякая связыва, начинающаяся правее максимального пучка, не пересекает его самой правой связыва. Перестановка на рисунке 6 или построирует нашу лемму. Красным отмечены связыва максимального пучка. (1, 5) — самая правая связыва максимального пучка, (4, 2) — самая левая. Заметим, кстати, что максимальных пучков может быть несколько. Для перестановки на рис.

15

сунке 6 их три:
{(4, 2), (3, 4), (1, 5)}, {(7, 3), (3, 4), (1, 5)} и {(7, 3), (6, 6), (5, 7)}.

Доказательство теоремы 1.

Мы даим конструктное доказательство, то есть указываем процесс, с помощью которого можно каждую перестановку разложить на минимальное число слов.

Обозначим толькоину максимального пучка через $p$. Отнесем связь $(u_1, 1)$ (то есть самую левую связь перестановки) в первый слой и обозначим ее $(u_1, v_1)$. Среди всех связей $(i, j)$, не пересекающих $(u_1, v_1)$, рассмотрим связь с наиболее шиммем $j$. Ее собственным $(u_2, v_2)$ и тоже относим в первый слой. Перебирая подряд связи, начиная с самой левой, и относая к первому слюю те, которые не пересекают уже выбранных, мы получим множество попарно непересекающих связей $(u_1, v_1), (u_2, v_2), \dots, (u_h, v_h)$, которые и образуют первый слой.

Связи, не попавшие в первый слой, сами образуют неокоторую перестановку. Применяя к этой перестановке предыдущей построение, мы получим второй слой и так далее.

Постотрим, что при этом построении произходит с максимальным пучком. Обозначим связи, входящие в этот пучок через $(i_1, j_1), (i_2, j_2), \dots, (i_p, j_p), j_1 < j_2 < \dots < j_p$. Согласно лемме, связь $(i_1, j_1)$ не пересекается ни с одной связью, начинающаяся слева от нее, и, следовательно, должна попасть в первый слой. Никакие другие связи из этого максимального пучка в первый слой уже не попадут, так как они пересекают связь $(i_1, j_1)$. Поэтому из каждого максимального пучка в первый слой попадет по одному связи.

Выделим из нашей перестановки первый слой. Легко видеть, что в оставшейся перестановке максимальные пучки имеют только $p-1$. Выделив второй слой, мы получим в оставшейся перестановке максимальные пучки только $p-2$. Продолжая этот процесс выделения слов, мы на $(p-1)$-м шаг получим перестановку, максимальные пучки которого имеют только 1. Но это означает, что связи в этой перестановке не пересекаются, и, следовательно, она сама образует последний $p$-й слой.

Итак, мы показали, что любую перестановку можно разложить на слой, число которых равно тольконице максимального пучка; это разложение и доказывает теорему.

Уражениее. Проверьте справедливость теоремы для $P_1, P_2$ и $P_3$.

Рассмотрим переключательные схемы, соответствующие перестановкам тольконы 2, то есть 2-реализуемым перестановкам; они представляют особый интерес, так как для их изготовления требуется всего два проводаших слоя. Пусть две такие переключательные схемы соединены так, как показано на рисунке 7. Очевидно, что получившаяся на рисунке 7 схема эквивалентна переключательной схеме на рисунке 8. Обозначим перестановку, соответствующее схеме рисунка 8, через $P$, а перестановки, соответствующие верхней и нижней схемам рисунка 7 — через $P_1$ и $P_2$ соответствующего. Будем говорить, что перестановка $P$ равна произведению перестановок $P_1 \cdot P_2$.

Аналогичным образом можно определить произведение любого числа перестановок. Порядок сомножителей в таком произведение важно: например, если взять перестановку

16

Оказывается, любую перестановку можно разложить в произведение нескольких 2-реализуемых! (Доказите это.)

Если перестановка представляется в виде произведения s «штук» 2-реализуемых перестановок, то говорят, что она s-каскадно реализуема. (Так, изображенная на рисунке 8 перестановка P (толщины 3) 2-каскадно реализуема; разложение P на 2 каскада 2-реализуемых перестановок осуществляют перестановки P₁ и P₂ рисунка 7.) Технологии s-каскадно реализуема перестановка имеет два проводаших слоя и один изолирующий, переванный s — 1 раз. Первыению изолирующего слоя соответствует разрыв между каскадами; очевидно, что в разрыве изолирующего слоя пересечения связи не проискодит. Каждый изолирующего слоя соответствует разрыве 2-реализуемых) проходит через каждый каскад, но, быть может, в разных проводах слоя — см. рисунок 10; связи, лежащие в одном проводшем слое, обозначаны одним цветом.

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

Начнем с перестановки Kₚ, ставшей в соответствии числу i число p — i + 1, то есть реализушей симметрию p чисел.

Как уже отмечалось, перестановка Kₚ совпадает со своим максимальным пучком и имеет только равную p. Сейчас мы построим некоторое каскадное разложение перестановки Kₚ на двуслойные перестановки и затем показем, что построенное разложение минимально.

При p = 2 перестановка K₂ сама является каскадом (единивным). Как разложить перестановку K₄ (p = 4), видно из рисунка 11. Использование идеи разложения на каскад

17

ды для перестановки $K_4$, построим каскадное разложение перестановки $K_8$ ($p = 8$) — см. рисунок 12. Теперъ уже ясно, как построить каскадное разложение перестановки $K_p$, если $p$ равно степени двойки. Верхний каскад (для $p = 2^r$) изобразен на рисунке 13. Остальные каскады симметрично реализуют перестановки положives 1, 2, …, $2^{r-1}$ и положives $2^{r-1} + 1$, $2^{r-1} + 2$, …, $2^r$; при этом $k$-й каскад перестановки степени $2^r$ получается объединением двух одинаковых ($k-1$)-х каскадов перестановки степени $2^{r-1}$. Очевидно, что число каскадов в построенном каскадном разложении перестановки $K_2^r$ равно $r$.

Пусть теперь $p$ не является степенью двойки; тогда существует такое $r$, что $2^r < p < 2^{r+1}$. Расмотрим каскадное разложение перестановки $K_{2r+1}$ степени $2^{r+1}$ и видим в нем связи, начинающие в положах с номерами, не превыходящими $p$. Очевидно, что эти связи определяют перестановку $K_p$ (входы с номерами $2^{r+1} - p + 1$, $2^{r+1} - p + 2$, …, $2^{r+1}$ нужно переумеровать, начиная с единиц: 1, 2, … $p$), а данное каскадное разложение перестановки $K_{2r+1}$ осуществляет также разложение перестановки $K_p$. Например, на рисунке 14 каскадное разложение для перестановки $K_6$ выделено из разложения для $K_8$.

Итак, для перестановок $K_p$, являющихся пучками, мы построили каскадные разложения. Если $p$ такое, что $2^{r-1} < p \leq 2^r$, то число каскадов равно $r$. Иначе это можно записать так: $r = \log_2 p$, где $|a|$ обозначает наименьшее целое, не меньше $a$.

Покажем теперь, что построенные каскадные разложения перестановок $K_p$ состоит из минимального числа каскадов. Для этой примера индекцию по $p$. Заметим, что если $p < q$, то для минимального каскадного разложения перестановки степени $q$ требуется каскадов не меньше, чем для минимального разложения перестановки степени $p$.

При $p = 2$ нашей утверждение очевидно. Пусть утверждение доказано для $p = k$. Расмотрим два случая.

a) $2^{r-1} < k < 2^r$.

Для перестановки $K_k$ степени $k$ имеем $r$-каскадное разложение. При переходе от $k$ и $k+1$ число каскадов, как следует из нашей замечания, не уменьшается. Но так как $k$ — число целое, то $k+1 \leq 2^r$, и, значит, мы можем построить $r$-каскадное разложение перестановки $K_{k+1}$ степени $k+1$; понятно теперь, что оно и является минимальным.

b) $k = 2^r$.

Расмотрим перестановку $K_{k+1} = K_{2r+1}$. Так как $2^{r+1} < 2^{r+1}$, то мы можем построить для перестановки $K_{k+1}$ $(r+1)$-каскадное разложение. Покажем, что $r$ каскадов для разложения перестановки $K_{k+1}$ недостаточно (тогда $(r+1)$-каскадное разложение как раз и будет минимальным).

Предположим противное: пусть имеется $r$-каскадное разложение перестановки $K_{2r+1}$ степени $2^{r+1}$. Расмотрим верхний каскад этого раз-