Техника - молодёжи 1963-09, страница 37

ного графа, обладающего эйлеровым контуром, есть одна особенность: число дуг, исходящих из какой-либо вершины, равно числу дуг, входящих в нее. Такой граф называется псевдосимметрическим.

Иного деловитого читателя, по-видимому, давно уже подмывает спросить: ну и что? На кой все эти мудреные обозначения простых вещей? Стоило выдумывать какие-то графы, чтобы придать наукообразие пустым забавам вроде задач о кенигсбергских мостах, о кругосветном путешествии, о ходах конем?

Санскритская абракадабра и цифровой барабан

Тихий напев плывет над Бенгальским¹ заливом. Звучные гонги, казалось бы, вторят всплескам набегающих волн. Но нет, ритмический узор, выводимый барабанщиком с помощью нехитрого инструмента, значительно сложнее монотонного шума прибоя. И сколь бы ни- был быстрым и замысловатым ритм, барабанщик не собьется в расстановке долгих и кратких пауз, не перепутает очередность слабых и сильных ударов в тугое чрево гонга. Откуда эта удивительная, почти математическая четкость ритмического рисунка?

Если спросить знатока древнего санскрита, что значит слово «яматараджабхйнасалагам», он в недоумении пожмет плечами. И не удивительно, ибо это всего-навсего ничего не значащий набор звуков, даром что санскритский. Выходит, бессмысленный? Не совсем. Посмотрите, как чередуются в нем ударные (1) и безударные (0) слоги: 0111010001. Приведенную цифровую последовательность можно развернуть в триплеты (рис. 7), соответствующие слогам: «ямата», -«матйра, «тараджа», «раджабха» и так далее. Таким путем получаются всевозможные чередования ударных и безударных слогов. Произнося мысленно эти комбинации, индус-ба-рабашцнк легко выводил самые затейливые ритмические фигуры, в которых паузы, слабые и сильные удары были подсказаны расположением ударных и безударных слогов.

Описанный мнемотехнический прием нетрудно представить в виде графа (рис. 8). «Да, но где здесь техническое приложение теории графов? — возразит нетерпеливый читатель. — Чем санскритская абракадабра лучше кенигсбергских мостов?»

Странно, но факт: индийский барабан имеет непосредственное отношение к барабанам, применяемым в вычислительной технике. Речь идет о цифровых барабанах, градуированных двумя видами делений, скажем 0 и 1. Ученым и инженерам приходится сталкиваться с такой задачей. В поле зрения читающей головки за один раз умещается не более к делений. Между тем иногда желательно сделать цифровую дорожку барабана как можно более длинной. Какова наибольшая цепочка из 0 и 1, в которой никакой мульти-плет из к цифр не повторяется?

Задача решается с помощью хорошо знакомого нам графа (рис. 8). Последовательность нз неповторяющихся муль-типлетов (в данном случае квадруплетов, ибо к=4) мы получим, обегая контур так, чтобы не следовать по одному и тому же пути дважды. Вот примеры 16-членных круговых последовательностей, найденные описанным приемом: 0000101001101111; 0000101101001111; 0000101100111101 и т. д. В устройстве памяти современных электронно-вычислительных машин используются барабаны, рассчитанные на десятки тысяч двоичных символов. Между прочим, и близ Калькутты, в долине Дамодар, где по-прежнему звучат барабаны народных музыкантов, вращается барабан электронной машины, составляющей прогнозы погоды по сводкам с 64 метеопостов.

Геометрия коммуникаций

В 1184 году до н. э. пала Троя. Несколько дней и ночей несли взмыленные лошади усталых гонцов в Афины с радостной вестью о победе. А в 1815 году под Ватерлоо закатилось солнце Аустерлица. И, как 30 веков назад, насмерть загоняли лошадей курьеры, чтобы разнести по столицам известие о разгроме Наполеона. Лишь 30 лет спустя — с изобретением телеграфа — начался переворот в технике связи. А сейчас?

В одной только нашей стране миллионы телефонных аппаратов, тысячи телеграфных станций и АТС. Эпистолярный

жанр обречен на отмирание. Радио и телевидение доносят информацию из любого уголка земного шара буквально мгновения спустя после происшествия. Однако прогресс в технике связи ставит все новые проблемы.

У нас более 1 600 городов и около 3 000 поселков. Как лучше соединить их линиями связи? 2 пункта можно связать одной линией. 10 пунктов — уже сорока пятью. А 4 000 — восемью миллионами! Ясно, что способ соединения каждого города или поселка с каждым другим неприемлем. Гораздо проще организовывать центральные узлы, скажем, в столицах. От них лучеобразно ответвлять линии связи в областные центры, а оттуда — в районные и т. д. При этом отпадет необходимость соединять между собой все райцентры. Но вот беда: центральные узлы, куда сходятся линии от всех близлежащих периферийных станций, часто бывают перегружены. Поэтому иной раз быстрее доехать до соседнего поселка на колеснице времен троянской войны или наполеоновских походов, чем ждать, пока освободится линия на переговорном пункте.

Число абонентов стремительно растет. И с каждым годом все острее и острее проблема—как наиболее рационально организовать работу телефонных и телеграфных сетей в масштабах страны, континента, земного шара?

Впрочем, не только телефонных и телеграфных сетей. Создание линий электропередач, транспортных магистралей, радиоэлектронных схем—словом, любых систем коммуникаций — немыслимо без поиска оптимальной конфигурации их составных частей. Тут-то и помогает теория графов.

Не секрет, что суммарная длина проводов в современной электронной машине может достигать многих километров. Допустим, нам нужно найти наиболее простую из всех возможных релейных схем с заранее заданными функциями. Известно, что конструируемое нами реле должно управляться тремя кнопками: А, В и С (рис. 9). Реле пропускает ток до тех пор, пока не нажаты вместе кнопки А и В или одна С. Далее задано, что каждая ветвь последовательно-параллельной схемы должна содержать по 2 переключателя. Как составить цепь с наименьшим количеством ветвей?

Обозначим состояние, когда кнопка нажата, знаком 1, отпущена — 0. По условию тока на выходе схемы не будет при комбинациях 001 (нажата третья кнопка) и 110 (нажаты первые две кнопки). Во всех остальных случаях: 000; 010; 011; 111; 101; 100 —реле должно пропускать ток.

Строим в пространственной системе координат XYZ куб abcdefgh с ребрами, равными 1. Очевидно, что координатами точки а будут 000 (х=0; у=0; z=0), точки b 010 (х=0; у—1; z=0), точки с 011 (х=0; у=1; z=l) и т. д. (рис. 10). Выбираем такие вершины куба, координаты которых соответствуют состояниям реле, когда оно пропускает ток; 000. 010, 011, 111, 101, 100. Это будут вершины а, Ь, с, h, е, f. Теперь осталось найти наименьшее количество дуг, которыми можно покрыть все 6 вершин полученного графа. Эта операция будет соответствовать поиску наименьшего количества ветвей в релейной схеме. Вот они, наши дуги: af, be, eh. Их три. Это означает, что в цепи должно быть 3 параллельных проводника, содержащих по 2 релейных переключателя. Но какова конфигурация переключателей и кнопок?

Посмотрите на дугу af. Она соединяет вершины 000 и 100. Первые цифры обоих триплетов разнятся, две вторые совпадают. Триплеты дуги eh¹ отличаются средней цифрой, дуги be — последней. Заменим несовпадающие цифры точкой, получим .00; 1.1; 01.; причем разместим их в табличку (рис. 11), изображающую совместное расположение кнопок и релейных переключателей. Точка означает, что кнопка и переключатель не связаны друг с другом. Теперь осталось нарисовать и самое схему (рис. 12). Можете проверить, что во всех случаях.

33