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

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

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

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

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

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

В четвертой главе представлена удивительная взаимосвязь между графами и геометрическими объектами. На примере формулы Эйлера, известной даже школьникам («сумма числа вершин и граней любого многогранника равна числу ребер, увеличенному на два»), вы увидите, как с помощью графов можно изучать многогранники и даже мозаики.

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

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

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

Схема метро — лишь один из немногих примеров использования графов в повседневной жизни. На иллюстрации — схема парижского метро.

Теория графов появилась благодаря одной занимательной задаче, которую решил Леонард Эйлер. История гласит, что в 1736 году этот блестящий математик остановился в Кёнигсберге (в настоящее время — Калининград). Город был разделен рекой на четыре части, которые были соединены семью мостами.

Старинный город Кёнигсберг на гравюре XVII вена.

На рисунке представлен упрощенный план города, на котором мосты обозначены цифрами, а районы города — буквами.

Эйлер писал об этой задаче: «Насколько я понимаю, эта задача широко известна. Она формулируется так: в прусском городе Кёнигсберге есть остров под названием Кнайпхоф, окруженный двумя рукавами реки Преголя. Через два рукава реки перекинуто семь мостов. Нужно определить, можно ли обойти все мосты, пройдя по каждому ровно один раз. Мне сообщили, что некоторые утверждают, будто это невозможно, другие сомневаются, но никто не верит, что это и в самом деле возможно».

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

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

Кёнигсбергские мосты были разрушены во время Второй мировой войны, но эта история, авторство которой приписывается Эйлеру, дала начало удивительно полезной и красивой математической теории — теории графов. Нужно учитывать, что еще до ее создания многие ученые совершенно независимо друг от друга использовали понятия, которые впоследствии были объединены в теорию графов.

В 1847 году Густав Кирхгоф использовал схемы, подобные графам, при изучении электрических цепей. В 1857 году Артур Кэли изучал число изомеров органического соединения с помощью графов, в которых точки соединялись между собой одной или четырьмя линиями — по числу химических связей. В 1869 году Мари Энмон Камиль Жордан занимался анализом абстрактных древовидных структур. В 1859 году ирландский математик Уильям Роуэн Гамильтон придумал игру (о ней мы расскажем несколько позже), цель которой — обойти вершины многогранника. Несколько лет спустя на основе этой игры были созданы гамильтоновы цепи, которые имеют очень интересное применение. В 1852 году возникла задача о раскраске карт таким образом, чтобы страны с общей границей были окрашены в разные цвета. Эта задача дала начало множеству исследований графов. Психолог Курт Левин ввел в психологию схемы, на которых люди обозначались точками, а личные отношения между ними — линиями. Физики Уленбек, Ли и Янг использовали схемы из точек и линий для изображения структур молекул и взаимодействия между ними.