Изменения

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

В графе ребро{{Определение|id = finite_graph|definition ='''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, концы которого совпадают, то есть в котором множества <tex>V</tex> и <tex>E</tex>e{{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.}} {{Определение|id =def_graph_edge_1|definition ='''Ребром''' (vангл. ''edge'', дугой (англ. ''arc''),vлинией (англ. ''line''))ориентированного графа называют упорядоченную пару вершин </tex>(v, называется <b>петлейu) \in E </btex>. Мультиграф с петлями принято называть }} {{Определение|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'') <btex>предокu </btex> .* <tex> u </tex>и <tex> v </tex> {{---}} '''смежные'''. Также вершины * Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u ) </tex> и .* Вершина <tex> v </tex> называют '''инцидентна''' ребру <btex>смежными(v, u) </btex>.  '''Инцидентность''' (англ. ''incidence'') {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны. Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами рёбрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex> - граф называют <b>тривиальным</b>.

'''Ориентированным Неориентированным графом''' (англ. ''undirected graph'') <tex>G</tex> называется четверка пара <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>{{---}} множество вершин, а <tex>E \subset \{\{v, u\}: v, u \in V\}</tex> и <tex>E</tex> {{--- некоторые абстрактные множества}} множество рёбер.

Иногда граф, построенный таким образом называют {{Определение|id=def_edge_und|definition ='''мультиграфомРебром'''. В мультиграфе не допускаются петлив неориентированном графе называют неупорядоченную пару вершин <tex> \{v, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''')u\} \in E </tex>.{|border="0" cellpadding="5" width=30% align=center}}|[[Файл: directed_graphGraph_definition_2.png|thumb|300px210px|center|Неориентированный граф<font colorbr>]]Иное определение:{{Определение|id = def_undirected_graph_2|definition =#ED1C24'''Неориентированным графом''' <tex>КраснымG</fonttex> выделено кратное ребро называется тройка <tex>G = (6V, E, 2\operatorname{ends})<br/tex> , где <tex>V</tex>{{---}} множество вершин, <font color=#22B14Ctex>ЗеленымE</fonttex> обозначена петля (6{{---}} множество рёбер, 6)]]|[[Файла <tex>\operatorname{ends} : MultigraphE \to \{\{u, v\}, u, v \in V\}</tex>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.png}} {{Определение|thumbid = def_simple_graph|300pxdefinition ='''Простым графом''' <tex>G</tex> называется граф, в котором нет петель и кратных рёбер.}} {{Определение|centerid = def_graph_degree_1|аdefinition ='''Степенью''' (англ. ''degree'', ''valency'') Мультиграфвершины <brtex>\operatorname{deg} v_i</tex> в неориентированном графе называют число рёбер, инцидентных <tex>v_i</tex> б) Псевдограф]].|}}Будем считать, что петли добавляют к степени вершины <tex>2</tex>.

Так же для ориентированных графов определяют '''полустепень захода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень исхода вершины''' <tex>deg^+v_i Представление графов = |\{e~|end~e = v\}|</tex>.

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

Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''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 ='''Циклическим путёмДлина пути''' называется путь{{---}} количество [[Основные определения теории графов|рёбер]], входящих в котором <tex>v_0 = v_k</tex>последовательность, задающую этот путь.

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

'''Неориентированным графомЦиклическим путём''' (undirected graph) <tex>G</tex> в ''неориентированном графе'' называется пара путь, в котором <tex>G v_0 = (V, E)</tex>, где <tex>Vv_k</tex> - конечное множество вершин, а также <tex> E \subset V \times V(uv \sim vu~\backslash~e_i \ne e_{uu~|~u \in Vi \bmod k + 1})</tex> - множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </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=Граф называется '''эйлеровым'''Ребро(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]