Модели разума. Как физика, инженерия и математика сформировали наше понимание мозга - Lindsay Grace Страница 54

* * *

В столице Восточной Пруссии XVIII века Кенигсберге река, проходя через город, разветвлялась на две части, образуя посередине небольшой остров. Остров соединялся с частями города к северу, югу и востоку от него семью мостами. В какой-то момент у жителей Кенигсберга возник вопрос: существует ли способ передвижения по городу, при котором каждый из мостов пересекается один и только один раз? Когда этот игривый вопрос встретился со знаменитым математиком Леонгардом Эйлером, родилась теория графов.

Эйлер, эрудит, родившийся в Швейцарии, но живший в России, в 1736 году написал работу "Решение задачи о геометрии положения" (Solutio problematis ad geometriam situs pertinentis). В этой работе он дал однозначный ответ на вопрос: кёнигсбержец не может совершить прогулку по своему городу, проходя через каждый мост ровно один раз. Чтобы доказать это, ему пришлось упростить карту города до скелета ее полной структуры и работать с ней логически. Он показал, не используя слово, как превратить данные в граф и как выполнять на нем вычисления (см. рис. 20).

В контексте теории графов слово "граф" не означает график или диаграмму, как это принято в обычном языке. Скорее, граф - это математический объект, состоящий из узлов и ребер (в современном понимании).Узлы - это базовые единицы графа, а ребра представляют связи между ними. В примере с Кенигсбергом мосты служат ребрами, соединяющими четыре различных массива суши - узлы. Степень узла - это количество ребер, которые он имеет; таким образом, "степень" массива суши -

Рисунок 20

Эйлер подошел к вопросу о мостовых переходах, заметив, что путь через город можно записать в виде списка узлов. Если дать каждому массиву земли буквенное имя, то список "ABDC", например, будет представлять собой путь, который идет от острова в центре к земле внизу (через любой мост, соединяющий их), затем от него к массиву земли справа и далее к земле вверху. При таком пути через граф между каждой парой узлов проходит одно ребро. Таким образом, количество пересеченных мостов равно количеству букв в списке минус одна. Например, если вы пересекли два моста, то в вашем списке будет три земельных массива.

Затем Эйлер заметил нечто важное в количестве мостов, которые есть у каждого массива суши. Это число связано с тем, сколько раз этот массив должен появиться в списке путей. Например, у массива земли B есть три моста, а значит, "B" должен дважды появиться в любом пути, который пересекает каждый мост по одному разу - то есть нет способа пересечь эти три моста, не посетив B дважды. То же самое верно и для массивов C и D, поскольку у них тоже по два моста. А вот массив A с пятью мостами должен появиться в списке путей три раза.

Вместе взятые, любой путь, удовлетворяющий этим требованиям, будет состоять из девяти (2+2+2+3) букв. Однако список из девяти букв представляет собой путь, пересекающий восемь мостов. Поэтому невозможно построить путь, который пересекает каждый из семи мостов только один раз.

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

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

Учитывая эту особенность, теория графов нашла применение во многих областях. Химики XIX века бились над, как изобразить структуру молекул. К 1860-м годам была разработана система, которая используется и по сей день: атомы рисуются в виде букв, а связи между ними - в виде линий. В 1877 году английский математик Джеймс Джозеф Сильвестр увидел в этом графическом представлении молекул параллель с работой потомков Эйлера в математике. Он опубликовал работу, в которой проводил аналогию, и впервые использовал слово "граф" для обозначения этой формы. С тех пор теория графов помогла решить множество проблем в химии. Одно из самых распространенных ее применений - поиск изомеров - наборов молекул, которые состоят из одного и того же типа и количества атомов, но отличаются друг от друга тем, как эти атомы расположены. Поскольку теория графов предоставляет формальный язык для описания структуры атомов в молекуле, она также хорошо подходит для перечисления всех структур, которые возможны при определенном наборе атомов. Алгоритмы, которые это делают, могут помочь в разработке лекарств и других нужных соединений.

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

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