Семь мостов Кёнигсберга
В XVIII веке город Кёнигсберг (ныне Калининград) располагался на обоих берегах реки Прегель и включал два острова, соединенных семью мостами. Задача звучала просто: можно ли пройти по всем мостам, пересекая каждый ровно один раз?
Леонард Эйлер решил эту задачу в 1736 году, доказав, что такого пути не существует. Его прорывом стало понимание того, что физические расстояния и формы мостов не важны; важна только связность (топология). Он представил участки суши как вершины (nodes), а мосты как ребра (edges).
Ключевые концепции
- Вершина (Vertex): Фундаментальная единица графа.
- Ребро (Edge): Связь между двумя вершинами.
- Степень вершины: Количество ребер, исходящих из вершины. Эйлер доказал, что для существования Эйлерова пути нечетную степень могут иметь не более двух вершин.
Современные приложения
Сегодня теория графов вездесуща. Поисковые системы используют её для ранжирования страниц (веб — это ориентированный граф). Социальные сети предлагают друзей на основе общих связей. Логистика использует алгоритмы поиска кратчайшего пути (Дейкстры) для GPS-навигации.
