Изменения

{{В разработке}}==Ориентированные графы (directed graph)==[[Файл: directed_graph.png|thumb|300px|right|Ориентированный граф<br><font color=#ED1C24>Красным</font> выделено ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]

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

Есть еще более другое определение.{{Определение|id = finite_graph|definition =Ориентированным '''Конечным графом ''' (англ. ''finite graph'') <tex>G</tex> называется четверка <tex>G = (Vграф, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а в котором множества <tex>V</tex> и <tex>E</tex> {{-- некоторые абстрактные множества-}} конечны. Иногда графСледует заметить, построенный таким образом называют мультиграфомчто большинство рассматриваевых нами графов {{---}} конечны.}}

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

В ориентированном графе ребро, концы которого совпадают, то есть <tex>e=\{(v,v\})</tex>, называется <b>петлей</b>(англ.Если имеется ребро <tex> (v, u''loop'') \in E </tex>, то иногда говорят, что <tex> u </tex> - родитель <tex> v </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>.

В неориентированном графе <tex>(vСтоит отметить, u) = (uчто для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], v)</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> {{---}} множество рёбер.}}{{Определение|id=Для неориентированного графа===def_edge_und|definition ='''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.}}[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]Иное определение:

Ребром называют неупорядоченную пару '''Неориентированным графом''' <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> {{- --}} это две последовательности ребер рёбер в циклическом пути.