Изменения
→Ориентированные графы
{{Определение
|definition=
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
}}
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b> (англ. ''loop''). Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2=(v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные''' (англ. ''adjacent'')* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
'''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
|id = def1
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>. Такой граф иногда называют '''псевдографом''' (англ. ''pseudograph'').
}}
Такой граф <tex>G</tex> иногда называют '''псевдографом''' (англ. ''pseudograph'').В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Псевдограф без петель принято называть '''мультиграфом'''(англ. ''multigraph'').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Синим</font> обозначена петля (6, 6)]]
|}
{{Определение|definition=Также для Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e~|~\mid \operatorname{beg(e)}~e = v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e~|~\mid \operatorname{end(e)}~e = v_i\}|</tex>.}}
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
