Дискретная математика

161 практически осуществимо из-за большого числа вариантов. Получим метод решения указанной задачи, исключающей перебор. Для поиска кратчайшей цепи реализуем поиск в ширину - один из базисных алгоритмов, составляющих основу многих других. Общее правило для нахождения кратчайшей цепи в графе состоит в том, чтобы каждой вершине vj приписать индекс Xj, равный длине кратчайшей цепи из данной вершины в заданную вершину и. Приписывание индексов вершинам осуществляем в следующем порядке: 1) вершине и приписывается 0; 2) всем вершинам, из которых идет ребро в вершину и, приписывается индекс 1; 3) всем вершинам, еще не имеющим индексов, из которых идет ребро в вершину с индексом Xj, приписывается индекс Xj+l. Если одной и той же вершине можно приписать различные индексы, то приписываем минимально возможный индекс. Этот процесс продолжается до тех пор, пока не будет помечена заданная вершина v. По окончании приписывания индексов индекс вершины v будет равен длине кратчайшей цепи Z{v,u). Кратчайшую цепь найдем, если будем двигаться из вершины v в направлении убывания индексов. Нахождение кратчайшей цепи между произвольными вершинами в графе с ребрами произвольной длины. Задача приписывания вершинам графа числовых индексов немного усложняется, если ребра графа имеют произвольную длину. Усложнение вызвано тем, что цепь, содержащая наименьшее число рёбер, зачастую имеет большую длину, чем некоторые обходные цепи. Введем следующее правило приписывания числовых индексов: 1) вершине и приписывается индекс Лд-О. Для остальных вершин предварительно полагаем 2) ищем такое ребро {vt,vj), для которого ^fXi>/u(vuVj), и заменяем индекс Aj- вершины Vjновым индексом ^ :-Xi+p(Vi,Vj) < Xj. Продолжается этот процесс замены индексов до тех пор, пока остается хотя бы одна вершина, для которой можно уменьшить А,. При этом индексы будут обладать следующим свойством. Пусть Vp - произвольная вершина. При рассмотренном процессе приписывания индексов, индекс л,, монотонно уменьшается. Пусть - последняя вершина, послужившая для его уменьшения. Тогда для любого р найдётся q такое, что; Следовательно, для произвольной вершины Vp с индексом найдется вершина v.,, соединенная ребром с Vp, такая, что Xp-X^=ju(v,i,Vp). Это свойство позволяет сформупировать правило для нахождения кратчайшей цепи. Правило для нахождения кратчайшей цепи. 1. Приписать индексы всем вершинам, как указано ранее. 2. Пусть v „=v - заданная верошна (индекс которой получился равным А„). Ищем вершину v^,, такую, что X „-Xpi=f.ifvp,,v,J, Далее ищем