Изменения
Нет описания правки
'''Ориентированным графом''' <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]).
{|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 =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset V\{v_1times V: (u, v_2 v) \in VE \Rightarrow (v, u) \}in E)</tex> {{---}} множество рёбер.
}}
{{Определение
{{Определение
|definition =
'''Неориентированным графом''' <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 EV: \operatorname{ends}(v_1, v_2) \implies \operatorname{ends}(v_2, v_1)</tex>
}}
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
Если граф разрежен (sparse graph, <tex>|E| < = O(|V^k|), 1 < k < 2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
=== Матрица инцидентности ===
