Теория графов: мосты, циклы и эйлеровы пути
Графы — это мощный инструмент моделирования связей между объектами. Олимпиадные задачи на графы часто маскируются под задачи о городах и дорогах, знакомых людях или рукопожатиях.
Основные понятия, которые нужно знать: вершина, ребро, степень вершины, связность. Лемма о рукопожатиях гласит, что сумма степеней всех вершин графа равна удвоенному количеству ребер. Из этого следует важный вывод: количество вершин с нечетной степенью всегда четно.
Задача о Кенигсбергских мостах положила начало теории графов. Эйлер доказал, что пройти по всем мостам по одному разу и вернуться в начало можно только тогда, когда степени всех вершин четны (эйлеров цикл). Если есть ровно две вершины нечетной степени, существует эйлеров путь, но вернуться в начало нельзя.
Также в олимпиадах популярны задачи на деревья (графы без циклов), двудольные графы и планарность (возможность нарисовать граф на плоскости без пересечения ребер). Теорема Эйлера для планарных графов: V - E + F = 2 (Вершины - Ребра + Грани = 2).
