29
правок
Изменения
→Представление графов
=== Матрица и списки смежности ===
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
Если граф разрежен (англ. ''sparse graph'', <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
=== Пути в графах ===
{{Определение
|definition =
'''Путём''' (маршрутом, англ. ''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> {{---}} '''длина''' пути.
}}
{{Определение
|definition =
'''Циклическим путём''' (англ. ''closed walk'') в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' (англ. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}
