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

Типы графов Теория графов

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

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

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

  • Неориентированные

  • Направленные

  • Взвешенные

Разберем каждый тип подробнее.

Неориентированные графы

Неориентированными называют графы, если между их узлами нет заданных направлений. Поэтому ребро из узла в будет идентично ребру из в :

eyJpZCI6IjA3ZmIzN2JjNDRjZjQ1ZDA5N2QwNzk3ZTFiYjBlMzIwLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=9c532730f12c56e30945259dde51560ee987e97bcb82741c95b7a52cdbd47fd9

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

Направленные графы

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

eyJpZCI6IjkxYjVmY2QzMjVjOTkwYzdlNzQ1NzJlY2MxZTMyZjUzLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=b84d64477ecbb0a34ce5f1cecc1604be1c1d3970a985453b235d62c78e9cba4b

Снова представим, что узлы — это города. У нас есть направление из города 1 в город 2. Получается, вы можете проехать по этому пути, но не обратно в город 1, так как нет направления обратно в город 1 из города 2. При этом у граф может быть двунаправленным. Например, города 3 и 4 имеют направления в обе стороны.

Взвешенные графы

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

eyJpZCI6IjJiZWM3YWJjMzMyODdmNGUzZTVjMzljOGNhMWRkYWI2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=af19d12ed44e9993a998f5c2157e319419a9aa88d72cf8cdbb0ee1100a903f18

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

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

Наиболее перспективными будут маршруты из зеленого в розовый через оранжевый и синий. Если весами являются затраты между городами, то нам придется потратить 11 долларов на поездку через синий город, чтобы добраться до розового. Если мы воспользуемся другим маршрутом через оранжевый город, то нам придется заплатить за поездку всего десять долларов.

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

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

Выводы

В этом уроке мы познакомились с тремя основными типами графов:

  • Неориентированные графы без заданных направлений

  • Направленные с указанными направлениями

  • Взвешенные с весами — числами на ребрах

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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