Изменения

'''Ориентированным графом ''' <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер.

[[Файл: Multigraphdirected_graph.png|thumb|300px|right|аОриентированный граф<br><font color=#ED1C24>Красным</font> выделено ребро (6, 2) мультиграф<br> б<font color=#22B14C>Зеленым</font> обозначена петля (6, 6) псевдограф]]Есть еще Заметим, что по такому определению любые две вершины <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> - некоторые абстрактные множества. Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли (см. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').

'''Ребром ''' (дугой) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.

{{ОпределениеТак же еще для ориентированных графов определяют '''полустепень входа вершины'''.|definition =Полустепенью входа вершины <tex>deg^-v_i= |\{e~|beg~e = v\}|</tex> называется число рёбер, входящих в эту вершину, и обозначается .<br><tex>deg^+v_i= |\{e~|end~e = v\}|</tex>.<br>АналогичноДокажем, полустепенью выхода вершины что выполнено следующее равенство: <tex>\sum\limits_{v\in V(G)}deg^-v_i</tex> называется число рёбер, выходящих из этой вершины, и обозначается <tex>= \sum\limits_{v\in V(G)}deg^-+v_i= |E|</tex>.<br> }}У каждого ребра ровно одно начало и ровно один конец.