4
правки
Изменения
Новая страница: «==Граф== {{Определение |definition = Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечно…»
==Граф==
{{Определение
|definition =
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
}}
В ориентированном графе (v, u) = (u, v).
==Ребро==
====Для неориентированного графа====
{{Определение
|definition =
Ребром называют неупорядоченную пару вершин <math> (v, u) \in E </math>.
}}
====Для ориентированного графа====
{{Определение
|definition =
Ребром называют упорядоченную пару вершин <math> (v, u) \in E </math>.
}}
==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины v<sub>i</sub> называется число рёбер инцидентных v<sub>i</sub>, и обозначается deg v<sub>i</sub>
}}
====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины v<sub>i</sub> называется число рёбер, входящих в эту вершину, и обозначается deg<sup>+</sup> v<sub>i</sub>.
}}
{{Определение
|definition =
Полустепенью выхода вершины v<sub>i</sub> называется число рёбер, выходящих из этой вершину, и обозначается deg<sup>-</sup> v<sub>i</sub>.
}}
==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <math>e=\{v,v\}</math>.
}}
В неориентированном графе петли запрещены.
==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида v<sub>0</sub> e<sub>1</sub> v<sub>1</sub> ... e<sub>k</sub> v<sub>k</sub>; где e<sub>i</sub> = (v<sub>i-1</sub>; v<sub>i</sub>).
}}
==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь, начало и конец которого совпадают, тоесть v<sub>0</sub> = v<sub>k</sub>
}}
====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v<sub>0</sub> = v<sub>k</sub>
}}
{{Определение
|definition =
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер.
}}
В ориентированном графе (v, u) = (u, v).
==Ребро==
====Для неориентированного графа====
{{Определение
|definition =
Ребром называют неупорядоченную пару вершин <math> (v, u) \in E </math>.
}}
====Для ориентированного графа====
{{Определение
|definition =
Ребром называют упорядоченную пару вершин <math> (v, u) \in E </math>.
}}
==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины v<sub>i</sub> называется число рёбер инцидентных v<sub>i</sub>, и обозначается deg v<sub>i</sub>
}}
====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины v<sub>i</sub> называется число рёбер, входящих в эту вершину, и обозначается deg<sup>+</sup> v<sub>i</sub>.
}}
{{Определение
|definition =
Полустепенью выхода вершины v<sub>i</sub> называется число рёбер, выходящих из этой вершину, и обозначается deg<sup>-</sup> v<sub>i</sub>.
}}
==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <math>e=\{v,v\}</math>.
}}
В неориентированном графе петли запрещены.
==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида v<sub>0</sub> e<sub>1</sub> v<sub>1</sub> ... e<sub>k</sub> v<sub>k</sub>; где e<sub>i</sub> = (v<sub>i-1</sub>; v<sub>i</sub>).
}}
==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь, начало и конец которого совпадают, тоесть v<sub>0</sub> = v<sub>k</sub>
}}
====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v<sub>0</sub> = v<sub>k</sub>
}}
