Изменения

==ГрафОриентированные графы== {{Определение|id = oriented_grath|definition ='''Ориентированным графом''' (англ. ''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> называется пара граф, в котором множества <tex>G = (V, E)</tex>, где и <tex>VE</tex> {{- конечное множество вершин--}} конечны. Следует заметить, а <tex> E \subset V \times V </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> (англ. ''loop''). Два ребра, имеющие общую концевую вершину, то есть <tex>e_1=(v, u_1)</tex> и <tex>e_2==Для (v, u_2)</tex>, называются '''смежными''' (англ. ''adjacent'').  Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>. '''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны. Граф с <tex> p </tex> вершинами и <tex> q </tex> рёбрами называют <tex> (p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>. Заметим, что по определению ориентированного графа====, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.Поэтому часто используют другое определение.

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

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

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

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

Петлёй '''Изолированной вершиной''' (англ. ''isolated vertex'') в ориентированном неориентированном графе называется ребро, концы которого совпадают, то есть называют вершину степени <tex>e=\{v,v\}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>. Данный способ позволит сэкономить память, так как не придется хранить много нулей. === Пути в графах ===

'''Путём ''' (маршрутом,англ. ''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> {{- --}} это две последовательности ребер рёбер в циклическом пути.}} {{Определение|definition='''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.}}{{Определение|definition='''Рёберно-простой путь''' {{---}} путь, в котором каждое из рёбер графа встречается не более одного раза.}} == Часто используемые графы =={{Определение|id = defFullGraph|definition='''Полный граф''' (англ. ''complete graph'', ''clique'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex> рёбер и обозначается <tex>K_n</tex>.}} {{Определение|id = defBiparateGraph|definition=<span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.}} {{Определение|id = defRegularGraph|definition='''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.}} {{main|Дерево, эквивалентные определения}}{{Определение|id=defTree|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.}} {{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}{{Определение|definition=Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл. }} {{main|Гамильтоновы графы}}{{Определение|definition=Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.}} {{main|Укладка графа на плоскости}}{{Определение|definition=Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.}} {{main|Лемма о безопасном ребре}}{{Определение|definition='''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.