35
правок
Изменения
→Ориентированные графы
{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{- --}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{--- }} множество рёбер. '''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
Заметим, что '''инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют <b>тривиальным</b>.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
{{Определение
|definition =
'''Ориентированным графом''' <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)]]
{{Определение
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{- --}} это две последовательности ребер в циклическом пути.
}}
