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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{{В разработке}}
 
==Ориентированные графы (directed graph)==
 
==Ориентированные графы (directed graph)==
 
[[Файл: directed_graph.png|thumb|300px|right|Ориентированный граф<br><font color=#ED1C24>Красным</font> выделено ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]
 
[[Файл: directed_graph.png|thumb|300px|right|Ориентированный граф<br><font color=#ED1C24>Красным</font> выделено ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]
Строка 15: Строка 16:
  
 
В ориентированном графе ребро, концы которого совпадают, то есть <tex>e=\{v,v\}</tex>, называется <b>петлей</b>.
 
В ориентированном графе ребро, концы которого совпадают, то есть <tex>e=\{v,v\}</tex>, называется <b>петлей</b>.
 +
Если имеется ребро <tex> (v, u) \in E </tex>, то иногда говорят, что <tex> u </tex> - родитель <tex> v </tex>.
  
 
{{Определение
 
{{Определение

Версия 01:18, 25 октября 2011

Эта статья находится в разработке!

Ориентированные графы (directed graph)

Ориентированный граф
Красным выделено ребро (6, 2)
Зеленым обозначена петля (6, 6)
Определение:
Ориентированным графом [math]G[/math] называется пара [math]G = (V, E)[/math], где [math]V[/math] - конечное множество вершин, а [math] E \subset V \times 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] - некоторые абстрактные множества. Иногда граф, построенный таким образом называют мультиграфом.


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


В ориентированном графе ребро, концы которого совпадают, то есть [math]e=\{v,v\}[/math], называется петлей. Если имеется ребро [math] (v, u) \in E [/math], то иногда говорят, что [math] u [/math] - родитель [math] v [/math].


Определение:
Полустепенью входа вершины [math]v_i[/math] называется число рёбер, входящих в эту вершину, и обозначается [math]deg^+v_i[/math].


В неориентированном графе [math](v, u) = (u, v)[/math].

Ребро

Для неориентированного графа

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


Степень вершины

Для неориентированного графа

Определение:
Степенью вершины [math]v_i[/math] называется число рёбер инцидентных [math]v_i[/math], и обозначается [math]deg \; v_i[/math].

Говорят, что ребро [math] e = (u, v) [/math] инцидентно вершине [math]a[/math], если [math]u = a[/math] или [math]v = a[/math].

Для ориентированного графа

Определение:
Полустепенью входа вершины [math]v_i[/math] называется число рёбер, входящих в эту вершину, и обозначается [math]deg^+v_i[/math].


Определение:
Полустепенью выхода вершины [math]v_i[/math] называется число рёбер, выходящих из этой вершины, и обозначается [math]deg^-v_i[/math].


Петля

По умолчанию петли в неориентированном графе запрещены.

Путь

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


Циклический путь

Для ориентированного графа

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


Для неориентированного графа

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


Цикл

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