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

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

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

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

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

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