Теория графов применяется, чтобы решать задачи разного типа. Например, нам нужно найти путь из одного города в другой, съездить туда и обратно или узнать стоимость перевозки. Чтобы правильно решить поставленную задачу, применяют графы разных типов.
В этом уроке разберем, какие типы графов существуют и для каких задач они подходят.
Когда мы работаем с задачей, нужно понимать, с каким типом графов работаем. Выделим три основных типа:
- Неориентированные
- Направленные
- Взвешенные
Разберем каждый тип подробнее.
Неориентированные графы
Неориентированными называют графы, если между их узлами нет заданных направлений. Поэтому ребро из узла A в B будет идентично ребру из B в A:
В приведенном выше графе каждый узел может представлять различные города, а ребра показывают двунаправленные дороги.
Направленные графы
У направленных графов или диграфов есть ориентация или направление между узлами. Получается, если есть ребро из узла A в B, вы можете двигаться только из A в B, так как другое направление не указано:
Снова представим, что узлы — это города. У нас есть направление из города 1 в город 2. Получается, вы можете проехать по этому пути, но не обратно в город 1, так как нет направления обратно в город 1 из города 2. При этом граф может быть двунаправленным. Например, города 3 и 4 имеют направления в обе стороны.
Взвешенные графы
У взвешенных графов есть ребра, которым присвоены весы — некоторые числа. Например, они могут отражать стоимость перевозки груза, расстояние, которое нужно преодолеть. Это данные, с которыми нам нужно проводить различные действия. Пример взвешенных графов:
Взвешенные графы бывают и направленными, и неориентированными. В примере выше неориентированный взвешенный граф. Стоимость или расстояние от зеленого узла до оранжевого и наоборот равна трем. Допустим, вы хотите проехать между двумя городами — зеленым и оранжевым. Значит, вам предстоит проехать три мили.
Эти метрики определяются самостоятельно и могут быть изменены в зависимости от ситуации. Предположим, вам нужно попасть в розовый город из зеленого. Если посмотреть на граф города, мы не найдем прямых дорог или ребер между этими двумя городами. Поэтому мы можем поехать через другой город.
Наиболее перспективными будут маршруты из зеленого в розовый через оранжевый и синий. Если весами являются затраты между городами, то нам придется потратить 11 долларов на поездку через синий город, чтобы добраться до розового. Если мы воспользуемся другим маршрутом через оранжевый город, то нам придется заплатить за поездку всего десять долларов.
Каждое ребро может иметь несколько весовых коэффициентов — расстояние, время в пути или денежные затраты. Такие взвешенные графы обычно используются для программирования GPS и поисковых систем планирования путешествий, которые сравнивают время и стоимость перелета.
Типы графов можно определять по признакам, которые мы разобрали в этом уроке. Например, если вы увидите направление от одного узла к другому — это диграфы. Если у них еще есть ребра с числами — это направленные взвешенные графы. Когда вы научитесь определять тип графов, то сможете правильно решать задачи.
Выводы
В этом уроке мы познакомились с тремя основными типами графов:
- Неориентированные графы без заданных направлений
- Направленные с указанными направлениями
- Взвешенные с весами — числами на ребрах
Эти знания помогут вам верно выбирать тип графа под реальную задачу и наглядно показывать свои вычисления.
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
