В этом уроке мы познакомимся с направленным графом — диграфом. Также расскажем, чем он отличается от обычного графа и как его можно построить и представить.
Что такое диграф
В теории графов существует понятие направленного графа или диграфа, когда к ребрам добавляют направление:
Диграфы применяют для моделирования дорожных сетей. Неориентированный граф может моделировать только двусторонние дороги, но направленный граф дает возможность построить дорогу и с односторонним движением.
Если дорожная сеть состоит из дорог с односторонним и двусторонним движением, мы можем использовать пары направленных ребер. Например, по одному в каждом направлении для дорог с двусторонним движением.
В качестве другого примера можно привести графы, которые часто используются для моделирования состояний в игре. Состояния — это вершины, а ребра между вершинами указывают на возможность перехода из одного состояния в другое в игре.
Во многих играх ходы работают только в одну сторону, как в шашках или шахматах. Поэтому для моделирования состояний многих игр больше подходит направленный граф, чем неориентированный.
Если ребра графа — это двухэлементные подмножества вершин, то в направленном графе вместо подмножеств мы используем упорядоченные пары для ребер.
Направленные пути и циклы в диграфе — это пути и циклы, которые учитывают ориентацию ребер. Например, ниже показаны направленный путь abcdh и направленный цикл abc g f ea:
В обоих случаях все ребра идут в одном направлении, когда вы прослеживаете путь и цикл. Граф, который лежит в основе диграфа, получен из диграфа удалением всех направлений из ребер.
Один из способов построения диграфа — взять обычный граф и добавить направления к его ребрам. Это называется ориентацией графа.
Диграф — это пара (V, E), где:
V— множество объектов (вершины)E— коллекция упорядоченных пар элементовV(направленные ребра)
Направленное ребро из u в v мы обычно записываем как u → v. Вершина u называется головной, а v - хвостовой. Мы также можем создавать мультиграфы, в которых разрешены циклы и множественные ребра.
Понятие степени вершины теперь разделяется на два понятия: indegree и outdegree. Indegree (полустепень захода вершины) вершины v — это общее количество ребер, направленных из других вершин в v, а outdegree (полустепень исхода вершины) — общее количество ребер, направленных из v в другие вершины.
Чтобы лучше разобраться с диграфами, рассмотрим несколько теорем.
Теоремы о диграфах
Одной из первых теорем, которую мы рассмотрели, была формула Degree sum — сумма степеней вершин в графе в два раза больше числа ребер. У нее есть аналог для диграфов.
Теорема для формулы суммы степеней для диграфов. В любом диграфе сумма полустепеней захода вершины всех вершин равна количеству ребер в диграфе. Аналогично — сумма отступов всех вершин равна количеству ребер в диграфе.
Докажем данную теорему. У каждого ребра есть голова и хвост. Голова вносит 1 в сумму отступов, а хвост — 1 в сумму заступов.
Теорема о четных степенях для эйлеровых графов также имеет хороший аналог для диграфов. Напомним, что у графа есть эйлеровая схема, когда каждая вершина имеет четную степень.
Есть версия и для сильно связанных диграфов — то есть для диграфов, в которых существует путь из любой вершины в любую другую, или граф содержит ровно одну сильно связную компоненту. Рассмотрим ее:
У сильно связного диграфа есть эйлерова схема, когда полустепени захода вершины каждой вершины совпадают с ее полустепенями исхода вершины
Теперь разберем, как можно представить диграфы.
Представление диграфов
Ранее мы представляли граф в виде списка смежности. Вот вариант для диграфа:
class Digraph(dict):
def add(self, v):
if v not in self:
self[v] = []
def add_edge(self, u, v):
self[u].append(v)
Если вы посмотрите на оригинал, то увидите, что этот класс digraph точно такой же, только в нем нет строки self[v]иappend(u)в методеadd_edge`. Это то, что делает ребра двусторонними в обычном графе. Если ее не добавить, мы получим одностороннее ребро.
Выводы
В этом уроке мы познакомились с направленным графом — диграфом. Чтобы его построить, нужно взять обычный граф и добавить направления к его ребрам. Этим он и будет отличаться от обычного графа. Диграфы помогают моделировать дорожные сети не только с двусторонним движением, но и с односторонним.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
