168
правок
Изменения
→Ориентированные графы
{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер. '''Ребром''' ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''. Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> v </tex> - <b>предок</b> <tex> u </tex>. Также вершины <tex> u </tex> и <tex> v </tex> называют <b>смежными</b>. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют <b>тривиальным</b>. Заметим, что по такому определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
}}
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли (см. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|<font color=#ED1C24>Красным</font> выделено кратное ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф<br> б) Псевдограф]]
|}
Так же для ориентированных графов определяют '''полустепень захода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex>.<br>и '''полустепень исхода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.<br>
Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:
{{Определение
|definition =
'''Путём''' в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>.
}}
{{Определение
