Изменения

'''Ориентированным графом''' (англ. ''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>V</tex> и <tex>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, 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>.

{{Определение|definition=Для ориентированных графов определяют '''полустепень исхода вершины'''(англ. 'Ориентированным графом'outdegree'' ) <tex>G</tex> называется четверка <tex>G \operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(V, E, beg, ende)</tex> , где <tex>beg, end : E } = v_i\rightarrow V </tex>, а <tex>V}|</tex> и <tex>E</tex> - некоторые абстрактные множества. Иногда граф, построенный таким образом называют '''мультиграфомполустепень захода вершины'''. В мультиграфе не допускаются петли (смангл. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными'indegree'' ) <tex>\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(иначе - '''параллельные'''e)} = v_i\}|</tex>.}}

Стоит отметить, что для ориентированного графа справедлива [[Файл: directed_graph.pngЛемма о рукопожатиях|thumb|300px|center|Ориентированный граф<br><font color=#ED1C24>Красным</font> выделено ребро (6лемма о рукопожатиях]], 2)<br><font color=связывающая количество рёбер с суммой [[Основные определения теории графов#22B14C>Зеленым</font> обозначена петля (6, 6)Степень вершины|степеней вершин]].

'''Неориентированным графом''' (англ. ''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>]]Иное определение:{{Определение|id = def_undirected_graph_2|definition ='''Неориентированным графом''' <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>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.

В графе ребро, концы которого совпадают, то есть {{Определение|id = def_simple_graph|definition ='''Простым графом''' <tex>e=(v,v)G</tex>называется граф, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''в котором нет петель и кратных рёбер.[[Файл: Multigraph.png|thumb|300px|right|а) Мультиграф<br> б) Псевдограф]]}}

Если имеется ребро <tex> {{Определение|id = def_graph_degree_1|definition ='''Степенью''' (vангл. ''degree'', u''valency'') \in E </tex>, то иногда говорят, что <tex> v </tex> - <b>предок</b> <tex> u </tex>. Также вершины <tex> u \operatorname{deg} v_i</tex> и в неориентированном графе называют число рёбер, инцидентных <tex> v v_i</tex> называют <b>смежными</b>. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p}}Будем считать, q) что петли добавляют к степени вершины </tex> - графом. <tex> (1, 0) 2</tex> - граф называют <b>тривиальным</b>.

Так же для ориентированных графов определяют {{Определение|id = isolated_vertex|definition ='''полустепень входа вершиныИзолированной вершиной'''(англ.''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex> }}

<tex>deg^-v_i = |\{e~|beg~e = v\}|</tex>Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.<br><tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.<br>

<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |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'') пути.

'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.

'''ЦиклЦиклическим путём''' - это класс эквивалентности циклических путей на отношении эквивалентности такомв ''неориентированном графе'' называется путь, что два пути эквивалентныв котором <tex>v_0 = v_k</tex>, если а также <tex> e_i \exists j : \forall i \Rightarrow ne e_{(i \mod bmod k)} = e'_{(i + j) \mod k1}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.

'''Неориентированным графомЦикл''' (undirected graphангл. ''integral cycle'') {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex>G</tex> называется пара <tex>G \exists j \forall i : e_{(i \mod k)} = e'_{(V, Ei + j)\bmod k}</tex>, ; где <tex>Ve</tex> - конечное множество вершин, а и <tex> E \subset V \times V(uv ~ vu \{uu~|~u \in V\})e'</tex> {{--- множество }} это две последовательности рёберв циклическом пути.

{{Определение|definition='''Неориентированным графомПростой (вершинно-простой) путь''' <tex>G = (V, E, endsангл. ''simple path'')</tex> {{---}} путь, где <tex>ends : E \rightarrow V \times V</tex>в котором каждая из вершин графа встречается не более одного раза.}}{{Определение|definition='''Рёберно-простой путь''' {{---}} путь, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множествав котором каждое из рёбер графа встречается не более одного раза. }}

== Часто используемые графы =={{Определение|id = defFullGraph|definition='''РебромПолный граф''' (англ. ''complete graph'', ''clique'') {{---}} граф, в неориентированном графе называют неупорядоченную пару котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex> n(v, un-1) \in E /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>deg~v_ik</tex> в неориентированном называют число ребер, инцидентных называется <tex>v_ik</tex>. Будем считать‑регулярным, что петли добавляют к или регулярным графом степени вершины <tex>2k</tex>.}}

{{main|Дерево, эквивалентные определения}}{{Определение|id=defTree|definition='''Циклическим путёмДерево''' называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1англ. ''tree'') \mod k{{---}</tex>} связный ациклический граф.}}

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

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

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

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

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