К.т.н. Борисова Л.Ф.

Мурманский государственный технический университет (МГТУ), г. Мурманск, Российская Федерация

Вопросы теории графов кодовых пересечений в приложении к сетевым задачам

При анализе различных сетей основными структурными показателями являются диаметр, связность, порядок узлов и другие. Диаметр определяет время обслуживания. Связность определяет степень устойчивости информационной сети к отказам или блокировкам линий передачи. В транспортной сети связность определяет возможность системы сохранять работоспособность в случае блокировок приоритетных направлений движения (автомобильный, морской транспорт) вследствие наличия мешающих факторов (посторонние объекты, предметы, льды и т.д.). Порядок узлов определяет максимальное среди всех узлов сети число инцидентных ребер. Варьируя эти показатели, можно изменять топологию и качество работы или обслуживания системы. Решение о выборе той или иной топологии невозможно принять без анализа и учета основных структурных показателей, к которым относятся количество вершин и их степеней в графе. Использование графов кодовых пересечений (ГКП) для представления сетевых топологий позволяет упростить решение многих задач. При исследовании ГКП использованы понятия и термины в соответствии с [1].

Теорема 1. В любом неориентированном ГКП(n, k, r), r=r*, G(A,V) с множеством вершин А и множеством ребер V существуют kⁿ вершин, из которых:

1) k^r вершин имеют степень deg a = 2k^r-k^2r-n-1, 2r³n, deg a = 2k^r-2, 2r<n, a Î A,

2) k^r (k^r – 1) вершин имеют степень deg a = 2k^r-1, 2r < n ≤ 4r, a Î A,

3) остальные вершины имеют степень deg a = 2k^r-k^2r-n, 2r ³ n, deg a = 2k^r, n > 4r, a Î A,

Доказательство. В ГКП(n, k, r) существуют kⁿ вершин, из которых ровно k^r вершин имеют кодовые комбинации номеров, у которых n-r* первых символов совпадают с n-r последними символами при любых значениях n и r (условие 1). Действительно, если 2r ³ n, то комбинаций, удовлетворяющих условию 1, всего k^n-r k^2r-n = k^r. Если 2r < n, то в кодовой комбинации n-r* символов пересекаются с n-r символами по n-2r символов. Следовательно, разнообразных кодовых комбинаций, удовлетворяющих условию 1, в k^n-2r раз меньше, чем k^n-r, т.е. k^r. Эти вершины имеют степень 2k^r-2, если 2r < n, так как каждая вершина имеет по k^r-1 соседей по прямому и обратному зацеплениям, и степень 2k^r-k^2r-n-1, если 2r ≥ n, так как каждая вершина имеет по k^r-1 соседей, k^{2r – n}-1 из которых совпадают. Остальные kⁿ-k^r вершин, если 2r ³ n, имеют по k^r соседей по каждому виду зацеплений, k^{2r – n} из которых совпадают, т.е. степень этих вершин равна 2k^r-k^2r-n. Если 2r < n, то в любой кодовой комбинации n-r символов пересекаются с n-r* символами по n-2r символов. Если соотношение параметров n и r таково, что 2(n – 2r) ≤ n, т.е. 2r < n ≤ 4r (условие 2), то k^n-r – k^n-2r = k^n-2r (k^r- – 1) вершин имеют k^r соседей по одному зацеплению и k^r-1 соседей по обратному, т.е. 2k^r-1. Из условия 2 имеем n=3r. После подстановки выражение (3.4) примет вид: k^r (k^r-1). Остальные kⁿ-k^r-k^r(k^r-1) вершин имеют по k^r соседей по каждому виду зацепления, т.е. их степень равна 2 k^r. Если n > 4r, то все kⁿ-k^r вершин имеют степень 2 k^r.

Теорема 2. В любом ориентированном ГКП(n, k, r), G(A,V) с множеством вершин А и множеством дуг V существуют é(kⁿ(k^r-1))/(kⁿ-1)ù+1 вершин, где éxù – наименьшее целое, не меньшее х, имеющих od(a) = id(a) = (k^r-1), aÎA и kⁿ-é(kⁿ(k^r-1))/(kⁿ-1)ù-1 вершин, имеющих od(a) = id(a) = k^r, aÎA.

Доказательство. Для доказательства удобно воспользоваться представлением матрицы смежности ГКП в виде аналитической записи матричных преобразований:

М_ГКП = М_ПКП – Е¹, М_ПКП = Р (Е Ä М_ф),

где P ==║p_i,j║, p_i,j = 1, если i=b, j=c , p_i,j = 0, если i≠b, j≠c, b = (m - 1) k^n-r + l-1, c = (l - 1) k^r + m - 1, l = 1, 2, …, k^n-r, m = 1, 2, …, k^r, – матрица размером kⁿ´kⁿ; Е¹ – (kⁿ´ kⁿ) – единичная матрица; M_ф=║m_i,j║ : m_i,j = 1 – матрица размером k^r´k^r; Е – (k^n-r´ k^n-r) – единичная матрица. Нулевые элементы существуют только в позициях матрицы смежности, расположенных на главной диагонали, с номерами (m - 1) k^n-r + l – 1 = (l - 1) k^r + m – 1, l = 1, 2, …, k^n-r, m = 1, 2, …, k^r. Отсюда m – 1 = é((l – 1)(k^r-1))/(k^n-r - 1)ù, что соответствует номерам позиций (l – 1) k^r + é((l – 1)(k^r-1))/(k^n-r - 1)ù = (l – 1) é(kⁿ-1)/(k^n-r-1)ù, где l = é(m - 1) (k^n-r – 1)/(k^r - 1)ù + 1, m = 1, 2, …, k^r. Частота нулевой позиции среди всех диагональных позиций определяется при m=2, а именно: é(kⁿ-1))/(k^r-1)ù. Отсюда общее число нулевых позиций, расположенных на главной диагонали (с учетом позиции, соответствующей номеру "0") равно: é(kⁿ(k^r-1))/(kⁿ-1)ù+1. Вследствие наличия нулевых элементов вдоль главной диагонали матрицы смежности ГКП, вершины с номерами, определенными выше, имеют полустепени исхода и захода на единицу меньше, чем все остальные вершины ГКП, а именно: od(a) = id(a) = (k^r-1). Остальные kⁿ - é(kⁿ(k^r-1))/(kⁿ-1)ù-1 вершин имеют od(a) = id(a) = k^r.

Теорема 3. Реберная связность λ любого ГКП(n, k, r), G(A,V) определяется величиной параметра k: λ ³ 2k-2, k=2, 3,... .

Доказательство. Реберная связность неориентированного графа определяется минимальной степенью вершин. Согласно теореме 1 реберная связность неориентированного ГКП для любых n, и k при r=1 равна λ=2k-2. Очевидно, что минимально возможная реберная связность неориентированного ГКП λ=2 для любого n при k=1 и r=1.

Реберная связность ориентированного графа определяется минимальной суммой полустепеней исхода и захода. Согласно теореме 2, реберная связность ориентированного ГКП в предельном случае при r=1 для любых n и k равна λ=2k-2. Очевидно, что минимально возможная реберная связность неориентированного ГКП λ=2 для любого n при k=1 и r=1.

Следствие. Удаление любых 2k-3 вершин из множества А вершин ГКП не приводит к несвязному или тривиальному графу.

Теорема 4. Максимальная из минимальных длин маршрутов (простых цепей – совокупностей точек поворота курса, траекторий движения) – диаметр – в любом ГКП(n, k, r) определяется только соотношением длины кодовых комбинаций номеров вершин и мощностью пересечений этих комбинаций и не зависит от основания кода: d = én / rù, "k, где éxù – наименьшее целое, не меньшее х. При этом требование d = éxù означает, что d ≥ 2, т.к. d=1 справедливо для полносвязанной структуры, которая не является ГКП, d=0 справедливо для несвязного графа.

Доказательство. Пусть ГКП – ориентированный. Для доказательства используем алгоритм отыскания путей в сетях со структурами ГКП(n, k, r) [1]. Построение множества путей производится для двух соотношений параметров: lr ≥ n и lr < n, где l – длина пути, 0 < l < kⁿ. Максимальная из минимально возможных длин путей d будет наименьшей в неравенстве lr ≥ n и наибольшей в неравенстве lr ≤ n. Пусть ГКП – неориентированный. Неориентированный ГКП(n, k, r), GA может быть представлен объединением двух ориентированных графов. Диаметры обоих графов равны d = én / rù, следовательно, диаметр неориентированного ГКП принимает то же значение.

При синтезе оптимальной топологии сети обычно требуется обеспечить минимальный диаметр при заданной связности.

Теорема 5. Если требования к живучести сети заданы в виде связности λ, то диаметр ГКП(n, k, r) равен:

· ориентированного ГКП: d = én / log_k (λ+1)ù или d = é(n – r) / log_k (λ+1)ù +1,

· неориентированного ГКП: d = én / log_k (0.5λ+1)ù или d = é(n – r) / log_k (0.5λ+1)ù +1.

Доказательство. Минимальная реберная связность графа определяется минимальной из степеней его вершин. Из теорем 1 и 2 имеем в ориентированном ГКП λ=k^r-1, отсюда r = log_k (λ+1), а в неориентированном ГКП λ=2k^r-2, отсюда r = log_k (0,5λ+1).

Теорема 6. Диаметр любого ГКП(n, k, r) G(A,V) с множеством вершин А и множеством дуг V растет не быстрее d = é(log_k A) / rù. Таким образом, значения А числа вершин в ГКП с ростом диаметра d растут практически неограниченно: A = k^dr.

Доказательство. Для доказательства используем теорему 4 и выражение n=log_k A.

Как правило, диаметр сетей, особенно тех, которые ориентированы на соединение большого числа узлов, тем больше, чем меньше порядок узлов сети. Порядок d вершин ГКП(n, k, r) для различных групп параметров определяем, воспользовавшись теоремой 1:

d = max deg a = aÎA

2k^r, 2k^r – 1, 2k^r – 2, 2k^r – 2k^2r-n,

4r < n 2r < n £ 4r 2r = 4 2r > n.

Оптимальные значения δ соответствуют группе параметров, для которых справедливо соотношение 2r=n. Из нескольких структур с равным числом вершин и диаметром лучше та, в которой порядок вершин меньше. При соотношении параметров n≥2r порядок вершин в ГКП при заданном значении k не зависит от числа вершин A=kⁿ и может регулироваться изменением параметра r. ГКП с такими параметрами являются предпочтительными для практических применений, когда требуется выбрать оптимальную структуру при заданном А. При соотношении параметров 2r>n выбор структур ограничен.

Зависимость порядка вершин в ГКП от его диаметра получаем с учетом теорем 1 и 3: d = 2k^r – 2k^r(2-d), n £ 2r; d = 2k^n/d, n > 2r. При соотношении параметров 2r ≥ n порядок вершин не зависит от диаметра, а определяется лишь параметрами ГКП, т.к. в таких структурах, согласно теореме 4, диаметр не превышает значения d = én / rù = é(2r – 1) / rù. При соотношении параметров n ≥ 2r в графах кодовых пересечений с равным числом вершин диаметр тем меньше, чем больше порядок вершин. Рост числа вершин в ГКП при заданном диаметре сопровождается ростом порядка вершин.

Для анализа топологий с разным числом узлов, которые имеют разные диаметры и разные порядки узлов, удобно использовать обобщенный структурный показатель ψ, представляющий собой произведение диаметра сети на порядок ее узлов: y = dd = 4k^r – 4, n £ 2r; y = 2dk^n/d, n > 2r. Здесь учтено, что в случае, когда n≤2r, диаметр d=2. При n≤2r показатель ψ ГКП не зависит от диаметра и тем больше, чем больше число вершин. Если n>2r при d>4 обобщенный показатель ψ ГКП практически не зависит от диаметра и тем больше, чем больше число вершин. В сетях с постоянным числом узлов, варьируя соотношением параметров n и r, можно добиваться изменения диаметра, что в определенных пределах, позволяет улучшать обобщенный структурный показатель сети.

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

Литература:

1. Амосов, А. А. Метод определения путей в сетях связи / А. А. Амосов, М. М. Шарипова // Техника средств связи. Сер. ТПС. - 1977. - Вып. 8(18). - С.15-22.