Изменения

'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин(vertices), а <tex> E \subset V \times V </tex> {{---}} множество рёбер(edges, дуг (arcs), линий (lines)).}} {{Определение|definition ='''Конечным графом''' (finite graph) <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.

В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''(loop).

* <tex> v </tex> {{---}} '''предок''' (direct predecessor) <tex> u </tex>.* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''(adjacent)

'''Ориентированным графом''' <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> {{---}} некоторые абстрактные множества.

Иногда граф, построенный таким образом, называют '''мультиграфом'''(multigraph). В мультиграфе не допускаются петли, но пары вершин допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', multi-edge, parallel edge). Мультиграф с петлями принято называть '''псевдографом''' ([http://mathworld.wolfram.com/Pseudograph.html pseudograph]).

Также для ориентированных графов определяют '''полустепень исхода вершины''' (outdegree) <tex>\operatorname{deg}^-+v_i = |\{e~|~\operatorname{beg}~e = v_i\}|</tex> и '''полустепень захода вершины''' (indegree) <tex>\operatorname{deg}^+-v_i = |\{e~|~\operatorname{end}~e = v_i\}|</tex>.

'''Путём''' (маршрутом, path) в графе называется последовательность вида <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>; <tex>k</tex> {{---}} '''длина''' пути.

'''Циклическим путём''' (closed walk) называется путь, в котором <tex>v_0 = v_k</tex>.

'''Цикл''' (integral cycle) {{---}} это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow 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(uv \sim vu~\backslash~\{uu~|~u v_1, v_2 \in V\})</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 E: \operatorname{ends}(v_1, v_2) \implies \operatorname{ends}(v_2, v_1)</tex>

Две вершины называются '''смежными'''(adjacent), если между ними есть ребро.

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]](adjacency matrix), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).

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