ИННОВАЦИИ БИЗНЕСУ

Описание к ИЛ № 42-150-00

Результат выполнения научно-исследовательской работы .

При решении большого класса задач приходится решать проблему поиска множества путей, связывающих исходный и конечный узлы. Путем в графе g=(x,u) из узла i в узел k называется чередующаяся последовательность x _i, u _i, x _n, u _n, ... , x _k узлов и ребер, обладающая тем свойством, что любая пара соседних элементов инцедентна. Множество всех путей может быть представлено в виде матрицы П, где столбцы соответствуют элементам топологического графа, а строки - отдельным путям. Если элемент i входит в путь j, то на пересечении столбца i и строки j ставится 1, в противном случае - 0. Поиск путей должен начинаться с проверки условия связности графа и достижимости вершин. Большинство алгоритмических задач на графах и сетях можно представить как последовательность основных операций на множествах: принадлежности, вставки, удаления, объединения, поиска, разбиения и выделения минимального элемента [1]. Эффективность выполнения каждой из операций напрямую зависит от структуры данных. В качестве базового аналитического образа графа применяется io-представление, дополненное массивом функций стоимости С, заданное на его ребрах. Параметры io-представления это: q - число ребер, iu, ou - массивы из q элементов для орграфов. В случае неориентированного или смешанного графа каждое ребро представляется парой встречных дуг. Каждой дуге соответствуют элементы массивов iu(i)=k, ou(i)=l и cu(i)=y, где k - узел исхода дуги, l - узел захода дуги, y - проводимость ветви, соединяющей узлы k и l.

Задачи проверки связности и поиска путей целесообразно разбить на отдельные процедуры, выполняющие определенные операции преобразования элементов и представлений графа:

- преобразовать io-представление в матрицу непосредственных путей a;

- по матрице a методом поиска в глубину найти остовое дерево наибольшей стоимости и проверить условие связности графа;

- выделить остовый путь между заданными узлами;

- добавляя обратные ветви к остовому пути, определить все множество возможных путей;

- выделить независимые и зависимые пути.

Поскольку массивы io-представления и матрица непосредственных путей a эквивалентны одному и тому же графу, это позволяет установить между ними однозначное соответствие. Порядок матрицы непосредственных путей a определяется числом вершин в исходном графе, т.е. матрица является квадратной. Трансформация io-представления графа в квадратную матрицу a осуществляется с помощью поиска и замены элементов матрицы значениями из массива cu(i).

Элементы массивов iu и ou указывают на индекс строки i и столбца j соответственно. Элементу, принадлежащему i-й строке и j-му столбцу матрицы a, присваивается значение проводимости ветви y _ij, идущей из вершины i к вершине j, и нулевое, если такой ветви не существует.

Алгоритм построения остового дерева графа g=(x,u) методом поиска в глубину по матрице a осуществляется последовательностью операций с тремя множествами a, io и t. Поиск в глубину разбивает все ребра на два множества древесных и обратных ребер. Множество t является характеристическим вектором, i-й элемент которого равен 1, если i-ое ребро является древесным, и 0 - если обратным. Построение начинается с корневого узла v, затем выбираем ребро, инцидентное v наибольшей стоимости, и посещаем узел w, который помечаем как старый. Ветви, соединяющей узлы (v,w), в множестве t ставим в соответствие значение 1. Если узел w уже помечен как старый, то во множестве t ветви соответствует 0. Далее продолжаем поиск от узла w, последовательно помечая посещенные узлы. Пройдя все пути, начинающиеся в узле w, возвращаемся в v и ищем следующее ребро, инцидентное корневому узлу v. Перебор продолжаем до тех пор, пока не закончится список ветвей, исходящих из корневого узла v. Если граф несвязный, то отыскивается его связная компонента. Наличие непомеченных узлов является признаком несвязности графа. Выбирая в качестве начального новый узел, который еще не посещался, начинаем повторный поиск.

Наиболее эффективно процедура поиска реализуется по матрице непосредственных путей a. Каждая i-я строка матрицы соответствует определенному узлу. Анализируя состояние элементов строки, можно выбрать ветвь, исходящую из i-го узла и имеющую максимальную пропускную способность. Индекс столбца выбранного элемента укажет номер следующего узла и соответствующей ему строки. Элемент главной диагонали матрицы является индикатором посещения узла, если элемент равен 0, то элемент посещается впервые и равен 1 в противном случае.

Выделение остового пути целесообразно начинать с узла нагрузки и двигаться к корневому узлу, в качестве которого выступает узел источников. Процесс поиска осуществляется на элементах массивов iu, ou и характеристического вектора остового дерева t. Алгоритм производит выделение необходимых узлов при помощи

последовательного перебора элементов массива ou(i) и одновременной проверки принадлежности ветви к остовому дереву по условию t(i)=1. Соответствующий элемент iu(i) указывает номер следующего узла остового пути. Поиск заканчивается при достижении корневого узла. Полученные номера узлов и ветвей формируют первую строку матрицы путей П. Очевидно, что выделенный путь будет единственным и будет иметь максимальную пропускную способность.

Исходной информацией для определения множества всех путей являются io-представление, массив функций стоимости cu, характеристический вектор t и номера узлов остового пути. Суть метода состоит в поиске всех возможных ответвлений от остового и вновь образованных путей. На каждом шаге поиска, начиная с конечного узла, последовательно добавляем обратные ветви. Алгоритм, превращающий исходную информацию в матрицу путей П, удобнее сформулировать в виде последовательности операций:

1) выбираем узел У _i остового пути;

2) определяем инцидентные ему входящие ребра из множества обратных ветвей (t(i)=0);

3) выбираем ветвь с наибольшей пропускной способностью;

4) определяем исходящий узел У _k для выбранной ветви;

5) строим путь из выбранного узла У _k до корневого узла на множестве древесных ветвей (t(i)=1);

6) возвращаемся в узел У _i и повторяем операции пунктов 2-5;

7) если для узла У _i больше нет инцидентных входящих ветвей, то выбираем предшествующий узел остового пути У _i-1 и повторяем операции пунктов 2-6;

8) все множество полученных путей для узла У _i-1 дополняем ветвями остового и вновь образованных путей до нагрузочного узла;

9) множество всех полученных путей заносим в матрицу П. Процедура продолжается до тех пор, пока не будет использовано все множество обратных ребер. По завершении процедуры в матрице П будет находиться множество всех путей в порядке возрастания числа зависимых элементов.