Изменения

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

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

'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.

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

 Также для ориентированных графов определяют '''полустепень исхода вершины''' (outdegree) <tex>\operatorname{deg}^+v_i = |\{e~|~\operatorname{beg}~e = v_i\}|</tex> и '''полустепень захода вершины''' (indegree) <tex>\operatorname{deg}^-v_i = |\{e~|~\operatorname{end}~e = v_i\}|</tex>. Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер рёбер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].

'''Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</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 V\}</tex>. Это определениеграф, в отличие от предыдущего, позволяет задавать графы с кратными ребрамикотором нет петель и кратных рёбер.

Две вершины называются {{Определение|id = def_graph_degree_1|definition ='''смежнымиСтепенью''' (adjacent), если между ними есть реброангл. ''degree'Степенью', '' (degree, valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число реберрёбер, инцидентных <tex>v_i</tex>. }}Будем считать, что петли добавляют к степени вершины <tex>2</tex>. 

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</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)</tex>; <tex>, 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 : e_{(i \mod k)} = e'_{(i + j) \mod bmod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер рёбер в циклическом пути.

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

'''РеберноРёберно-простой путь''' {{---}} путь, в котором каждое из ребер рёбер графа встречается не более одного раза.

'''Длина путиПолный граф''' (англ. ''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''), задающую этот путьесли он содержит гамильтонов цикл.

<tex>K_n</tex> {{---}} полный Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф с <tex>n</tex> вершинамиуже уложенный на плоскости.

<tex>K_{n,m}</tex> '''Остовное дерево''' (англ. ''spanning tree'') {{---}} двудольный граф с <tex>n</tex> вершинами ациклический связный подграф данного связного неориентированного графа, в одной доле и <tex>m</tex> во второйкоторый входят все его вершины.

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