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