Основные определения

В любом графе есть двудольный подграф, содержащий не менее половины рёбер графа.

Путём в графе называется последовательность $v_{1} e_{1} v_{2} e_{2} \ldots e_{n-1} v_{n}$, в которой для любого $i$ ребро $e_{i}$ соединяет вершины $v_{i}$ и $v_{i+1}$. Число $n-1$ называется длиной пути. (Рёбра $e_{1}, e_{2}, \ldots , e_{n-1}$ не обязательно попарно различны.)

Циклом в графе называется последовательность $v_{1} e_{1} v_{2} e_{2} \ldots e_{n-1} v_{n} e_{n}$, в которой для любого $i < n$ ребро $e_{i}$ соединяет вершины $v_{i}$ и $v_{i+1}$, а ребро $e_{n}$ соединяет вершины $v_{n}$ и $v_{1}$. Циклы считаются одинаковыми, если они отличаются циклическим сдвигом последовательности. Число $n$ называется длиной цикла.

Несамопересекающимся называется цикл, для которого вершины $v_{1}, v_{2}, \ldots , v_{n}$ попарно различны и рёбра $e_{1}, e_{2}, \ldots , e_{n}$ попарно различны. Стандартный термин (менее удобный для начинающих) — простой цикл.

Если степень каждой из $n$ вершин графа больше $\frac{n}{2}-1$, то граф связен.

Пусть дан ориентированный граф $G$, у которого на каждом ребре $u$ написан вес $f(u)$. (Этот вес можно понимать как работу, которую нужно затратить для того, чтобы пройти по ребру от начала до конца.) Функция $p: V(G) \to \mathbb {R}$ («потенциал»), такая что $f(x,y) = p(x) - p(y)$ для любого ребра $u = (x,y)$, существует тогда и только тогда, когда сумма весов рёбер любого цикла равна нулю (при прохождении ребра по циклу в направлении, противоположном ориентации, вес в сумму берётся со знаком «минус»).