Теория графов Эйлера

В 1736 году Леонард Эйлер рассмотрел знаменитую задачу о семи мостах Кёнигсберга (ныне Калининград). Город был разделён рекой Прегель на четыре части (два берега и два острова), соединённых семью мостами. Задача заключалась в том, чтобы пройти по всем мостам ровно по одному разу и вернуться в исходную точку.

Эйлер абстрагировался от географии и представил задачу в виде графа:

- Части города — вершины графа
- Мосты — рёбра графа

Эйлер доказал:

- Обойти все рёбра графа по одному разу и вернуться в исходную вершину (эйлеров цикл) можно только если из каждой вершины выходит чётное число рёбер, и граф связный.
- Если допустить, что не обязательно возвращаться в исходную точку, то можно иметь ровно две вершины с нечётным числом рёбер: путь начнётся в одной и закончится в другой.

В случае Кёнигсберга все четыре вершины имели нечётное число рёбер, поэтому задача не имела решения. Этот подход стал основой теории графов и дал старт целому направлению в математике.

Кратко:

- Эйлеров цикл: все вершины чётные, путь начинается и заканчивается в одной точке.
- Эйлеров путь: ровно две вершины нечётные, путь начинается в одной, заканчивается в другой.

Этот принцип применяется сегодня в логистике, проектировании сетей, биоинформатике и многих других областях.