Пути и связность
С учетом сказанного путь в ненаправленном графе 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 является корнем дерева |
Еще по теме Пути и связность:
- Пути оттока
- Будьте верны своему пути
- Первая глава НА ПУТИ К ЧЕТВЕРТОМУ ИЗМЕРЕНИЮ
- Защита в пути
- По пути самосовершенствования
- По пути самосовершенствования
- Четыре пути к самоуважению
- Часть первая. Первые шаги на пути к успеху
- НА ПУТИ К ЗРЕЛОМУ СОЕДИНЕНИЮ
- ЛОВУШКИ НА ПУТИ ПЕРЕМЕН
- РЕТРО НА ПУТИ К БУДУЩЕМУ
- Тем, кто в Пути
- НАЧАЛО ПУТИ К УСПЕХУ
- Главлит на пути к монополии в цензуре
- 6.2. ВОСЕМЬ ШАГОВ НА ПУТИ К ИНТЕРПРЕТАЦИИ
- 13.1. Возможные пути развития общества
- Глава 2 Идеалы и пути к ним
- Плохая успеваемость, пути решения