Пути и связность

Одной из основополагающих операций с графами является обход последовательности узлов, соединенных ребрами. В приведенных выше примерах такой обход может соответствовать сеансу просмотра веб-страниц с переходами по гиперссылкам; слухам, передаваемым между людьми на другой конец света; перелету авиапассажира из Сан-Франциско в Рим с несколькими пересадками.

С учетом сказанного путь в ненаправленном графе G = (V, E) определяется как последовательность P узлов v1, v2, …, vk–1, vk, обладающая тем свойством, что каждая очередная пара vi, vi+1 соединяется ребром из G. P часто называется путем из v1 в vk, или путем v1 – vk.

Цикл представляет собой путь v1, v2, …, vk–1, vk, в котором k > 2, первые k − 1 узлов различны, а v1 = vk, — другими словами, последовательность узлов, которая «возвращается» к своему началу.

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

Ненаправленный граф называется связным, если для каждой пары узлов u и v существует путь из u в v. Для направленных графов способ определения связности не столь очевиден: может оказаться, что в графе существует путь из u в v, тогда как пути из v в u не существует. Направленный граф называется сильно связным, если для каждых двух узлов u и v существует путь из u в v, и путь из v в u.

Кроме самого факта существования пути между парой узлов u и v нам, возможно, понадобится узнать, существует ли короткий путь. Расстояние между двумя узлами нами u и v определяется как минимальное количество ребер в пути u–v.

(Для обозначения расстояния между узлами, между которыми не существует соединяющего пути, можно использовать условный знак — например, ∞). Чтобы понять, откуда происходит термин «расстояние», вообразите G как представление коммуникационной или транспортной сети; для перехода из u в v хотелось бы выбрать маршрут с минимальным количеством «пересадок».