Что вы знаете о графах?

Не о тех, которые вельможи, а о тех, которые фигуры из вершин и рёбер.

Наверное, самый часто встречаемый в быту граф – это карта движения общественного транспорта. Например, карта метро (рис 1). С ее помощью можно легко построить маршрут от одной вершины (станции) до другой. И чем больше кольцевых линий, дополнительных диаметров, пересадочных станций – тем больше вариантов маршрута можно найти.

Очевидно, что чтобы добраться от станции А до станции Б нам нужно, чтобы они были связаны между собой ребрами (перегонами) – непосредственно или через другие вершины. Доехать от Невского проспекта до Охотного ряда на метро пока, к сожалению, не получается. Граф, в котором можно найти путь от любой вершины к любой другой называется «связным».

Но как мы выбираем маршрут, по которому поедем?

Одна из задач теории графов – это поиск кратчайшего, или оптимального, пути.

Что лучше: проехать 7 остановок, сделать пересадку, проехать одну, сделать еще одну пересадку, и проехать еще 5? Или проехать 9, сделать одну пересадку и проехать еще 7?

Под словом «кратчайший» можно понимать разные характеристики в зависимости от условий конкретной задачи. Маршрут, оптимальный для одного пассажира, может оказаться неприемлемым для другого.

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

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

А в случае со станциями ситуация чуть сложнее. Кроме непосредственно времени, затрачиваемого на остановку поезда для посадки и высадки пассажиров, в разных ситуациях могут применяться и другие параметры.

Например, при проезде станции нам не важно, является она пересадочной или нет. Но если мы хотим пересесть на другую ветку, то при выборе оптимального пути нам нужно учесть сам факт перехода (оторвать попу от сидения – задача не из легких), длительность этого перехода (включая как непосредственно расстояние, которое необходимо пройти, так и интенсивность пассажиропотока и риск оказаться в толпе пингвинов), а также наличие лестниц или эскалаторов.

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

Но что, если при пересадке со станцию А на станцию Б надо подняться по лестнице, а при пересадке с Б на А – спуститься? Если вы тащите с собой чемодан без ручки, подъем по лестнице будет сложнее, зато на спуске прекрасно поможет гравитация. Получается, что вес ребра-пересадки будет зависеть еще и от направления движения. В таком случае пересадочные станции нам придется соединять не одним ребром, а двумя, с указанием направления движения на конкретном ребре (см рис. 4 со стрелочками), которое мы теперь можем гордо именовать дугой.

Граф, в котором все ребра имеют направления (являются дугами), называется ориентированным, в котором нет ни одной дуги – неориентированным, а тот, в котором есть и ребра, и дуги - смешанным.