Неориентированный граф — это пара (V, E), где V — множество вершин (узлов), а E — множество рёбер. Каждое ребро представляет собой неупорядоченную пару \{u, v\} вершин u, v \in V.
Основные свойства:
- Ребра без направления: Связь между вершинами симметрична. Если есть ребро между
u и v, это означает, что можно перемещаться как из u в v, так и из v в u.
- Степень вершины: Количество рёбер, инцидентных данной вершине. Обозначается как
deg(v).
- Сумма степеней вершин: В любом неориентированном графе сумма степеней всех вершин равна удвоенному количеству рёбер.
\sum_{v \in V} deg(v) = 2|E|.
- Путь: Последовательность вершин
v_0, v_1, ..., v_k, где каждая пара (v_i, v_{i+1}) является ребром.
- Цикл: Путь, который начинается и заканчивается в одной и той же вершине, при этом все остальные вершины уникальны.
- Связность: Граф называется связным, если существует путь между любой парой вершин. Несвязный граф состоит из нескольких связных компонент.
- Взвешенный граф: Каждому ребру может быть присвоено некоторое числовое значение (вес).
- Отсутствие петель и кратных рёбер (простой граф): В простых неориентированных графах между двумя вершинами может быть не более одного ребра, и рёбра не соединяют вершину саму с собой (нет петель).
- Полный граф: Граф, в котором каждая пара различных вершин соединена ребром. Обозначается
K_n, где n — количество вершин.
- Двудольный граф: Множество вершин можно разбить на два непересекающихся подмножества
U и W, такие что каждое ребро соединяет вершину из U с вершиной из W.