122 added
3 removed
Original
2026-01-01
Modified
2026-02-26
1
-
<p>Ориентированный граф (directed graph) - это структура данных, которая представляет собой множество вершин и направленных ребер, соединяющих эти вершины. Ориентированные графы используются для моделирования систем, в которых элементы связаны друг с другом в определенном направлении, например, в сетях передачи данных, маршрутизации, планировании и т. д.</p>
1
+
<p>Ориентированный граф - это структура данных, состоящая из множества вершин и направленных ребер. Каждое ребро задает направление движения от одной вершины к другой. Такая модель применяется в математике, программировании, анализе систем, когда важно учитывать порядок переходов между элементами.</p>
2
-
<p>2 года назад</p>
2
+
<p>Ориентированные графы позволяют описывать зависимости, последовательности, маршруты, потоки данных. В отличие от неориентированных, здесь каждое соединение имеет направление, что ограничивает возможные траектории обхода структуры. Если граф представить как карту, вершины будут точками, а ребра - дорогами, но все дороги односторонние. Это ключевое свойство, определяющее специфику поведения алгоритмов.</p>
3
-
<p>Елена Редькина</p>
3
+
<h2>Разновидности</h2>
4
+
<p>Граф может описывать связи между любыми сущностями: компонентами системы, элементами алгоритма, участниками взаимодействия. Визуально структура представляется в виде точек и соединяющих их линий, но в вычислительных системах используется внутреннее представление.</p>
5
+
<p>Графы подразделяются на два основных класса:</p>
6
+
<ul><li><p>Неориентированные. Ребра не имеют направления. Переход возможен в обе стороны.</p>
7
+
</li>
8
+
<li><p>Ориентированные. Все ребра направлены. Направление определяет валидный маршрут обхода.</p>
9
+
</li>
10
+
</ul><p>Если ребро отображается как стрелка, оно задает единственно допустимое направление движения. Двойная стрелка является эквивалентом двух отдельных ориентированных ребер.</p>
11
+
<p>Понятие направления формирует правила переходов. Из вершины A можно перейти в B только при наличии ребра A→B. Обратный переход невозможен без отдельного ребра B→A.</p>
12
+
<h2>Сфера применения</h2>
13
+
<p>Ориентированные графы применяются при моделировании процессов, структур, цепочек зависимостей. Они позволяют формально представить причинно-следственные связи, последовательности действий, архитектуру взаимодействий.</p>
14
+
<p>Использование актуально в различных дисциплинах:</p>
15
+
<ul><li><p>математике - для описания абстрактных структур и отношений;</p>
16
+
</li>
17
+
<li><p>инженерии - для представления электрических и технологических цепей;</p>
18
+
</li>
19
+
<li><p>информатике - для построения сложных структур данных, анализа сетей, маршрутизации и расчета зависимостей;</p>
20
+
</li>
21
+
<li><p>логике - для моделирования условий и следствий;</p>
22
+
</li>
23
+
<li><p>социальных и гуманитарных исследованиях - для отображения направленных взаимодействий между объектами.</p>
24
+
</li>
25
+
</ul><p>Ориентированный граф используется там, где важен порядок переходов и влияние одного элемента системы на другой.</p>
26
+
<h2>Основные понятия графов</h2>
27
+
<p>Для корректного описания графов используется стандартный набор терминов.</p>
28
+
<ul><li><p>Вершина. Базовый элемент структуры. Представляет объект или состояние.</p>
29
+
</li>
30
+
<li><p>Ребро. Соединение между двумя вершинами. В ориентированном графе - направленное.</p>
31
+
</li>
32
+
<li><p>Путь. Последовательность вершин, соединенных ребрами без повторения самих ребер.</p>
33
+
</li>
34
+
<li><p>Простой путь. Последовательность без повторяющихся вершин.</p>
35
+
</li>
36
+
<li><p>Цикл. Замкнутый путь, в котором первая и последняя вершина совпадают.</p>
37
+
</li>
38
+
<li><p>Связный граф. Граф, где из любой вершины можно попасть в любую другую.</p>
39
+
</li>
40
+
<li><p>Дерево. Связный граф без циклов. Широко используется в алгоритмах и данных.</p>
41
+
</li>
42
+
<li><p>Полный граф. Каждая пара вершин соединена ребром (в ориентированном - ориентированным).</p>
43
+
</li>
44
+
<li><p>Петля. Ребро, начинающееся и заканчивающееся в одной вершине.</p>
45
+
</li>
46
+
</ul><p>Эти определения применимы и к ориентированным, и к неориентированным графам, но в ориентированном варианте добавляются дополнительные характеристики.</p>
47
+
<h2>Термины, специфичные для ориентированных графов</h2>
48
+
<p>Ориентированные графы требуют уточнения свойств, связанных с направлением ребер.</p>
49
+
<ul><li><p>Степень выхода. Количество ребер, исходящих из вершины.</p>
50
+
</li>
51
+
<li><p>Степень входа. Количество ребер, входящих в вершину.</p>
52
+
</li>
53
+
<li><p>Изолированная вершина. Вершина, у которой нет входящих и выходящих ребер.</p>
54
+
</li>
55
+
<li><p>Источник. Вершина с нулевой степенью входа и положительной степенью выхода.</p>
56
+
</li>
57
+
<li><p>Сток. Вершина с нулевой степенью выхода и положительной степенью входа.</p>
58
+
</li>
59
+
<li><p>Ориентированный цикл. Цикл, включая только направленные ребра, образующие замкнутый путь.</p>
60
+
</li>
61
+
<li><p>Полный ориентированный граф. Каждая пара вершин соединена одним уникальным направленным ребром.</p>
62
+
</li>
63
+
</ul><p>Эти показатели позволяют анализировать структуру и поведение систем, основанных на графах.</p>
64
+
<h2>Представление ориентированных графов в программировании</h2>
65
+
<p>Для вычислительных целей граф необходимо хранить в виде структуры данных. Наиболее распространены два формата: матрица смежности и список смежности. Они обеспечивают разные свойства по памяти, скорости и удобству реализации алгоритмов.</p>
66
+
<h3>Матрица смежности</h3>
67
+
<p>Матрица смежности - это квадратная таблица N×N, где N - количество вершин. Строки и столбцы соответствуют вершинам. На пересечении строки i и столбца j хранится значение:</p>
68
+
<ul><li><p>1 - есть ребро i→j;</p>
69
+
</li>
70
+
<li><p>0 - отсутствует ребро.</p>
71
+
</li>
72
+
</ul><p>Свойства метода:</p>
73
+
<ul><li><p>одинаково применим к ориентированным и неориентированным графам;</p>
74
+
</li>
75
+
<li><p>позволяет быстро проверять наличие ребра;</p>
76
+
</li>
77
+
<li><p>эффективен для плотных графов, где количество ребер близко к N²;</p>
78
+
</li>
79
+
<li><p>потребляет много памяти при малом числе связей, так как таблица содержит много нулей.</p>
80
+
</li>
81
+
</ul><h3>Список смежности</h3>
82
+
<p>Список смежности - это набор массивов, где каждый массив содержит вершину и перечень ее соседей, достижимых по исходящим ребрам.</p>
83
+
<p>Особенности:</p>
84
+
<ul><li><p>экономия памяти при работе с разреженными графами;</p>
85
+
</li>
86
+
<li><p>удобный доступ к исходящим связям каждой вершины;</p>
87
+
</li>
88
+
<li><p>использование в алгоритмах обхода, где важны локальные переходы;</p>
89
+
</li>
90
+
<li><p>менее удобен для проверки произвольного ребра i→j.</p>
91
+
</li>
92
+
</ul><p>Для неориентированного графа каждый переход A-B хранится дважды, для ориентированного - только по направлению ребра.</p>
93
+
<h2>Алгоритмы, использующие ориентированные графы</h2>
94
+
<p>Ориентированные графы применяются в широком спектре алгоритмов анализа связей, поиска путей и обработки зависимостей. Они встречаются в задачах маршрутизации, оптимизации, анализа процессов и построения вычислительных моделей.</p>
95
+
<h3>Поиск в глубину (DFS)</h3>
96
+
<p>DFS проходит граф, углубляясь по доступным ребрам. Алгоритм двигается по направлению стрелок, помечает посещенные вершины, избегает повторов и возвращается назад при отсутствии новых исходящих ребер. Метод используется для:</p>
97
+
<ul><li><p>поиска путей,</p>
98
+
</li>
99
+
<li><p>выявления циклов,</p>
100
+
</li>
101
+
<li><p>построения компонент достижимости.</p>
102
+
</li>
103
+
</ul><h3>Поиск в ширину (BFS)</h3>
104
+
<p>BFS перемещается по слоям: сначала обходит всех соседей исходной вершины, затем - соседей следующего уровня. В ориентированных графах BFS учитывает направление переходов и применяется для:</p>
105
+
<ul><li><p>нахождения минимальных расстояний,</p>
106
+
</li>
107
+
<li><p>анализа структуры и уровней,</p>
108
+
</li>
109
+
<li><p>задач маршрутизации.</p>
110
+
</li>
111
+
</ul><h3>Топологическая сортировка</h3>
112
+
<p>Топологическая сортировка упорядочивает вершины так, чтобы каждое ребро направляло от более раннего элемента к более позднему. Метод применим только к ацикличным ориентированным графам.</p>
113
+
<p>Используется для:</p>
114
+
<ul><li><p>работы с зависимостями,</p>
115
+
</li>
116
+
<li><p>планирования задач,</p>
117
+
</li>
118
+
<li><p>анализа очередности операций.</p>
119
+
</li>
120
+
</ul><h3>Задача 2-SAT</h3>
121
+
<p>2-SAT сводится к построению ориентированного графа импликаций, где каждая переменная имеет вершины x и ¬x. Для каждого условия добавляются импликации. Решение существует, если не существует пути из x в ¬x и обратного пути одновременно.</p>
122
+
<p>Алгоритм применяется для задач, где переменные имеют два возможных состояния.</p>