Сигналы, графы и короли на торе

14

А. Футер

Сигналы, графы и короли на торе

Наутро мелеfon как завоит! Я вскочил неодетый, схватил мрубку и крицу:
— Слушаю!
А из мрубки в ответ:
— Ты чего хрюкаешь?
— Как это — хрюкаю? Я не хрюкаю, — говорю я.
— Брось хрюкать! Говори по-человеческим! — крицит Мишка.
— Я и говорю по-человеческим. Зачем хрюкать?
— Ну, довольно мне баловать!
Все равно я не поверю, что мы поросенка в комнату примацил.

Н. Носов. Телефон

Когда два человека ведут heteropollinую беседу, слова каждой из них обычно вполне понятны собеседнику. Переспрашивать, уточнять непонятные слова приходится редко. Если тот же самый разговор вести по телефону, то, в зависимости от качества связи, неясно рассышанные слова встречаются чаще, иногда сильно затрудняя понимание. Если же мы попробуем передать по телефону не осмысленные слова, а просто последовательность букв, что-нибудь вродеритффсклаaaam…,

то окажется, что некоторые буквы часто перепутываются, например «ф» и «с», «б» и «г» и т. д.

Искажает сигналы практическки каждой способа связи, будь то телефон, радио, бинокль. С этим явлением существует разные способы борбы, но все они снижают эффективность связи. Например, по телефону можно передавать не отдельные буквы, а связные слова: «б» как «Борис», «г» как «Григорий» и т. п., — но тогда вместе одной буквы нам придется передавать 5—8. Можно повторять каждой сигнал много раз, как передавались, например, на Землю perвые фотографию обратной стороны Луны в 1959 году, но это займет во столько же раз больше времени. В этой заметке исследуется один экономный способ борбы с искажением сигналов при передаче*). Идея этого способа проста: если уж мы знаем, какие сигналы с какими можно спутать, то будем передавать лишь один сигнал из каждой такой группы, а от остальных откажется. Например, по телефону из звуков «ф», «с», «ш» — только звук «с».

*) Впервые эти вопросы исследовал американский кибернетик (француз по проискожению) Клод Шеннон.

15

Графы ошибок

Каждеое сообщение обычно состоит из отдельных «элементарных» сигналов: слов (в разговоре по телефону), букв (в морской флажковой сигнализации «семафор») или других знаков (точка и тipe на телефонке). Пусть эти элементы сигналы образуют множество $S$ — входной алфавит. Избраним каждый сигнал из $S$ кружочком и соединим пару кружочков отрезком («ребром»), если соответствующие им сигналы при передаче можно спутать друг с другом. Получится граф $^*$ с множеством вершин $S$. Изовем его графом ошибок нашего передающего аппарата.

Приведем пример. Минутная стрелка электрических часов меняет свое положение сначала как только кончается очередная минута, стрелка прыгает к следующей. Если эти часы находится дальше от нас, то мы не можем точно определить положение минутной стрелки. Но пусть мы ошибаемся какдый раз не очень сильно — не более, чем на минуту. тогда входной алфавит будет содержать 60 элементов — 60 возможных положений минутной стрелки (каждому из них соответствует точка на окружности — границе циферблата), а графом ошибок $\Gamma$ будет правильный 60-угольник — какдая точка соединена отрезками с двумя соседями.

А теперь попытаемся выяснить, что надо сделать, чтобы можно было безшибочно распознать наиболее число показаний минутной стрелки. Передаем часы так, чтобы минутная стрелка прыгала через каждые 2 минуты, то есть чтобы часы показали лишь четное число минут. тогда уже никакое видимое нам показание ни с каким другим спутать нельзя — ведь ошибок в 2 минуты или больше мы не допускаем. Таким образом, если довооритться, что множество передаваемых сигналов — это только 30 четных чисел от 0 до 58, то все они будут безшибочно определены. С другой стороны, оченьindo, что 30 — максимальное значение: если в графе $\Gamma$ взять 31 вершину или больше, то какне-нибуд две из них обязательно будут соединены (доказите!).

В этом примере мы построили множество $M$ вершин графа, обладающее следующим свойством: любые две вершины из $M$ не соединены ребром. Такое множество $M$ называется независящим множеством (н. м.). В нашем примере независящим любые наборы четырех минутной стрелки, например: {2, 8, 34, 52, 56}, — или набор показаний, делящийся на 5: {0, 5, 10, …, 55}.

Если $M$ вершин неокоторого графа $G$ содержит наиболее число вершин среди всех его $M$, то оно называется наиболее числом независящим множеством (н. н. м.), а число $\alpha(G)$ вершин в нем — числом независящим (ч. н.) графа $G$.

В рассмотрении выше графе $\Gamma$ много различных $M$, а $H, N, M$. — всего два (совокупность четырех чисел от 0 до 58 и совокупность четырех чисел от 1 до 59), и $\alpha(\Gamma) = 30$.

Если графе $G$ является графом ошибок неокоторого передающего аппарата $A$, то $\alpha(G)$ — это наиболее число различных сигналов, которые можно передать через этот аппарат без перепутывания. Поэтому $\alpha(G)$ называют еще пропускной способностью аппарата $A$.

16

Квадрат алфавита

С каждым передающим аппаратом $A$ мы связывали входной алфавит $S$, граф ошибок $G$ и число независимости графа $G$ (пропускная способность аппарата $A$) $\alpha(G)$. А как бы, если аппарат $A$ задан раз и навсегда, а его пропускная способность для нас неодостаточная? Скажем, если $A$ — телефон передавать по телефонную буквы? Выход известен — это азбука Морзе: надо передавать через $A$ пачки из нескольких знаков (точек — тipe) и считать каждую такую пачку одним сигналом.

Сначала попробуем передавать через тот же аппарат $A$ по два последовательных сигналов из $S$. Посмотрим, сколько сильно возрастает элементы любого алфавита будем называть буквами).

Попробуем определить пропускную способность аппарата $A^2$. Для этого прежде всего надо построить граф ошибок, обозначаемый через $G^2$. Посмотрим, при каких условиях сигнал $(v_1; v_2)$ можно спутать с сигналом $(w_1; w_2)$. Очевидно, для этого должно выполняться одно из следующих трех условий:

a) $v_1 = w_1$, $v_2 \sim w_2$;
b) $v_1 \sim w_1$, $v_2 = w_2$;
c) $v_1 \sim w_1$, $v_2 \sim w_2$.

Таким образом, вершины $(v_1; v_2)$ и $(w_1; w_2)$ графа $G^2$ соединены ребром, если в графе $G$ есть ребра $v_1 - w_1$ (или $v_1 = w_1$) и $v_2 - w_2$ (или $v_2 = w_2$). Например, если графе $G$ содержит всего две вершины, соединенные ребром, то $G^2$ — это квадрат с диагоналями (рис. 2).

Заддача 3. Построить граф $G^2$ для каждого из графов $G$, изображенных на рисунке 3.

Таким образом, можно считать, что $G^2$ — это «слоенный» граф: каждый его вертикальный или горизонтальный слой совпадает с $G$, а каждому ребру $a - b$ графа $G$ соответствует квадрат с диагоналями в графе $G^2$.

Попробуем найти какое-нибудь независимое множество в графе $G^2$.

Пусть в графе $G$ множество $M$ независимо. Это означает, что элементы из $M$ при передаче аппаратом $A$ друг с другом не путаются. Тогда при передаче пар букв из $M$ ни одна из этих букв не исказится, поэтому в алфавите $S^2$ не путаются друг с другом элементы вида $(a; b)$, где $a \in M$, $b \in M$. Множество пар $(a; b)$, где $a \in M$, $b \in M$, обозначается символом $M^2$. Легко видеть, что если $p$ — число элементов в $M$, то число элементов в множество $M^2$ равно $p^2$. Таким образом, пропускная способность аппарата $A^2$ является как минимум квадратом пропускной способности аппарата $A$, то есть на языке графов

$$\alpha(G^2) \geqslant (\alpha(G))^2.$$

Заметим, однако, что такое увеличение пропускной способности дается не даром — вдвое падает скорость передачи сигналов.

На самом деле буквы по телефонную передаются несколько иначе. В принципе для всех 33 буквы алфавита необходимо наборы из 6 знаков (пятизнаковых не хватит), но по телефонную передаать не только точ

17

Королі на торе

Усложним немного граф $G_5$ рисунка 3: склеим точки 0 и $n$. Получится $n$-угольник 012 … $(n-1)$. Обозначим этот граф через $P_n$. Его квадрат $P_n^2$ получится из квадрата отрезка, если склеить попарно две горизонтальные и две вертикальные его стороны. Но квадрат отрезка — настоящий квадрат, а если еще склеить его противоположные стороны, то получится тор! А точнее, сетка на торе, содержащая $n^2$ квадратиков $1 \times 1$ с диагоналями (рис. 4).

Если вершины этих квадратиков отложить с клетками горизонтой доски размером $n \times n$, то соседние в шахматном смысле поля доски оказываются соединенными отрезками сетки, или, что то же самое, ребрами графа $P_n^2$, а задача $M415$ о максимальном числе несоседних королей на торе превращится в задачу определения числа независяности графа $P_n^2$. Ее решение приведено в этом номере журнала (см. с. 37).

Если вы хотите яснее представить себе структуру н. н. м. графа $P_n^2$, решите следующие задачи.

Задча 4. Пусть множество $M$ — н. н. м. графа $P_n^2$ (или, что то же самое, горизонтой доски $n \times n$). Доказите, что

a) если $n=2s$, то $M_1^2$, где $M_1$ — некоторое н. н. м. $P_n$, является н. н. м., и $\alpha(P_2s^2) = s^2$;

18

6. если $n=4s+1$, то на каждой вертикали и на каждой горизонтали доски расположетсяровно $s=\left[\frac{n}{4}\right]$ точек (королей) из $M$ (здесь $[a]$ — целая часть числа $a$);
   в) если $n=4s+3$, то на каждой вертикали и на каждой горизонтали горизонтали доски расположется либо $s$, либо $s+1$ точек из $M$.

Задача 5. Будем изобразить граф $P_2^2$ (тор) квадратом, помня, что противоположные стороны его склеены. Наозем циклический свойством графа $P_n^2$ отображение «паралельный перенос», при котором элемент (0; 0) переходит в $(s; t)$.

Докажите, что любое н. н. $M$ графа $P_2^2$ можно привести к виду, изобразенную на рисунке 5, если разрешить циклическое сdvизом графа доски и симметричное отношение диагонали, вертикали и горизонтали квадрата.

Примечние. Симметрию относительно диагонали (0; 0) $(n-1; n-1)$ квадрата можно записать формулой $(x; y) \rightarrow (y; x)$. Циклический сdvиз может быть запись так: $(x, y) \rightarrow (x+s; y+t)$, но в этой формуле будет одна неточность. Хотелось бы отложить числа $n$ и $0$, $h+1$ и $1$ и т. д. Для этого применяются значки $\equiv$ и $(mod n)$. Говорят, что $a$ сравним с $b$ по modulo $n$ и пишут $a \equiv b$ $(mod n)$, если $a$ и $b$ при делении на $n$ дают равные остатки. Обозначим через $a$ $(mod n)$ остаток от деления $a$ на $n$. Тогда можно сказаать, что элемент $(x; y)$ переходит при циклическом сdvизе графа в элемент $((x+s) (mod n); (y+t) (mod n))$, а при отложении относительно, скажем, прямой $x=a$ — в элемент $(2a-x) (mod n); y)$.

Рис. 6.

Все, что известно

Попробуем dalleше условия наш передающий аппарат; построим аппарат $A^k$, где $k$ — некоторое натуральное число. Это значит, что с помощью аппарата $A$ мы будем передавать пачки из $k$ букв, каждой из которых береется из начального входного алфавита $S$.

По аналогии с двухбуквенными сигналами несложно построить граф $G^k$ ошибок аппарата $A^k$. Его множество вершин — это алфавит $S^k$, состоящий из всевозможных наборов букв длины $k$: $(v_1; v_2; ...; v_k)$, где все $v_i$ берутся из алфавита $S$. Несложно построить и ребра в графе $G^k$, то есть понять, какие сигналы $(v_1; v_2; ...; v_k)$ и $(w_1; w_2; ..., w_k)$ могут перепутаться. Для этого должны перепутаться между собой буквы каждой из координат, то есть для каждой $i$ $(1 \leq i \leq k)$ должны выполнять одно из двух условий: либо $v_i = w_i$, либо $v_i \sim w_i$ (если $v_i = w_i$ для каждой $i$, то данные наборы совпадают).

Определять точное значение пропускной способности аппарата $A^k$ в общем случае довольно сложно, но можно оценить ее снизу.

Задача 6. Докажите, что $\alpha(G^k) \geqslant (\alpha(G))^k$.

А дальней… Дажке в одном из самых простых случая, когда граф ошибок — это $n$-угольник $P_n$, об $\alpha(P_n^k)$ известно мало. Все, что известно из литературы, сейчас и будет расссказано.

Торическая шахматную доску размером $n \times n$ называют еще двумерным мором. Аналогично $k$-ю степени $n$-угольника (граф $P_n^k$) можно назвать $k$-мерным мором со стороны $n$. Вер-

19

Рис. 7.

шины графа $P^k_n$ можно отложить с набором из $k$ целых чисел: $(x_1; x_2; \dots; x_k)$, где каждое число $x_i$ изменяется от 0 до $n-1$.

Задание 7. Определите число вершин в графе $P^k_n$.

Согласно определению, два набора $(x_1; x_2; \dots; x_k)$ и $(y_1; y_2; \dots; y_k)$ смежны в графе $P^k_n$, если в $n$-угольнике каждой пара координат $x_i, y_i$ — соседи, то есть для каждой значения $i$-тоя координаты различаются не более, чем на единицу: $|x_i - y_i| \equiv h_i$ (mod $n$) $\in \{0, 1\}$ для всех $i$ от 1 до $k$ (например, на рисунке 6 для случая $k=3, n=5$ отмечены соседи набора (0; 1; 2)).

Задание 8. Определите число соседей каждой вершины $k$-мерного tora.

Задание 9. Докажите, что

$$\alpha(P^k_n) \leq \left[ \left( \frac{n}{2} \right)^k \right].$$

Задание 10. Определите $\alpha(P^k_n)$, если $n$-четное.

Для нечетных $n$ справедлива оценка

$$\left( \frac{n-1}{2} \right)^k \leq \alpha(P^k_n) \leq \left[ \left( \frac{n}{2} \right)^k \right],$$

а иногда известно и точное значение $\alpha(P^k_n)$.

Теорема. Если $n-1$ делится на $2^k$, то

$$\alpha(P^k_n) = \frac{n-1}{2^k} \cdot n^{k-1}.$$

Полное доказательство этой теоремы довольно длино, поэтому показем лишь, как определить независящее множество с таким числом элементов. По каждому набору $(x_1; x_2; \dots; x_{k-1})$ первый $k-1$ координат получим $r = \frac{n-1}{2^k}$ значений $k$-тоя координаты:

$$x_k \equiv 2l + r(2^{k-1}x_1 + 2^{k-2}x_2 + \dots + 2^1x_{k-1}) \pmod n.$$

Здесь $l$ — любое целое число от 0 до $r-1$.

Если для случая $k=2$ вы изобразите множество вершин, координаты которых заданы последней формулой, то получится ответ задан. М415 при $n-1$, делящем на 4.

Эти результаты позволяют построить таблицу значений $\alpha(P^k_n)$ (рис. 7).

В ней часть чисел получена теоретически, а остальные — при помощи вычислительной машины. Вы видите, что с ростом $k$ и $n$ должна незаполненных мест становится все-всеоме.

Может быть, кто-то из вас заполнит пропуски в этой таблице и решит задачу об определении пропускной способности передачи аппаратов?