Изменения

==Ориентированные графы== {{В разработке}}Определение|id =oriented_grath|definition =Ориентированные графы '''Ориентированным графом''' (англ. ''directed graph'')<tex>G</tex> называется пара <tex>G ==[[Файл: directed_graph(V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ.png|thumb|300px|right|Ориентированный граф''vertices''), а <brtex>E \subset V \times V <font color/tex> {{---}} множество рёбер.}} {{Определение|id = finite_graph|definition =#ED1C24'''Конечным графом''' (англ. ''finite graph'') <tex>КраснымG</fonttex> выделено ребро (6называется граф, 2)в котором множества <tex>V<br/tex>и <font color=#22B14Ctex>ЗеленымE</fonttex> обозначена петля (6{{---}} конечны. Следует заметить, 6)]]что большинство рассматриваевых нами графов {{---}} конечны.}} 

Ориентированным графом '''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex>G(v, u) \in E </tex> называется пара <tex>G .}} {{Определение|id = isomorphic_graphs|definition= '''Изоморфные графы''' (V, Eангл. ''isomorphic graphs'')</tex>, где {{---}} два графа <tex>VA</tex> - конечное множество вершин, а и <tex> E \subset V \times V B</tex> - множество рёберназываются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.

Ребром '''Ориентированным графом''' <tex>G</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> и '''полустепень захода вершины''' (v, uангл. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e) } = v_i\in E }|</tex>.

В ориентированном графе реброСтоит отметить, концы которого совпадают, то есть <tex>e=\{v,v\}</tex>что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], называется <b>петлей</b>.Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> u </tex> - родитель <tex> v </tex>связывающая количество рёбер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

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

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

Степенью вершины '''Простым графом''' <tex>v_iG</tex> называется число рёбер инцидентных <tex>v_i</tex>граф, в котором нет петель и обозначается <tex>deg \; v_i</tex>кратных рёбер.

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

Полустепенью выхода вершины '''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>v_i0</tex> называется число рёбер, выходящих из этой вершины, и обозначается <tex>deg^-v_i</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>. Данный способ позволит сэкономить память, так как не придется хранить много нулей. === Пути в графах ===

'''Путём ''' (маршрутом,англ. ''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='''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.

'''Циклическим путём ''' (англ. ''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> {{- --}} это две последовательности ребер рёбер в циклическом пути.