- граф
- Граф — это совокупность вершин (узлов) и рёбер (связей между вершинами). Вершины обозначаются точками, рёбра — линиями, соединяющими вершины.
- неориентированный граф
- Неориентированный граф — это граф, в котором каждое ребро не имеет определённого направления. Вершины соединяются рёбрами без стрелок.
- ориентированный граф
- Ориентированный граф — это граф, в котором каждое ребро имеет определённое направление, обозначаемое стрелкой. Вершины соединяются направленными рёбрами.
- полный граф
- Полное граф — это граф, в котором каждая пара вершин соединена ровно одним ребром. Количество рёбер в полном графе $n$-вершин равно $n(n-1)/2$.
- двудольный граф
- Двудольный граф — это граф, вершины которого можно разделить на две непересекающиеся части так, что каждое ребро соединяет вершину из одной части с вершиной из другой.
- маршрут в графе
- Маршрут в графе — это последовательность рёбер, соединяющих вершины. Маршрут может начинаться и заканчиваться в одной вершине.
- путь в графе
- Путь в графе — это маршрут, в котором все вершины и рёбра различны. Путь не может содержать повторяющихся вершин или рёбер.
- цикл в графе
- Цикл в графе — это путь, начинающийся и заканчивающийся в одной и той же вершине. Цикл может содержать повторяющиеся рёбра, но не вершины.
- простой цикл в графе
- Простой цикл в графе — это цикл, не содержащий повторяющихся рёбер и вершин, кроме начальной и конечной. Простой цикл начинается и заканчивается в одной вершине.
- связный граф
- Связный граф — это граф, в котором любая пара вершин соединена хотя бы одним путём. Граф, не являющийся связным, называется несвязным.
- компонента связности графа
- Компонента связности графа — это максимальное подмножество вершин, в котором любая пара вершин соединена хотя бы одним путём. Несвязный граф состоит из нескольких компонент связности.
- степень вершины графа
- Степень вершины графа — это количество рёбер, инцидентных данной вершине. Степень вершины обозначается $\deg(v)$. Сумма степеней всех вершин графа равна удвоенному числу рёбер.
- эйлеров граф
- Эйлеров граф — это граф, в котором существует цикл, проходящий через каждое ребро ровно один раз. Эйлеров цикл должен начинаться и заканчиваться в одной вершине.
- хроматическое число графа
- Хроматическое число графа — это минимальное количество цветов, необходимых для раскраски вершин графа так, чтобы смежные вершины имели разные цвета. Хроматическое число обозначается $\chi(G)$.