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

Клауди Альсина «Мир математики» № 11 « Карты метро и нейронные сети . Теория графов»

Красота математики столь совершенна, что самое красивое и правильное также оказывается самым полезным.

Дарси Томпсон

Предисловие

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

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

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

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

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

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

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

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

Глава 1 Знакомство с графами

Хорошо да коротко — вдвойне хорошо.

Народная мудрость

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

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

Из Кёнигсберга с любовью

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

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

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