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

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

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

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

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

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

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

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

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

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

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

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

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