Вычисление маршрутов между вершинами неориентированного дерева

ВЫЧИСЛЕНИЕ МАРШРУТОВ МЕЖДУ ВЕРШИНАМИ НЕОРИЕНТИРОВАННОГО ДЕРЕВА

Российский Университет Дружбы Народов, *****@***ru

Предложен алгоритм, программная реализация и численный пример метода вычисления маршрута между парами вершин неориентированного дерева.

Ключевые слова: граф сети, маршрут между вершинами дерева, таблица маршрутов.

Введение

Деревья – очень эффективный инструмент для представления различных структур данных. Поскольку для любого графа можно всегда построить покрывающее дерево, то многие вычисления удобно проводить именно на уровне деревьев. При анализе и построении сетей часто возникает задача определения маршрута между узлами. Для решения такой задачи уже существуют различные алгоритмы: например, алгоритмы Дейкстры, Уоршала-Флойда, Джонса, волновой алгоритм и другие. Каждый из этих алгоритмов наиболее эффективен в своем отдельном случае. В работе приводится альтернативный метод нахождения маршрутов между вершинами дерева.

Постановка задачи

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

Необходимо определить маршрут из некоторой заданной вершины в некоторую заданную вершину заданного дерева.

Решение

Дерево представляется в виде ориентированного дерева, ребра которого направлены к центральной вершине. То есть все ребра, смежные с корнем, входят из него, а ребра, смежные с концевыми вершинами, выходят из них. Матрица смежности полученного ориентированного дерева , имеет нижний треугольный вид с нулями на диагонали и выше нее.

Доказано, что и последовательность индексов задает единственный маршрут из вершины в центр дерева – вершину с номером (табл. 1).

Строки табл. 1 однозначно задают маршруты из каждой вершины в центральную, а по ним можно определить и маршруты из любых заданных вершин и до некоторой первой общей для них вершины , после которой их маршруты начинают совпадать. Для этого в строках и табл. 1 необходимо найти совпадающие элементы – такие и , что . Тогда последовательность a…p есть маршрут от вершины a до вершины p, а b…p есть маршрут от b до p.

Очевидно, что объединение таких маршрутов с переменой порядка на прямо противоположный для вершины , т. е. даст для исходного дерева маршрут из вершины в вершину .

Таблица 1. Таблица маршрутов из всех вершин дерева в его центральную вершину

1			…			1
2			…			1
…			…			…
			…			1
			…			1
…			…			…
			…			1

Алгоритм вычисления маршрута между парой вершин и

Задачу поиска маршрута из некоторой вершины в некоторую вершину b можно условно разделить на 2 части:

1.  Формирование матрицы , соответствующей табл. 1. Для этого по матрице смежности дерева составляется матрица смежности дерева . Для каждой вершины вычисляется путь до центра и заносится в соответствующие строки матрицы .

2.  Поиск маршрута из вершины в вершину по полученной матрице . Для этого элементы строки матрицы поочередно сравниваются с каждым из элементов строки матрицы . Как только найден формируется вектор : первые элементов вектора есть первые элементов строки матрицы , остальные элементов есть элементы матрицы из строки , записанные в обратном порядке – от элемента до .

Таким образом, полученный вектор представляет собой последовательность вершин, задающих маршрут из вершины в вершину . Алгоритм программно реализован в среде Scilab.

Выводы

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

Литература

1. лгоритмы: построение и анализ. –2-е. – М.: «Вильямс», 2005. – 1296 с.

2.Анищенко вычисления маршрутов в иерархической структуре.//Математическое и программное обеспечение вычислительных систем: Межвуз. сб. науч. тр. – Рязань: РГРТУ, 2012 – С. 70-76

3.еория графов. – М.: «Мир», 1973. – 301 с.

FINDING routeS between the vertices IN AN undirected TREE

Anishchenko A. A.

PFUR, *****@***ru

Propose an algorithm, program realization and an example of the method of finding the path between pairs of vertices of an undirected tree.

Кеу words: network graphs, path between the vertices, routing table.