Карты метро и нейронные сети. Теория графов

Клауди Альсина

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

Область допустимых решений имеет форму многоугольника. Именно в вершинах этого многоугольника расположены значения (х, у), обеспечивающие максимальную прибыль, которая рассчитывается по формуле 6х + 5у. Чтобы найти максимально возможный объем прибыли, нужно выполнить следующие действия.

1. Определить координаты вершин области

допустимых решений.

2. Рассчитать прибыль в каждой из вершин области допустимых решений.

3. Выбрать вершину, для которой прибыль будет максимальной.

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

* * *

РЕШЕНИЯ ЗАДАЧ

Цепь в прямоугольнике (стр. 106):

Цепь на квадратной сетке (стр. 107):

Задача о четырех окружностях (стр. 110):

Магическая гексаграмма (стр. 111): чтобы получить одно из возможных решений, нужно расположить числа в рядах, сверху вниз, следующим образом: 10; 4, 7, 9, 6; 8, 5; 1, 11, 12, 2; 3.

* * *

Здесь снова появляется теория графов: эта задача может быть решена с помощью симплекс-метода, разработанного Джорджем Данцигом.

Представьте область допустимых решений в виде графа (это может быть многоугольник на плоскости, многогранник в пространстве либо же некий плоский граф в общем виде).

Плоский граф, соответствующий области допустимых решений, которая представляет собой многогранник.

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

Поиск быстрых алгоритмов для решения подобных задач всегда имел особую важность. Работы Кармаркара позволяют, например, найти оптимальные решения на 50—100 % быстрее, чем традиционный симплекс-метод.

Эпилог

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

Хорхе Вагенсберг

Есть книги, которые хранят, но не читают. Другие книги читают, но не хранят. А есть книги, которые читают, хранят и которые заставляют искать другие книги по этой же теме. Нам бы хотелось, чтобы этот маленький путеводитель в мире графов стал для вас именно такой книгой. О теории графов и ее различных применениях, а также о смежных областях — топологии, теории алгоритмов, дискретной математике — написано бесчисленное множество книг. Если эта тема вас заинтересовала, не прекращайте поиски, расширяйте свои знания.

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

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

Теория графов — еще одно подтверждение того, как важно уметь видеть лишь основное и необходимое в сложном мире.

В завершение эпилога приведем некоторые размышления философов на тему того, почему наше пространство имеет три измерения. Много лет назад Джеральд Джеймс Уитроу в своей книге «Структура и эволюция Вселенной» показал, что в пространствах, имеющих больше трех измерений, стабильное и равномерное движение планет вокруг Солнца было бы невозможно. Но в двумерном пространстве разумная жизнь также не могла бы существовать, что доказывает теория графов: мозг состоит из огромного числа нейронов (вершин графа!), связанных между собой нервами (ребрами графа!), которые не должны пересекаться. Подобные сложные связи между нейронами в двумерном пространстве были бы невозможны, что ясно видно на примере плоских графов. Эта аналогия особенно интересна тем, что даже наш разум представляется в ней как огромный нейронный граф.

Желаем, чтобы прекрасные графы сопровождали вас по жизни и помогали в решении самых разных задач.

Приложение

Графы, множества и отношения

Математика, подобно любому прочному зданию, твердо стоит на фундаменте. Логика играет главную роль при выполнении дедуктивных умозаключений, лежит в основе понятий истинности и ложности, различий между аксиомами (постулатами) и теоремами, допустимыми формами доказательств и так далее. Теория множеств — еще одна колонна, на которой стоит здание математики. С ее помощью можно формализовать самые основные составляющие математических структур: элементы, множества, отношения, функции.

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

= (1, 2, 3, …} обозначает множество натуральных чисел. На рисунке ниже изображено это же множество в виде точек на прямой.

* * *

ГЕОРГ КАНТОР (1845–1918) И ТЕОРИЯ МНОЖЕСТВ

Этот гениальный немецкий математик создал теорию множеств, чтобы дать более строгие определения многим математическим понятиям, в частности понятию бесконечности. Важный вклад в теорию множеств также внесли Фридрих Фреге и Юлиус Дедекинд. Благодаря Кантору стало возможным говорить, что «конечное множество — это множество, которое не является бесконечным» и что множество А является бесконечным, если между этим множеством и его подмножеством можно установить взаимно однозначное соответствие, то есть один к одному. Кантор прояснил вопрос, касающийся счетных бесконечных множеств, например множеств натуральных, целых или дробных чисел. Ему же принадлежит определение различных категорий бесконечностей (трансфинитные кардинальные и ординальные числа). Его идеи породили ожесточенные споры с другими математиками того времени (его основным противником стал Леопольд Кронекер), появились некоторые парадоксы, которые требовалось разрешить. Однако благодаря ему родилась красивая и фундаментальная теория множеств.