Изменения

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

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

{{Определение|id = def_graph_edge_1|definition ='''Ребром''' (англ. ''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 </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>G</tex> называется четверка <tex>G = (V, E, \operatorname{beg}, \operatorname{end})</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества, а <tex>\operatorname{beg}, \operatorname{end} : E \rightarrow V</tex>.}}Иногда граф, построенный таким образом, называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается Данное определение разрешает соединять вершины более чем одним ребром. Такие ребра рёбра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Граф с кратными рёбрами принято называть '''мультиграфом''' (англ. ''multigraph''). Если в мультиграфе присутствуют петли, то такой граф называют '''псевдографом''' (англ. ''pseudograph'').

|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#71c8373771c8>ЗеленымСиним</font> обозначена петля (6, 6)]]

Также для ориентированных графов определяют ==Неориентированные графы=={{Определение|id = def_undirected_graph_1|definition ='''полустепень исхода вершиныНеориентированным графом''' (англ. ''undirected graph'') <tex>G</tex>deg^называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{--v_i -}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.}}{{Определение|id= def_edge_und|definition ='''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{e~|~beg~e = v_iv, u\}|\in E </tex> и .}}[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]Иное определение:{{Определение|id = def_undirected_graph_2|definition ='''полустепень захода вершиныНеориентированным графом''' <tex>deg^+v_i G</tex> называется тройка <tex>G = |(V, E, \operatorname{ends})</tex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество рёбер, а <tex>\operatorname{ends} : E \to \{\{e~|~end~e = v_iu, v\}, u, v \in V\}|</tex>.Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.}}

Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях{{Определение|id = def_simple_graph|лемма о рукопожатиях]]definition ='''Простым графом''' <tex>G</tex> называется граф, связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]]в котором нет петель и кратных рёбер.}}

'''ПутёмИзолированной вершиной''' (маршрутомангл. ''isolated vertex'') в неориентированном графе называется последовательность вида называют вершину степени <tex>v_0 e_1 v_1 ... e_k v_k0</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.

'''Циклическим путёмПутём''' называется путь(маршрутом, англ. ''path'') в котором графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = v_k(v_{i-1}, v_i), k</tex>{{---}} '''длина''' (англ. ''length'') пути.

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

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

'''РебромЦиклическим путём''' в ''неориентированном графе называют неупорядоченную пару вершин '' называется путь, в котором <tex> (vv_0 = v_k</tex>, u) а также <tex> e_i \ne e_{i \in E bmod k + 1}</tex>.

'''Неориентированным графомЦикл''' <tex>G</tex> называется тройка <tex>G = (Vангл. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, Eчто два пути эквивалентны, ends)если </tex> , где <tex>ends \exists j \forall i : E e_{(i \rightarrow V mod k)} = e'_{(i + j) \times Vbmod k}</tex>, а ; где <tex>Ve</tex> и <tex>Ee'</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=== Матрица и списки смежности ===Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл. }}

Граф можно представить в виде [[Матрица смежности графа{{main|Гамильтоновы графы}}{{Определение|матрицы смежности]], где <tex>graph[v][u] definition= true \Leftrightarrow Граф называется '''гамильтоновым''' (vангл. ''hamiltonian graph''), u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра)он содержит гамильтонов цикл.Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.}}

Если граф разрежен (<tex>{{main|EУкладка графа на плоскости}}{{Определение| < |V^2|</tex>definition=Граф называется '''планарным''' (англ. ''planar graph''), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: если он обладает укладкой на плоскости. '''Плоским''' (vангл. ''plane graph'', u''planar embedding of the graph'') \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулейназывается граф уже уложенный на плоскости.}}

=== Матрица инцидентности ==={{main|Лемма о безопасном ребре}}{{ОпределениеИмеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:definition=# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin '''Остовное дерево''' (e_jангл. ''spanning tree'') \wedge u = end (e_j)</tex>, в случае ориентированного {{---}} ациклический связный подграф данного связного неориентированного графа.# <tex>graph[v][j] = 1 \Leftrightarrow v</tex> инцидентна ребру <tex>e_j</tex>, в случае неориентированного графакоторый входят все его вершины.# Во всех остальных случаях ячейки матрицы равны 0.}}

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