0 added
0 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>В этом уроке мы познакомимся с направленным графом - диграфом. Также расскажем, чем он отличается от обычного графа и как его можно построить и представить.</p>
1
<p>В этом уроке мы познакомимся с направленным графом - диграфом. Также расскажем, чем он отличается от обычного графа и как его можно построить и представить.</p>
2
<h2>Что такое диграф</h2>
2
<h2>Что такое диграф</h2>
3
<p>В теории графов существует понятие<strong>направленного графа</strong>или<strong>диграфа</strong>, когда к ребрам добавляют направление:</p>
3
<p>В теории графов существует понятие<strong>направленного графа</strong>или<strong>диграфа</strong>, когда к ребрам добавляют направление:</p>
4
<p>Диграфы применяют для моделирования дорожных сетей. Неориентированный граф может моделировать только двусторонние дороги, но направленный граф дает возможность построить дорогу и с односторонним движением.</p>
4
<p>Диграфы применяют для моделирования дорожных сетей. Неориентированный граф может моделировать только двусторонние дороги, но направленный граф дает возможность построить дорогу и с односторонним движением.</p>
5
<p>Если дорожная сеть состоит из дорог с односторонним и двусторонним движением, мы можем использовать пары направленных ребер. Например, по одному в каждом направлении для дорог с двусторонним движением.</p>
5
<p>Если дорожная сеть состоит из дорог с односторонним и двусторонним движением, мы можем использовать пары направленных ребер. Например, по одному в каждом направлении для дорог с двусторонним движением.</p>
6
<p>В качестве другого примера можно привести графы, которые часто используются для моделирования состояний в игре.<strong>Состояния</strong>- это вершины, а ребра между вершинами указывают на возможность перехода из одного состояния в другое в игре.</p>
6
<p>В качестве другого примера можно привести графы, которые часто используются для моделирования состояний в игре.<strong>Состояния</strong>- это вершины, а ребра между вершинами указывают на возможность перехода из одного состояния в другое в игре.</p>
7
<p>Во многих играх ходы работают только в одну сторону, как в шашках или шахматах. Поэтому для моделирования состояний многих игр больше подходит направленный граф, чем неориентированный.</p>
7
<p>Во многих играх ходы работают только в одну сторону, как в шашках или шахматах. Поэтому для моделирования состояний многих игр больше подходит направленный граф, чем неориентированный.</p>
8
<p>Если ребра графа - это двухэлементные подмножества вершин, то в направленном графе вместо подмножеств мы используем упорядоченные пары для ребер.</p>
8
<p>Если ребра графа - это двухэлементные подмножества вершин, то в направленном графе вместо подмножеств мы используем упорядоченные пары для ребер.</p>
9
<p>Направленные пути и циклы в диграфе - это пути и циклы, которые учитывают ориентацию ребер. Например, ниже показаны направленный путь abcdh и направленный цикл abc g f ea:</p>
9
<p>Направленные пути и циклы в диграфе - это пути и циклы, которые учитывают ориентацию ребер. Например, ниже показаны направленный путь abcdh и направленный цикл abc g f ea:</p>
10
<p>В обоих случаях все ребра идут в одном направлении, когда вы прослеживаете путь и цикл. Граф, который лежит в основе диграфа, получен из диграфа удалением всех направлений из ребер.</p>
10
<p>В обоих случаях все ребра идут в одном направлении, когда вы прослеживаете путь и цикл. Граф, который лежит в основе диграфа, получен из диграфа удалением всех направлений из ребер.</p>
11
<p>Один из способов построения диграфа - взять обычный граф и добавить направления к его ребрам. Это называется<strong>ориентацией графа</strong>.</p>
11
<p>Один из способов построения диграфа - взять обычный граф и добавить направления к его ребрам. Это называется<strong>ориентацией графа</strong>.</p>
12
<p>Диграф - это пара (V, E), где:</p>
12
<p>Диграф - это пара (V, E), где:</p>
13
<ul><li>V - множество объектов (вершины)</li>
13
<ul><li>V - множество объектов (вершины)</li>
14
<li>E - коллекция упорядоченных пар элементов V (направленные ребра)</li>
14
<li>E - коллекция упорядоченных пар элементов V (направленные ребра)</li>
15
</ul><p>Направленное ребро из u в v мы обычно записываем как u → v. Вершина u называется головной, а v - хвостовой. Мы также можем создавать мультиграфы, в которых разрешены циклы и множественные ребра.</p>
15
</ul><p>Направленное ребро из u в v мы обычно записываем как u → v. Вершина u называется головной, а v - хвостовой. Мы также можем создавать мультиграфы, в которых разрешены циклы и множественные ребра.</p>
16
<p>Понятие степени вершины теперь разделяется на два понятия: indegree и outdegree.<strong>Indegree</strong>(полустепень захода вершины) вершины v - это общее количество ребер, направленных из других вершин в v, а<strong>outdegree</strong>(полустепень исхода вершины) - общее количество ребер, направленных из v в другие вершины.</p>
16
<p>Понятие степени вершины теперь разделяется на два понятия: indegree и outdegree.<strong>Indegree</strong>(полустепень захода вершины) вершины v - это общее количество ребер, направленных из других вершин в v, а<strong>outdegree</strong>(полустепень исхода вершины) - общее количество ребер, направленных из v в другие вершины.</p>
17
<p>Чтобы лучше разобраться с диграфами, рассмотрим несколько теорем.</p>
17
<p>Чтобы лучше разобраться с диграфами, рассмотрим несколько теорем.</p>
18
<h2>Теоремы о диграфах</h2>
18
<h2>Теоремы о диграфах</h2>
19
<p>Одной из первых теорем, которую мы рассмотрели, была формула<strong>Degree sum</strong>- сумма степеней вершин в графе в два раза больше числа ребер. У нее есть аналог для диграфов.</p>
19
<p>Одной из первых теорем, которую мы рассмотрели, была формула<strong>Degree sum</strong>- сумма степеней вершин в графе в два раза больше числа ребер. У нее есть аналог для диграфов.</p>
20
<p>Теорема для формулы суммы степеней для диграфов. В любом диграфе сумма полустепеней захода вершины всех вершин равна количеству ребер в диграфе. Аналогично - сумма отступов всех вершин равна количеству ребер в диграфе.</p>
20
<p>Теорема для формулы суммы степеней для диграфов. В любом диграфе сумма полустепеней захода вершины всех вершин равна количеству ребер в диграфе. Аналогично - сумма отступов всех вершин равна количеству ребер в диграфе.</p>
21
<p>Докажем данную теорему. У каждого ребра есть голова и хвост. Голова вносит 1 в сумму отступов, а хвост - 1 в сумму заступов.</p>
21
<p>Докажем данную теорему. У каждого ребра есть голова и хвост. Голова вносит 1 в сумму отступов, а хвост - 1 в сумму заступов.</p>
22
<p>Теорема о четных степенях для эйлеровых графов также имеет хороший аналог для диграфов. Напомним, что у графа есть эйлеровая схема, когда каждая вершина имеет четную степень.</p>
22
<p>Теорема о четных степенях для эйлеровых графов также имеет хороший аналог для диграфов. Напомним, что у графа есть эйлеровая схема, когда каждая вершина имеет четную степень.</p>
23
<p>Есть версия и для сильно связанных диграфов - то есть для диграфов, в которых существует путь из любой вершины в любую другую, или граф содержит ровно одну сильно связную компоненту. Рассмотрим ее:</p>
23
<p>Есть версия и для сильно связанных диграфов - то есть для диграфов, в которых существует путь из любой вершины в любую другую, или граф содержит ровно одну сильно связную компоненту. Рассмотрим ее:</p>
24
<p>У сильно связного диграфа есть эйлерова схема, когда полустепени захода вершины каждой вершины совпадают с ее полустепенями исхода вершины</p>
24
<p>У сильно связного диграфа есть эйлерова схема, когда полустепени захода вершины каждой вершины совпадают с ее полустепенями исхода вершины</p>
25
<p>Теперь разберем, как можно представить диграфы.</p>
25
<p>Теперь разберем, как можно представить диграфы.</p>
26
<h2>Представление диграфов</h2>
26
<h2>Представление диграфов</h2>
27
<p>Ранее мы представляли граф в виде списка смежности. Вот вариант для диграфа:</p>
27
<p>Ранее мы представляли граф в виде списка смежности. Вот вариант для диграфа:</p>
28
<p>Если вы посмотрите на оригинал, то увидите, что этот класс digraph точно такой же, только в нем нет строки self[v]`` иappend(u)в методеadd_edge`. Это то, что делает ребра двусторонними в обычном графе. Если ее не добавить, мы получим одностороннее ребро.</p>
28
<p>Если вы посмотрите на оригинал, то увидите, что этот класс digraph точно такой же, только в нем нет строки self[v]`` иappend(u)в методеadd_edge`. Это то, что делает ребра двусторонними в обычном графе. Если ее не добавить, мы получим одностороннее ребро.</p>
29
<h2>Выводы</h2>
29
<h2>Выводы</h2>
30
<p>В этом уроке мы познакомились с направленным графом - диграфом. Чтобы его построить, нужно взять обычный граф и добавить направления к его ребрам. Этим он и будет отличаться от обычного графа. Диграфы помогают моделировать дорожные сети не только с двусторонним движением, но и с односторонним.</p>
30
<p>В этом уроке мы познакомились с направленным графом - диграфом. Чтобы его построить, нужно взять обычный граф и добавить направления к его ребрам. Этим он и будет отличаться от обычного графа. Диграфы помогают моделировать дорожные сети не только с двусторонним движением, но и с односторонним.</p>