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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Ориентированные графы)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер.
+
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин (vertices), а <tex> E \subset V \times V </tex> {{---}} множество рёбер (edges, дуг (arcs), линий (lines)).
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
'''Конечным графом''' (finite graph) <tex>G</tex> называется граф, в котором множества <tex>V</tex> и <tex>E</tex> {{---}} конечны. Следует заметить, что большинство рассматриваевых нами графов {{---}} конечны.
 
}}
 
}}
  
Строка 11: Строка 16:
 
}}
 
}}
  
−
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.
+
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b> (loop).
  
 
Если имеется ребро <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> {{---}} '''смежные''' (adjacent)
 
* Вершина <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>
Строка 28: Строка 33:
 
|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>\operatorname{beg}, \operatorname{end} : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества.
 
}}
 
}}
−
Иногда граф, построенный таким образом, называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').
+
Иногда граф, построенный таким образом, называют '''мультиграфом''' (multigraph). В мультиграфе допускается соединять вершины более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''', multi-edge, parallel edge). Мультиграф с петлями принято называть '''псевдографом''' ([http://mathworld.wolfram.com/Pseudograph.html pseudograph]).
 
{|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)]]
Строка 40: Строка 45:
  
  
−
Также для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|~beg~e = v_i\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|~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>.
  
 
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
 
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
Строка 47: Строка 52:
 
{{Определение
 
{{Определение
 
|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)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.
+
'''Циклическим путём''' (closed walk) называется путь, в котором <tex>v_0 = v_k</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
'''Цикл''' {{---}} это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists  j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
+
'''Цикл''' (integral cycle) {{---}} это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists  j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
 
}}
 
}}
  
Строка 61: Строка 66:
 
{{Определение
 
{{Определение
 
|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> {{---}} множество рёбер.
+
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} множество вершин, а <tex> E \subset \{v_1, v_2 \in V\})</tex> {{---}} множество рёбер.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 72: Строка 77:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.
+
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, \operatorname{ends})</tex> , где <tex>\operatorname{ends} : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые множества, причем <tex>\forall v_1, v_2 \in E: \operatorname{ends}(v_1, v_2) \implies \operatorname{ends}(v_2, v_1)</tex>
 
}}
 
}}
  
−
Две вершины называются '''смежными''', если между ними есть ребро.
+
Две вершины называются '''смежными''' (adjacent), если между ними есть ребро.
  
−
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
+
'''Степенью''' (degree, valency) вершины <tex>\operatorname{deg}~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
  
 
{{Определение
 
{{Определение
Строка 90: Строка 95:
 
=== Матрица и списки смежности ===
 
=== Матрица и списки смежности ===
  
−
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <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>.
  
−
Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
+
Если граф разрежен (sparse graph, <tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
  
 
=== Матрица инцидентности ===
 
=== Матрица инцидентности ===

Версия 02:25, 23 октября 2013

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

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


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


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


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

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

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

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

Граф с [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]\operatorname{beg}, \operatorname{end} : E \rightarrow V [/math], а [math]V[/math] и [math]E[/math] — некоторые множества.

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

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


Также для ориентированных графов определяют полустепень исхода вершины (outdegree) [math]\operatorname{deg}^+v_i = |\{e~|~\operatorname{beg}~e = v_i\}|[/math] и полустепень захода вершины (indegree) [math]\operatorname{deg}^-v_i = |\{e~|~\operatorname{end}~e = v_i\}|[/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)[/math]; [math]k[/math] — длина пути.


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


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


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

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


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

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


Определение:
Неориентированным графом [math]G[/math] называется тройка [math]G = (V, E, \operatorname{ends})[/math] , где [math]\operatorname{ends} : E \rightarrow V \times V[/math], а [math]V[/math] и [math]E[/math] — некоторые множества, причем [math]\forall v_1, v_2 \in E: \operatorname{ends}(v_1, v_2) \implies \operatorname{ends}(v_2, v_1)[/math]


Две вершины называются смежными (adjacent), если между ними есть ребро.

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


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


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

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

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

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

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

Матрица инцидентности

Имеет место и другое представление графа - матрица инцидентности, которая сопоставляет множество вершин множеству ребер. То есть:

  1. [math]graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)[/math], в случае ориентированного графа.
  2. [math]graph[v][j] = 1 \Leftrightarrow v[/math] инцидентна ребру [math]e_j[/math], в случае неориентированного графа.
  3. Во всех остальных случаях ячейки матрицы равны 0.

См. также

Литература

  • Харари Фрэнк Теория графов = 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 (рус.)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Основные_определения_теории_графов&oldid=33201»