Теория графов
2026-02-26 22:29 Diff
https://ru.hexlet.io/courses/graphs/lessons/digraphs/theory_unit

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

Что такое диграф

В теории графов существует понятие направленного графа или диграфа, когда к ребрам добавляют направление:

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

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

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

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

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

Направленные пути и циклы в диграфе — это пути и циклы, которые учитывают ориентацию ребер. Например, ниже показаны направленный путь 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 в сумму заступов.

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

Есть версия и для сильно связанных диграфов — то есть для диграфов, в которых существует путь из любой вершины в любую другую, или граф содержит ровно одну сильно связную компоненту. Рассмотрим ее:

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

Теперь разберем, как можно представить диграфы.

Представление диграфов

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

Если вы посмотрите на оригинал, то увидите, что этот класс digraph точно такой же, только в нем нет строки self[v]`` иappend(u)в методеadd_edge`. Это то, что делает ребра двусторонними в обычном графе. Если ее не добавить, мы получим одностороннее ребро.

Выводы

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