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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 71 промежуточная версия 28 участников)
Строка 2: Строка 2:
  
 
{{Определение
 
{{Определение
 +
|id = oriented_grath
 
|definition =
 
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер. '''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
+
'''Ориентированным графом''' (англ. ''directed graph'') <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (англ. ''vertices''), а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
 
}}
 
}}
  
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.
+
{{Определение
 +
|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, u) \in E </tex>, то говорят:
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
+
* <tex> v </tex> {{---}} '''предок''' (англ. ''direct predecessor'') <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
+
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''.
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>, вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </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> 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>.
 
Поэтому часто используют другое определение.  
 
Поэтому часто используют другое определение.  
 
 
{{Определение
 
{{Определение
 
|id = def1
 
|id = def1
 
|definition =
 
|definition =
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</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'').
 
{|border="0" cellpadding="5" width=30% align=center
 
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|<font color=#ED1C24>Красным</font> выделено кратное ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]
+
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Синим</font> обозначена петля (6, 6)]]
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф<br> б) Псевдограф]]
+
|[[Файл: 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>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 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>.
 +
 +
{{Определение
 +
|id = isolated_vertex
 +
|definition =
 +
'''Изолированной вершиной''' (англ. ''isolated vertex'') в неориентированном графе называют вершину степени <tex>0</tex>
 +
}}
  
 +
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
  
Так же для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|beg~e = v\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.
+
== Представление графов ==
  
Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:
+
=== Матрица и списки смежности ===
  
<tex>\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|</tex>.
+
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]] (англ. ''adjacency matrix''), где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</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>. Данный способ позволит сэкономить память, так как не придется хранить много нулей.
  
 +
=== Пути в графах ===
 
{{Определение
 
{{Определение
 +
|id = path
 
|definition =
 
|definition =
'''Путём'''(маршрутом) в графе называется последовательность вида <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 =
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
+
'''Циклическим путём''' (англ. ''closed walk'') в ''ориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>.
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 +
|id = def_no_graph_path
 
|definition =
 
|definition =
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists  j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
+
'''Циклическим путём''' в ''неориентированном графе'' называется путь, в котором <tex>v_0 = v_k</tex>, а также <tex> e_i \ne e_{i \bmod k + 1}</tex>.
 
}}
 
}}
  
==Неориентированные графы==
 
 
{{Определение
 
{{Определение
 +
|id = def_graph_cycle_1
 
|definition =
 
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex> {{---}} множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in 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=
 +
'''Простой (вершинно-простой) путь''' (англ. ''simple path'') {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
 +
}}
 +
{{Определение
 +
|definition=
 +
'''Рёберно-простой путь''' {{---}} путь, в котором каждое из рёбер графа встречается не более одного раза.
 +
}}
 +
 
 +
== Часто используемые графы ==
 +
{{Определение
 +
|id = defFullGraph
 +
|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>.
 
}}
 
}}
[[Файл: Неорграф.png|thumb|300px|center|Неориентированный граф<br>]]
 
Иное определение:
 
  
 +
{{main|Дерево, эквивалентные определения}}
 
{{Определение
 
{{Определение
|definition =
+
|id=defTree
'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.  
+
|definition='''Дерево''' (англ. ''tree'') {{---}} связный ациклический граф.
 
}}
 
}}
  
Две вершины называются '''смежными''' если между ними есть ребро.
+
{{main|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов}}
 +
{{Определение
 +
|definition=
 +
Граф называется '''эйлеровым''' (англ. ''eulerian graph''), если он содержит эйлеров цикл.  
 +
}}
  
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
+
{{main|Гамильтоновы графы}}
 +
{{Определение
 +
|definition=
 +
Граф называется '''гамильтоновым''' (англ. ''hamiltonian graph''), если он содержит гамильтонов цикл.
 +
}}
  
 +
{{main|Укладка графа на плоскости}}
 
{{Определение
 
{{Определение
|definition =
+
|definition=
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.
+
Граф называется '''планарным''' (англ. ''planar graph''), если он обладает укладкой на плоскости. '''Плоским''' (англ. ''plane graph'', ''planar embedding of the graph'') называется граф уже уложенный на плоскости.
 
}}
 
}}
  
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
+
{{main|Лемма о безопасном ребре}}
 +
{{Определение
 +
|definition=
 +
'''Остовное дерево''' (англ. ''spanning tree'') {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
 +
}}
  
 
==См. также==
 
==См. также==
 
* [[Лемма о рукопожатиях]]
 
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
 
 
* [[Матрица смежности графа]]
 
* [[Матрица смежности графа]]
 
* [[Связь степени матрицы смежности и количества путей]]
 
* [[Связь степени матрицы смежности и количества путей]]
  
==Литература==
+
==Источники информации==
 +
* [[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

Текущая версия на 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 (рус.)