Изменения

'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.

 Иногда граф, построенный таким образом, называют '''псевдографом''' (multigraphpseudograph). В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', multi-edge, parallel edge). Псевдограф без петель принято называть '''мультиграфом'''.

'''Цикл''' (integral cycle) {{---}} это [[Отношение эквивалентности#Класс эквивалентности|класс эквивалентности ]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.

'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset V\times V: ({\{v, u, v) \in E \Rightarrow (}: v, u) \in E)V\}</tex> {{---}} множество рёбер.

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

'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>\operatorname{ends} : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, причем а <tex>\forall v_1, v_2 \in V: \operatorname{ends} (v_1, v_2) : e \implies mapsto \operatorname{endsu, v\} (v_2; e\in E; u, v_1)v \in V</tex> .

'''Степенью''' (degree, valency) вершины <tex>\operatorname{deg}~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Если граф разрежен (sparse graph, <tex>|E| << \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.