Изменения

'''Ориентированным графом''' (англ. ''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>u,~vV</tex> нельзя соединить более чем одним ребром и <tex>(u, v)E</tex>{{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.Поэтому часто используют немного другое определение. }}

{{Определение|id = def_graph_edge_1|definition ='''Ориентированным графомРебром''' <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> (v, u) \in E 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> u v </tex> {{-- <b>родитель</b> -}} '''предок''' (англ. ''direct predecessor'') <tex> v u </tex>. Также вершины * <tex> u </tex> и <tex> v </tex> называют <b>смежными</b>{{---}} '''смежные'''. Граф с * Вершина <tex> p u </tex> вершинами и '''инцидентна''' ребру <tex> q (v, u) </tex> ребрами называют .* Вершина <tex> (p, q) v </tex> - графом. '''инцидентна''' ребру <tex> (1v, 0u) </tex> - граф называют <b>тривиальным</b>.

Так же еще для ориентированных графов определяют '''полустепень входа вершиныИнцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с <tex>deg^-v_i = |\{e~|beg~e = v\}|p </tex>.вершинами и <tex> q <br/tex>рёбрами называют <tex>deg^+v_i = |\{e~|end~e = v\}|(p, q) </tex>-графом. <tex> (1, 0) </tex>-граф называют <brb>тривиальным</b>.

Так как у каждого ребра ровно одно начало Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.Поэтому часто используют другое определение. {{Определение|id = def1|definition ='''Ориентированным графом''' <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>\sumoperatorname{deg}^+v_i = |\limits_{ve \mid \in Voperatorname{beg(Ge)}= v_i\}|</tex> и '''полустепень захода вершины''' (англ. ''indegree'') <tex>\operatorname{deg}^-v_i = |\{e \summid \limits_operatorname{v\in Vend(Ge)}deg^+= v_i = |E\}|</tex>.}}

'''ПутёмНеориентированным графом''' в графе (англ. ''undirected graph'') <tex>G</tex> называется последовательность вида пара <tex>v_0 e_1 v_1 ... e_k v_kG = (V, E)</tex>, где <tex>e_i = (v_V</tex> {{i-1--}} множество вершин, а <tex> E \subset \{\{v, u\}: v, v_i)u \in V\}</tex>{{---}} множество рёбер.

'''Циклическим путёмРебром''' называется путь, в котором неориентированном графе называют неупорядоченную пару вершин <tex>v_0 = v_k\{v, u\} \in E </tex>.

'''ЦиклНеориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{--- это класс эквивалентности циклических путей на отношении эквивалентности таком}} множество вершин, что два пути эквивалентны<tex>E</tex> {{---}} множество рёбер, если а <tex> \exists j operatorname{ends} : E \forall i to \{\Rightarrow e_{(i u, v\}, u, v \in V\mod k)} </tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.}} {{Определение|id = def_simple_graph|definition = e'_''Простым графом''' <tex>G</tex> называется граф, в котором нет петель и кратных рёбер.}} {{Определение|id = def_graph_degree_1|definition ='''Степенью''' (i + jангл. ''degree'', ''valency'') вершины <tex>\mod koperatorname{deg} v_i</tex> в неориентированном графе называют число рёбер, инцидентных <tex>v_i</tex>.}}Будем считать, что петли добавляют к степени вершины <tex>2</tex>; . {{Определение|id = isolated_vertex|definition ='''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex> }} Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе. == Представление графов == === Матрица и списки смежности === Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>egraph[v][u] = true \Leftrightarrow (v, u) \in E</tex> . Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные рёбра).Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>e. Если граф '''разрежен''' (англ. ''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='''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.

'''Неориентированным графомЦиклическим путём''' (undirected graphангл. ''closed walk'') <tex>G</tex> в ''ориентированном графе'' называется пара путь, в котором <tex>G v_0 = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv ~ vu \{uu~|~u \in V\})v_k</tex> - множество рёбер.

{{Определение|id = def_no_graph_path|definition ='''Циклическим путём'Неориентированным графом''в ' 'неориентированном графе'' называется путь, в котором <tex>G v_0 = (V, E, ends)v_k</tex> , где а также <tex>ends : E e_i \rightarrow V ne e_{i \times V</tex>, а <tex>V</tex> и <tex>Ebmod k + 1}</tex> - некоторые абстрактные множества. }}

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

Две вершины называются {{Определение|definition='''смежнымиПростой (вершинно-простой) путь''' если между ними есть ребро(англ.''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.}}{{Определение|definition='''Рёберно-простой путь''' {{---}} путь, в котором каждое из рёбер графа встречается не более одного раза.}}

== Часто используемые графы =={{Определение|id = defFullGraph|definition='''СтепенюПолный граф''' вершины (англ. ''complete graph'', ''clique'') {{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>deg~v_in</tex> в неориентированном называют число ребер, инцидентных вершинами имеет <tex>v_in(n-1)/2</tex>. Будем считать, что петли добавляют к степени вершины рёбер и обозначается <tex>2K_n</tex>.}}

{{Определение|id = defBiparateGraph|definition=<span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф'''Циклическим путём(англ. ''bipartite graph'' называется путь) {{---}} граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex>n</tex> вершинами в котором одной доле и <tex>v_0 = v_km</tex>, а так же во второй обозначается <tex> e_i \ne e_K_{(i+1) \mod kn,m}</tex>.}}

В определении циклического пути {{ОпределениеОстальные определения в неориентированном графе совпадают |id = defRegularGraph|definition='''Регулярный граф''' (англ. ''regular graph'') {{---}} граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с аналогичными определениями в ориентированном графевершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex>.}}

{{main|Дерево, эквивалентные определения}}{{Определение|id=defTree|definition=Замечание=='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.В разной литературе используются разные термины для определения одного и того же}}

{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}{{Определение|definition=Граф называется '''эйлеровым'''Ребро(edge) - Дуга(arc) - Линия(line)англ. ''eulerian graph''), если он содержит эйлеров цикл. }}

{{main|Гамильтоновы графы}}{{Определение|definition=Граф называется '''гамильтоновым'''Вершина(vertex) - Узел(node) - Точка(point)англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.}}

{{main|Укладка графа на плоскости}}{{Определение|definition=Граф называется '''Путь - Маршрутпланарным'''(англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.}}

etc{{main|Лемма о безопасном ребре}}{{Определение|definition='''Остовное дерево''' (англ.''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.}}

==ЛитератураИсточники информации==* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]