Основные определения теории графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 21 участника)
Строка 2: Строка 2:
  
 
{{Определение
 
{{Определение
 +
|id = oriented_grath
 
|definition =
 
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (vertices), а <tex> E \subset V \times V </tex> {{---}} множество рёбер (edges, дуг (arcs), линий (lines)).
+
'''Ориентированным графом''' (англ. ''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 =
 
|definition =
'''Конечным графом''' (finite graph) <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
+
'''Конечным графом''' (англ. ''finite graph'') <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = def_graph_edge_1
 
|definition =
 
|definition =
'''Ребром''' (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
+
'''Ребром''' (англ. ''edge'', дугой (англ. ''arc''), линией (англ. ''line'')) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = isomorphic_graphs
 
|definition=
 
|definition=
'''Изоморфные графы''' {{---}} два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.
+
'''Изоморфные графы''' (англ. ''isomorphic graphs'') {{---}} два графа <tex>A</tex> и <tex>B</tex> называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.
 
}}
 
}}
  
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b> (loop).
+
В графе ребро, концы которого совпадают, то есть <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, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' (direct predecessor) <tex> u </tex>.
+
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные''' (adjacent)
+
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>
+
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>.
* Вершина <tex> v </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> p </tex> вершинами и <tex> q </tex> рёбрами называют <tex> (p, q) </tex>-графом.  <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.
  
 
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
 
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Строка 38: Строка 44:
 
|id = def1
 
|id = def1
 
|definition =
 
|definition =
'''Ориентированным графом''' <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>.
+
'''Ориентированным графом''' <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>.  
}}
+
}}  
 
+
Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются '''кратными''' (иначе {{---}} '''параллельные''', англ. ''multi-edge'', ''parallel edge''). Граф с кратными рёбрами принято называть '''мультиграфом''' (англ. ''multigraph''). Если в мультиграфе присутствуют петли, то такой граф называют '''псевдографом''' (англ. ''pseudograph'').
Иногда граф, построенный таким образом, называют '''псевдографом''' (pseudograph). В псевдографе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', multi-edge, parallel edge). Псевдограф без петель принято называть '''мультиграфом'''.
 
 
{|border="0" cellpadding="5" width=30% align=center
 
{|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)]]
 
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Синим</font> обозначена петля (6, 6)]]
Строка 49: Строка 54:
 
|}
 
|}
  
 +
{{Определение
 +
|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>.
 +
}}
  
 
+
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество рёбер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
Также для ориентированных графов определяют '''полустепень исхода вершины''' (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>.
 
 
 
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
 
  
 
==Неориентированные графы==
 
==Неориентированные графы==
 
{{Определение
 
{{Определение
 +
|id = def_undirected_graph_1
 
|definition =
 
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{\{v, u\}: v, u \in V\}</tex> {{---}} множество рёбер.
+
'''Неориентированным графом''' (англ. ''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 =
 
|definition =
 
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
 
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> \{v, u\} \in E </tex>.
Строка 66: Строка 74:
 
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]
 
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]
 
Иное определение:
 
Иное определение:
 
 
{{Определение
 
{{Определение
 
|id = def_undirected_graph_2
 
|id = def_undirected_graph_2
 
|definition =
 
|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 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>. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.
 
}}
 
}}
  
Две вершины называются '''смежными''' (adjacent), если между ними есть ребро.
+
{{Определение
 
+
|id = def_simple_graph
'''Степенью''' (degree, valency) вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
+
|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>.
  
 +
{{Определение
 +
|id = isolated_vertex
 +
|definition =
 +
'''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex>
 +
}}
  
 
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
 
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
Строка 85: Строка 105:
 
=== Матрица и списки смежности ===
 
=== Матрица и списки смежности ===
  
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (adjacency matrix), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
+
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные рёбра).
 
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
 
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
  
Если граф разрежен (sparse graph, <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
+
Если граф '''разрежен''' (англ. ''sparse graph''), <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много рёбер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.
  
 
=== Пути в графах ===
 
=== Пути в графах ===
 
{{Определение
 
{{Определение
 +
|id = path
 
|definition =
 
|definition =
'''Путём''' (маршрутом, 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> {{---}} '''длина''' пути.
+
'''Путём''' (маршрутом,англ. ''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=
 +
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Циклическим путём''' (closed walk) в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.
+
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = def_no_graph_path
 
|definition =
 
|definition =
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
+
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а также <tex> e_i \ne e_{i \bmod k + 1}</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = def_graph_cycle_1
 
|definition =
 
|definition =
'''Цикл''' (integral cycle) {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists  j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</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>e</tex> и <tex>e'</tex> {{---}} это две последовательности рёбер в циклическом пути.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
+
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
+
'''Рёберно-простой путь''' {{---}} путь, в котором каждое из рёбер графа встречается не более одного раза.
 
}}
 
}}
  
 +
== Часто используемые графы ==
 
{{Определение
 
{{Определение
 +
|id = defFullGraph
 
|definition=
 
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
+
'''Полный граф''' (англ. ''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''), если он содержит гамильтонов цикл.
 
}}
 
}}
  
== Часто используемые графы ==
+
{{main|Укладка графа на плоскости}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>K_n</tex> {{---}} полный граф с <tex>n</tex> вершинами.
+
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
 
}}
 
}}
  
 +
{{main|Лемма о безопасном ребре}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>K_{n,m}</tex> {{---}} двудольный граф с <tex>n</tex> вершинами в одной доле и <tex>m</tex> во второй.
+
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
 
}}
 
}}
  
Строка 141: Строка 202:
 
* [[Связь степени матрицы смежности и количества путей]]
 
* [[Связь степени матрицы смежности и количества путей]]
  
==Литература==
+
==Источники информации==
 +
* [[wikipedia:ru:Граф_(математика) | Википедия {{---}} Граф]]
 +
* [[wikipedia:Graph_(mathematics) | Wikipedia {{---}} Graph]]
 +
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
 
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://mathworld.wolfram.com/Graph.html Wolfram Mathworld: Graph]
+
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Текущая версия на 19:28, 4 сентября 2022

Ориентированные графы

Определение:
Ориентированным графом (англ. directed graph) [math]G[/math] называется пара [math]G = (V, E)[/math], где [math]V[/math] — множество вершин (англ. vertices), а [math] E \subset V \times V [/math] — множество рёбер.


Определение:
Конечным графом (англ. finite graph) [math]G[/math] называется граф, в котором множества [math]V[/math] и [math]E[/math] — конечны. Следует заметить, что большинство рассматриваевых нами графов — конечны.


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


Определение:
Изоморфные графы (англ. isomorphic graphs) — два графа [math]A[/math] и [math]B[/math] называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.


В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math], называется петлей (англ. loop).

Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math], называются смежными (англ. adjacent).

Если имеется ребро [math] (v, u) \in E [/math], то говорят:

  • [math] v [/math]предок (англ. direct predecessor) [math] u [/math].
  • [math] u [/math] и [math] v [/math]смежные.
  • Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math].
  • Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math].

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math]-графом. [math] (1, 0) [/math]-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,~v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math]. Поэтому часто используют другое определение.

Определение:
Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname{beg}, \operatorname{end})[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname{beg}, \operatorname{end} : E \rightarrow V[/math].

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Красным выделено кратное ребро (6, 2)
Синим обозначена петля (6, 6)
Мультиграф
Псевдограф


Определение:
Для ориентированных графов определяют полустепень исхода вершины (англ. outdegree) [math]\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|[/math] и полустепень захода вершины (англ. indegree) [math]\operatorname{deg}^-v_i = |\{e \mid \operatorname{end(e)} = v_i\}|[/math].


Стоит отметить, что для ориентированного графа справедлива лемма о рукопожатиях, связывающая количество рёбер с суммой степеней вершин.

Неориентированные графы

Определение:
Неориентированным графом (англ. undirected graph) [math]G[/math] называется пара [math]G = (V, E)[/math], где [math]V[/math] — множество вершин, а [math] E \subset \{\{v, u\}: v, u \in V\}[/math] — множество рёбер.


Определение:
Ребром в неориентированном графе называют неупорядоченную пару вершин [math] \{v, u\} \in E [/math].
Неориентированный граф

Иное определение:

Определение:
Неориентированным графом [math]G[/math] называется тройка [math]G = (V, E, \operatorname{ends})[/math] , где [math]V[/math] — множество вершин, [math]E[/math] — множество рёбер, а [math]\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}[/math]. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.


Определение:
Простым графом [math]G[/math] называется граф, в котором нет петель и кратных рёбер.


Определение:
Степенью (англ. degree, valency) вершины [math]\operatorname{deg} v_i[/math] в неориентированном графе называют число рёбер, инцидентных [math]v_i[/math].

Будем считать, что петли добавляют к степени вершины [math]2[/math].


Определение:
Изолированной вершиной (англ. isolated vertex) в неориентированном графе называют вершину степени [math]0[/math]


Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

Представление графов

Матрица и списки смежности

Граф можно представить в виде матрицы смежности (англ. adjacency matrix), где [math]graph[v][u] = true \Leftrightarrow (v, u) \in E[/math]. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены параллельные рёбра). Для матрицы смежности существует теорема, позволяющая связать степень матрицы и количество путей из вершины [math]v[/math] в вершину [math]u[/math].

Если граф разрежен (англ. sparse graph), [math]|E| \ll |V^2|[/math], то есть, неформально говоря, в нем не очень много рёбер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному, его лучше представить в виде списков смежности, где список для вершины [math]v[/math] будет содержать вершины [math]u: (v, u) \in E[/math]. Данный способ позволит сэкономить память, так как не придется хранить много нулей.

Пути в графах

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


Определение:
Длина пути — количество рёбер, входящих в последовательность, задающую этот путь.


Определение:
Циклическим путём (англ. closed walk) в ориентированном графе называется путь, в котором [math]v_0 = v_k[/math].


Определение:
Циклическим путём в неориентированном графе называется путь, в котором [math]v_0 = v_k[/math], а также [math] e_i \ne e_{i \bmod k + 1}[/math].


Определение:
Цикл (англ. integral cycle) — это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если [math] \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \bmod k}[/math]; где [math]e[/math] и [math]e'[/math] — это две последовательности рёбер в циклическом пути.


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


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


Часто используемые графы

Определение:
Полный граф (англ. complete graph, clique) — граф, в котором каждая пара различных вершин смежна. Полный граф с [math]n[/math] вершинами имеет [math]n(n-1)/2[/math] рёбер и обозначается [math]K_n[/math].


Определение:
Двудольный граф или биграф (англ. bipartite graph) — граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с [math]n[/math] вершинами в одной доле и [math]m[/math] во второй обозначается [math]K_{n,m}[/math].


Определение:
Регулярный граф (англ. regular graph) — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени [math]k[/math] называется [math]k[/math]‑регулярным, или регулярным графом степени [math]k[/math].


Определение:
Дерево (англ. tree) — связный ациклический граф.


Определение:
Граф называется эйлеровым (англ. eulerian graph), если он содержит эйлеров цикл.


Основная статья: Гамильтоновы графы
Определение:
Граф называется гамильтоновым (англ. hamiltonian graph), если он содержит гамильтонов цикл.


Определение:
Граф называется планарным (англ. planar graph), если он обладает укладкой на плоскости. Плоским (англ. plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.


Основная статья: Лемма о безопасном ребре
Определение:
Остовное дерево (англ. spanning tree) — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.


См. также

Источники информации

  • Википедия — Граф
  • Wikipedia — Graph
  • Wolfram Mathworld: Graph
  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)