Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Введение Теория графов

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

Базовые знания по этой теме помогут решать интересные задачи, с которыми вы можете столкнуться в другим разделах математики и в программировании.

В этом курсе мы рассмотрим конкретные примеры и на них мы покажем, как теория графов помогает:

  • Планировать и оптимизировать маршруты

  • Ориентироваться в тысячах товаров на складах

  • Эффективно распределять товары по пунктах приема

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

История теории графов

Основную идею графов впервые представил Леонгард Эйлер, одним из выдающихся математиков 18 века. Он активно работал над знаменитой «проблемой семи мостов Кенигсберга», и эти исследования считаются началом теории графов.

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

Чтобы решить эту задачу, Эйлер нарисовал первое визуальное представление современного графа. Посмотрим на рисунок ниже:

eyJpZCI6ImViZjY1N2IwZjEwN2FkZWM3ZTEwMmYxOTNjMDNkYzhiLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=bc606bef77d45edf1bb675c25703303efb1e1b649e845b871057115dd90ba559

Именно так и выглядит современный граф:

  • Это набор точек — их называют вершинами или узлами

  • Эти точки соединены линиями — их называют ребрами

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

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

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

Введение в теорию графов

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

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

Теперь попробуем раскрыть подробнее это расплывчатое описание и приведем реальные примеры. Теория графов помогает:

  • Выстаивать системы рекомендаций в Facebook, Instagram, LinkedIn и других соцсетях

  • Отслеживать распространение COVID-19 и других заболеваний

  • Обрабатывать запросы в поисковых системах и ранжировать результаты

  • Строить кратчайшие маршруты в Google Maps и других картах

  • Изучать взаимодействие молекул и атомов в химии

  • Секвенировать ДНК

  • Обеспечивать безопасность компьютерных сетей

Выводы

В этом уроке мы познакомились с теорией графов и изучили, как она применяется на практике. Мы выяснили, что такое графы и как они помогают решать конкретные задачи — переходить от практики к абстракции. Эти базовые знания о графах мы освоили на примере «задачи Кенинсберга» — популярной задачи, с которой и началась теория графов в 18 веке.


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»

Изображение Тото

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