Как объяснить граф бабушке через карту метро

Что вообще такое граф — простыми словами

Математики называют графом набор точек, часть которых соединена линиями. Точки называют вершинами, линии между ними — рёбрами. Звучит абстрактно, но схема метро — готовый пример прямо перед глазами: круглые значки станций и цветные линии путей между ними изображают ровно то же самое, просто без учёных слов. Если бабушка хоть раз пользовалась картой метро, она уже читала граф, просто не знала термина.

Станции — это вершины графа

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

Перегоны между станциями — это рёбра

Линия пути от одной станции до соседней — это ребро графа. Оно существует только там, где поезд проезжает без остановки на промежуточной станции, поэтому две станции без прямого перегона между ними ребром не соединены — доехать можно, но обязательно через промежуточные вершины. У ребра иногда есть вес, например время в пути или число минут, и тогда граф называют взвешенным. Взвешенный граф удобнее для практических задач: два перегона по числу остановок и по времени в пути совсем не одно и то же, один перегон может занимать минуту, а другой все четыре.

Пересадочные станции и степень вершины

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

Как искать кратчайший путь на карте метро

Кратчайший путь — маршрут с наименьшим числом пересадок или наименьшим временем в пути, в зависимости от того, что считать важнее. Человек ищет его на глаз: смотрит на две точки, прикидывает, через какую пересадку они соединяются быстрее всего, и мысленно перебирает пару вариантов. Компьютер делает практически то же самое, только гораздо быстрее и по всем вариантам сразу — он перебирает возможные цепочки рёбер и выбирает ту, что даёт наименьшую сумму весов. Такую задачу решают специальные алгоритмы поиска кратчайшего пути, и один из самых известных — алгоритм Дейкстры, предложенный ещё в конце 1950-х годов нидерландским учёным Эдсгером Дейкстрой для похожей навигационной задачи. Он же лежит в основе большинства современных навигаторов и планировщиков маршрута в метро.

Где ещё прячутся графы вокруг нас

Как только человек замечает граф в карте метро, он начинает видеть похожую структуру почти везде. Список друзей в соцсети — граф, где вершины — люди, а рёбра — дружеские связи. Схема дорог города — граф, где вершины — перекрёстки, а рёбра — участки улиц между ними. Интернет тоже граф: сайты соединены гиперссылками, и поисковые системы во многом ранжируют страницы по тому, сколько и каких ссылок на них ведёт.

• Список контактов в телефоне, где вершины — люди, а рёбра — записанные номера
• Схема кабелей в квартире, где вершины — розетки и приборы, а рёбра — провода между ними
• Дерево семьи на бумаге, где вершины — родственники, а рёбра — родственные связи
• Меню сайта со ссылками между страницами, где вершины — страницы, а рёбра — гиперссылки