Изменения

==ГрафОриентированные графы== 

Графом '''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E);</tex> , где <tex>V </tex> {{--- конечное }} множество вершин(англ. ''vertices''), а <tex> E \subset V \times V </tex> {{--- }} множество рёбер.

Ребром называют неупорядоченную пару вершин '''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> (vназывается граф, u) \in в котором множества <tex>V</tex> и <tex>E </tex>{{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.

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

Степенью вершины '''Ориентированным графом''' <tex>v_iG</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>. }} Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Граф с кратными рёбрами принято называть '''мультиграфом''' (англ. ''multigraph''). Если в мультиграфе присутствуют петли, то такой граф называют '''псевдографом''' (англ. ''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)]]|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]||} {{Определение|definition=Для ориентированных графов определяют '''полустепень исхода вершины''' (англ. ''outdegree'') <tex>\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|</tex>, и обозначается '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg }^-v_i = |\{e \mid \; operatorname{end(e)} = v_i\}|</tex>.

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество рёбер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]]. ==Неориентированные графы==Для ориентированного графа={{Определение|id =def_undirected_graph_1|definition ='''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G =(V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.}}

Полустепенью входа вершины v_i называется число рёбер, входящих '''Ребром''' в эту вершину, и обозначается неориентированном графе называют неупорядоченную пару вершин <tex>deg^+v_i\{v, u\} \in E </tex>.

Полустепенью выхода вершины '''Неориентированным графом''' <tex>v_iG</tex> называется число рёбертройка <tex>G = (V, E, \operatorname{ends})</tex> , выходящих из этой вершинугде <tex>V</tex> {{---}} множество вершин, и обозначается <tex>deg^E</tex> {{---v_i}} множество рёбер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.

Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть '''Простым графом''' <tex>e=\{v,v\}G</tex>называется граф, в котором нет петель и кратных рёбер.

Путём в графе называется последовательность вида '''Степенью''' (англ. ''degree'', ''valency'') вершины <tex>v_0 e_1 v_1 ... e_k v_k\operatorname{deg} v_i</tex>; где в неориентированном графе называют число рёбер, инцидентных <tex>e_i = (v_{i-1}, v_i)</tex>.

Путь такой'''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex> }} Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе. == Представление графов == === Матрица и списки смежности === Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''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>. Данный способ позволит сэкономить память, так как не придется хранить много нулей. === Пути в графах ==={{Определение|id = path|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), k</tex> {{---}} '''длина''' (англ. ''length'') пути.}} {{Определение|definition='''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.}} {{Определение|definition ='''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex> называется циклическим путём.

Путь такой'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а так же также <tex> e_i \ne e_{(i\bmod k +1) \mod k}</tex> называется циклическим путём.

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