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

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

С учетом сказанного путь в ненаправленном графе G = (V, E) определяется как последовательность P узлов v1, v2, ..., vk-1, vk, обладающая тем свойством, что каж- дая очередная пара v., v.+ 1 соединяется ребром из G. P часто называется путем из v1 в vk, или путем v1 - vk. Например, узлы 4, 2, 1, 7, 8 образуют путь на рис. 3.1. Путь называется простым, если все его узлы отличны друг от друга. Цикл представляет собой путь v1, v2, ..., vk-1, vk, в котором k > 2, первые k - 1 узлов различны, а v1 = vk, — другими словами, последовательность узлов, которая «возвращается» к своему началу. Все эти определения естественным образом переносятся на направленные графы со следующим изменением: в направленном пути или цикле каждая пара последовательных узлов обладает тем свойством, что (v, v.+ 1) является ребром. Другими словами, последовательность узлов в пути или цикле должна учитывать направленность ребер.

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

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

коммуникационной или транспортной сети; для перехода из и в v хотелось бы вы- брать маршрут с минимальным количеством «пересадок».

Рис. 3.1. Два представления одного дерева. В правой части хорошо видно, что узел 1 является корнем дерева


<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Пути и связность:

  1. Пути оттока
  2. Будьте верны своему пути
  3. Первая глава НА ПУТИ К ЧЕТВЕРТОМУ ИЗМЕРЕНИЮ
  4. Защита в пути
  5. По пути самосовершенствования
  6. По пути самосовершенствования
  7. Четыре пути к самоуважению
  8. Часть первая. Первые шаги на пути к успеху
  9. НА ПУТИ К ЗРЕЛОМУ СОЕДИНЕНИЮ
  10. ЛОВУШКИ НА ПУТИ ПЕРЕМЕН
  11. РЕТРО НА ПУТИ К БУДУЩЕМУ
  12. Тем, кто в Пути
  13. НАЧАЛО ПУТИ К УСПЕХУ
  14. Главлит на пути к монополии в цензуре
  15. 6.2. ВОСЕМЬ ШАГОВ НА ПУТИ К ИНТЕРПРЕТАЦИИ
  16. 13.1. Возможные пути развития общества
  17. Глава 2 Идеалы и пути к ним
  18. Плохая успеваемость, пути решения