Теория графов может показаться пугающей и абстрактной темой, которую сложно применить на практике. В этом курсе мы постараемся показать, что это не так. Дело в том, что на самом деле в теории графов существует огромное количество полезных и важных приложений, о которых мы и расскажем в следующих уроках.
Базовые знания по этой теме помогут решать интересные задачи, с которыми вы можете столкнуться в других разделах математики и в программировании.
В этом курсе мы рассмотрим конкретные примеры и на них мы покажем, как теория графов помогает:
-
Планировать и оптимизировать маршруты
-
Ориентироваться в тысячах товаров на складах
-
Эффективно распределять товары по пунктах приема
Как видите, графы помогают строить эффективные процессы и таким образом сокращать расходы. Поэтому эта абстрактная область математики активно применяется на практике, причем уже несколько веков.
История теории графов
Основную идею графов впервые представил Леонгард Эйлер, одним из выдающихся математиков 18 века. Он активно работал над знаменитой «проблемой семи мостов Кенигсберга», и эти исследования считаются началом теории графов.
В 18 века прусский город Кенигсберг располагался по обе стороны реки Прегель и находился на двух больших островах — Кнайпхоф и Ломзе. Эти острова и материковая часть города соединялись семью мостами. Такая география города вдохновила математиков поставить перед собой такую задачу: придумать такой маршрут по городу, который пересекал бы каждый из этих мостов один и только один раз.
Чтобы решить эту задачу, Эйлер нарисовал первое визуальное представление современного графа. Посмотрим на рисунок ниже:
Именно так и выглядит современный граф:
-
Это набор точек — их называют вершинами или узлами
-
Эти точки соединены линиями — их называют ребрами
Любой граф — это абстракция от практической задачи. Это видно на примере той же задачи с мостами. Найти путь по городу через семь мостов — это практическая задача. Чтобы ее решить, нужно свести решение к абстракции: извлечь из условия данные о вершинах и ребрах, а потом построить граф по ним.
В ходе своего исследования Эйлер доказал, что эта конкретная задача не имеет решения. В процессе он столкнулся с трудностью: на тот момент в математике не было инструментов, которые могли бы подтвердить нерешаемость задачи с математической точностью. Так появилась теория графов, но почти сразу она затихла на десятилетия.
В наше время она снова стала актуальна, и наконец-то ее начали активно применять. Далее мы обсудим, почему актуальность этой области так выросла.
Введение в теорию графов
В конечном счете теория графов изучает взаимосвязи. Учитывая набор узлов и связей, которые могут абстрагировать что угодно, от планировки города до компьютерных данных.
Именно поэтому теория графов стала полезным инструментом количественной оценки и упрощения динамических систем. С ее помощью можно решить многие проблемы с логистикой, упростить создание и оптимизацию сетей, прозрачнее согласовывать и эксплуатировать разные системы. При этом инструменты из теории графов применяются в информатике, физике, биологии, социальных науках и инженерии ПО.
Теперь попробуем раскрыть подробнее это расплывчатое описание и приведем реальные примеры. Теория графов помогает:
-
Выстраивать системы рекомендаций в Facebook, Instagram, LinkedIn и других соцсетях
-
Отслеживать распространение COVID-19 и других заболеваний
-
Обрабатывать запросы в поисковых системах и ранжировать результаты
-
Строить кратчайшие маршруты в Google Maps и других картах
-
Изучать взаимодействие молекул и атомов в химии
-
Секвенировать ДНК
-
Обеспечивать безопасность компьютерных сетей
Выводы
В этом уроке мы познакомились с теорией графов и изучили, как она применяется на практике. Мы выяснили, что такое графы и как они помогают решать конкретные задачи — переходить от практики к абстракции. Эти базовые знания о графах мы освоили на примере «задачи Кенигсберга» — популярной задачи, с которой и началась теория графов в 18 веке.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
