168
правок
Изменения
→Неориентированные графы
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> - конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~ vu \{uu~|~u \in V\})</tex> - множество рёбер. '''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Неорграф.png|thumb|300px|right|Неориентированный граф<br>]]
Иное определение:
{{Определение
|definition =
'''Неориентированным графом''' <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> - некоторые абстрактные множества.
Две вершины называются '''смежными''' если между ними есть ребро.
'''Степеню''' вершины <tex>deg~v_i</tex> в неориентированном называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
{{Определение|definition ='''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.}}
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
