Изменения

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

'''РебромОриентированным графом''' ориентированного графа называют упорядоченную пару вершин <tex> G</tex> называется четверка <tex>G = (vV, uE, \operatorname{beg}, \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>eG</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> называется тройка <btex>петлейG = (V, E, \operatorname{ends})</btex> , где <tex>V</tex> {{---}} множество вершин, <tex>E</tex> {{---}} множество рёбер, а <tex>\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}</tex>. Мультиграф Это определение, в отличие от предыдущего, позволяет задавать графы с петлями принято называть кратными рёбрами.}} {{Определение|id = def_simple_graph|definition ='''Простым графом''' <tex>G</tex> называется граф, в котором нет петель и кратных рёбер.}} {{Определение|id = def_graph_degree_1|definition ='''Степенью''псевдографом'(англ. ''degree'', ''valency'') вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число рёбер, инцидентных <tex>v_i</tex>.}}Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Если имеется ребро <tex> {{Определение|id = isolated_vertex|definition ='''Изолированной вершиной''' (v, uангл. ''isolated vertex'') \in E </tex>, то иногда говорят, что <tex> u </tex> - <b>родитель</b> <tex> v </tex>. Также вершины <tex> u </tex> и <tex> v </tex> в неориентированном графе называют <b>смежными</b>. Граф с вершину степени <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют <b>тривиальным</b>.}}

Так же еще для ориентированных графов определяют '''полустепень входа вершины'''Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

<tex>deg^-v_i = |\{e~|beg~e = v\}|</tex>.<br><tex>deg^+v_i Представление графов = |\{e~|end~e = v\}|</tex>.<br>

Так как у каждого ребра ровно одно начало === Матрица и ровно один конец выполнено следующее равенство:списки смежности ===

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>\sum\limits_{graph[v][u] = true \in VLeftrightarrow (Gv, u)}deg^-v_i = \sum\limits_{v\in VE</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (Gесли в графе разрешены параллельные рёбра)}deg^+v_i = |E.Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</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 \exists j : \forall i \Rightarrow ne e_{(i \mod bmod k)} = e'_{(i + j) \mod k1}</tex>; где <tex>e</tex> и <tex>e'</tex> - это две последовательности ребер в циклическом пути.

'''Неориентированным графомЦикл''' (англ. ''integral cycle'' ) {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}</tex>; где <tex>Ge</tex> называется пара и <tex>e'</tex>G {{---}} это две последовательности рёбер в циклическом пути.}} {{Определение|definition='''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.}}{{Определение|definition='''Рёберно-простой путь''' {{---}} путь, в котором каждое из рёбер графа встречается не более одного раза.}} == Часто используемые графы =={{Определение|id = defFullGraph|definition='''Полный граф''' (Vангл. ''complete graph'', E''clique''){{---}} граф, в котором каждая пара различных вершин смежна. Полный граф с <tex>n</tex> вершинами имеет <tex>n(n-1)/2</tex>, где рёбер и обозначается <tex>VK_n</tex> .}} {{Определение|id = defBiparateGraph|definition=<span id="Двудольный_граф">'''Двудольный граф'''</span> или '''биграф''' (англ. ''bipartite graph'') {{- конечное --}} граф, множество вершинкоторого можно разбить на две части таким образом, а что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с <tex> E \subset V \times Vn</tex> вершинами в одной доле и <tex>m</tex> во второй обозначается <tex>K_{n,m}</tex>.}} {{Определение|id = defRegularGraph|definition='''Регулярный граф''' (uv ~ vu \англ. ''regular graph'') {{uu~|~u \in V\---}})граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени <tex>k</tex> называется <tex>k</tex>‑регулярным, или регулярным графом степени <tex>k</tex> - множество рёбер.

{{main|Дерево, эквивалентные определения}}{{Определение|id=defTree|definition='''Неориентированным графомДерево''' <tex>G = (V, E, endsангл. ''tree'')</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{--- некоторые абстрактные множества}} связный ациклический граф. }}

{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}{{Определение|definition=Граф называется '''Ребромэйлеровым''' в неориентированном графе называют неупорядоченную пару вершин <tex> (vангл. ''eulerian graph''), u) \in E </tex>если он содержит эйлеров цикл.}}

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

{{main|Укладка графа на плоскости}}{{Определение|definition=Граф называется '''Степенюпланарным''' вершины <tex>deg~v_i</tex> называют число ребер(англ. ''planar graph''), инцидентных <tex>v_i</tex>если он обладает укладкой на плоскости. '''Плоским''' (англ. Будем считать''plane graph'', что петли добавляют к степени вершины <tex>2</tex>''planar embedding of the graph'') называется граф уже уложенный на плоскости.}}

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