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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ориентированные графы)
(Ориентированные графы)
Строка 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> - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер. '''Ребром''' ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
 
}}
 
}}
  
Заметим, что по такому определению любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
+
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.
 +
 
 +
Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> v </tex> - <b>предок</b> <tex> u </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>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
 
Поэтому часто используют другое определение.  
 
Поэтому часто используют другое определение.  
  
Строка 13: Строка 17:
 
'''Ориентированным графом''' <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, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
 
}}
 
}}
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли (см. определение ниже), но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').
+
Иногда граф, построенный таким образом называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе - '''параллельные''').
 
{|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)]]
 
|[[Файл: directed_graph.png|thumb|300px|center|<font color=#ED1C24>Красным</font> выделено кратное ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]
 
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф<br> б) Псевдограф]]
 
|[[Файл: Multigraph.png|thumb|300px|center|а) Мультиграф<br> б) Псевдограф]]
 
|}
 
|}
{{Определение
 
|definition =
 
'''Ребром''' ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
 
}}
 
  
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.
 
 
 
Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> v </tex> - <b>предок</b> <tex> u </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~|beg~e = v\}|</tex> и '''полустепень исхода вершины''' <tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.
<tex>deg^+v_i = |\{e~|end~e = v\}|</tex>.<br>
 
  
 
Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:
 
Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:
Строка 40: Строка 34:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Путём''' в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>,  где <tex>e_i = (v_{i-1}, v_i)</tex>.
+
'''Путём''' в графе называется последовательность вида <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>.
 
}}
 
}}
 
{{Определение
 
{{Определение

Версия 02:46, 27 октября 2011

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

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


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

Если имеется ребро [math] (v, u) \in E [/math], то иногда говорят, что [math] v [/math] - предок [math] u [/math]. Также вершины [math] u [/math] и [math] v [/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, beg, end)[/math] , где [math]beg, end : E \rightarrow V [/math], а [math]V[/math] и [math]E[/math] - некоторые абстрактные множества.

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

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


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

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

[math]\sum\limits_{v\in V(G)}deg^-v_i = \sum\limits_{v\in V(G)}deg^+v_i = |E|[/math].


Определение:
Путём в графе называется последовательность вида [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]v_0 = v_k[/math].


Определение:
Цикл - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если [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 \times V(uv ~ vu \{uu~|~u \in V\})[/math] - множество рёбер.
Неориентированный граф

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

Неориентированным графом [math]G = (V, E, ends)[/math] , где [math]ends : E \rightarrow V \times V[/math], а [math]V[/math] и [math]E[/math] - некоторые абстрактные множества.

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

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

Степеню вершины [math]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].

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

Замечание

В разной литературе используются разные термины для определения одного и того же

Ребро(edge) - Дуга(arc) - Линия(line)

Вершина(vertex) - Узел(node) - Точка(point)

Путь - Маршрут

etc..

См. также

Литература

  • Харари Фрэнк Теория графов = 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 (рус.)