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

Л. БОБРОВ

Рис. Г. КЫЧАКОВА

Что общего между радиоэлектронной схемой и созвездием Гончих Псов? Между картой железных дорог и траекторией ракеты, между иерархической лестницей и структурной химической формулой?

Сколь бы разношерстной ни была перечисленная компания, все это ни более и ни менее, как представители многочисленного семейства графов. Конечно, «граф» здесь вовсе не титул отпрыска какой-нибудь знатной фамилии. Зато генеалогическое древо любой знатной фамилии не что иное, как самый настоящий граф.

Что же такое графы? А главное — какой от них прок?

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

Операция „единица" сэра Уильяма Гамильтона

Известный английский математик Уильям Роуэн Гамильтон в свое время занялся задачей о замкнутом кругосветном путешествии. Вот она. Выберем на земном шаре 20 городов: г, Ь, с...

до марсианских каналов-

Прогулка по мостам и скачки на шахматной доске

Два с лишним столетия назад у жителей тихого Кенигсберга пропал покой. Простоватые бюргеры и высокомерные юнкеры, недоросли-школяры и ученые мужи, даже беззаботные Гретхен и доблестные прусские офицеры, не привыкшие утомлять свой мозг чрезмерными интеллектуальными упражнениями,— словом, все достопочтенные кенигсбергские граждане в поте лица корпели над задачей — как обойти семь мостов, перекинутых через реку Прегель, побывав на каждом всего один раз (см. 3-ю, стр. обложки, рис. 1).

Этой беспокойной затеей заинтересовался Леонард Эйлер. И вот на свет появился... граф (рис. 2). Именно он помог великому математику доказать неразрешимость знаменитой задачи: контур невозможно нарисовать единым росчерком, не отрывая пера от бумаги и не проходя по одной и той же линии дважды.

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

Разумеется, с графами сталкивается не только тот, кто делает ходы конем. Во многих случаях жизни мы рисуем на бумаге точки, изображающие людей, географические пункты, небесные светила, атомы, чтобы затем соединить эти точки линиями или стрелками, обозначающими определенную взаимосвязь. Например, для математика родословная династии Рюриковичей или дома Романовых — граф, в котором царственные особы могут фигурировать в виде обыкновенных точек, а право наследования короны — всего-навсего в виде стрелок (рис. 4). Те же стрелки и точки могут дать представление о субординации в соответствии с петровской «Табелью о рангах» или другой подобной. «иерархической лестницей». Структурная химическая формула — тоже граф (рис. 5). Цепкая реакция и телефонная сеть, система кровообращения и расписание космических рейсов — все это можно изобразить на бумаге в виде графа.

Граф симметричен, если любые две смежные вершины его соединены двумя противоположно ориентированными дугами'

Для простоты допустим, что эти города расположены в вершинах правильного додекаэдра (рис. 6). Наша цель — пройти через каждый город ровно один раз и вернуться в исходный пункт. Идти можно лишь по ребрам додекаэдра. Каков маршрут кругосветного вояжа?

Путешественник, стоящий на распутье, должен выбрать одну из трех возможностей. Например, повернуть направо (эту операцию определим как П) или налево (Л). Если же он остается на месте или каким-то образом пбсле скитаний очутится в исходной точке, то операция обозначится через 1. Тогда произведение ПЛ — сложная операция, когда путешественник идет сначала вправо, потом влево; ЛЛП, или Л^гП, — два раза подряд влево, затем один раз вправо. Наконец, две операции равноценны, если обе они от одной и той же станции отправления приводят к одной и той же станции назначения. Глядя на рисунок, легко вывести следующие формулы:

ПЛ^ЛП; (ЛЛ)П = Л(ЛП); № = Л5 = 1; ПЛ^гП = ЛПЛ;

ЛП²Л = ПЛП; ШШ = Л²; ЛП³Л = П².

Теперь найдем, сколькими способами можно возвратиться в исходную точку (операция «1»), обогнув земной шар. 1 = П⁵ = П²П³ = (ЛП³Л)П³ == (ЛП³)² = [Л(ЛП³Л)П]² =■ = (Л²П³ЛП)² = [Л²(ЛП³Л)ПЛП]² = (ЛЩ³ЛПЛП)² = = ЛЛЛПППЛПЛПЛЛЛПППЛПЛП.

Произведение содержит 20 сомножителей, причем из него невозможно выделить отрезок, тоже равный 1. Стало быть, найденная последовательность задает нам один из искомых маршрутов — его назвали гамильтоновым контуром. Второй маршрут найдем, прочитав последовательность в обратном порядке. Остальные гамильтоновы контуры получаются циклической перестановкой обеих последовательностей. Между прочим, эйлеровы «ходы конем» тоже сводятся к отысканию гамильтонова контура в симметрическом графе.

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

в таком диапазоне работает ТЕОРИЯ ГРАФОВ

32