Пути и связность
Одной из основополагающих операций с графами является обход последователь- ности узлов, соединенных ребрами. В приведенных выше примерах такой обход может соответствовать сеансу просмотра веб-страниц с переходами по гипер- ссылкам; слухам, передаваемым между людьми на другой конец света; перелету авиапассажира из Сан-Франциско в Рим с несколькими пересадками.
С учетом сказанного путь в ненаправленном графе 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, — другими словами, последовательность узлов, которая «возвращается» к своему началу.
Ненаправленный граф называется связным, если для каждой пары узлов u и v существует путь из u в v. Для направленных графов способ определения связности не столь очевиден: может оказаться, что в графе существует путь из u в v, тогда как пути из v в u не существует. Направленный граф называется сильно связным, если для каждых двух узлов u и v существует путь из u в v, и путь из v в u.
Кроме самого факта существования пути между парой узлов u и v нам, возмож- но, понадобится узнать, существует ли короткий путь. Расстояние между двумя узлами нами u и v определяется как минимальное количество ребер в пути u–v.
(Для обозначения расстояния между узлами, между которыми не существует соединяющего пути, можно использовать условный знак — например, ∞). Чтобы понять, откуда происходит термин «расстояние», вообразите G как представление коммуникационной или транспортной сети; для перехода из u в v хотелось бы вы- брать маршрут с минимальным количеством «пересадок».
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу