Матрицы инциденций, матрицы смежности и матрицы маршрутов

Графовой модели ТКС, имеющей N узлов и М рёбер (каналов связей) можно сопоставить матрицу инциденций E размерности N´ M, столбцы и строки которой соответствуют узлам и рёбрам графа. Элементы этой матрицы определяются по формулам

(3.27)

Матрица инциденций характеризует некоторые важные свойства графа ТКС. Например, поскольку ребро графа инцидентно только двум вершинам графа, то каждый столбец матрицы Е= | e_ij | содержит ровно два единичных элемента.

Каждой подсети ТКС, рассматриваемой как его компонента (подграф), соответствует подматрица E_k матрицы инциденций E. При соответствующей нумерации узлов и рёбер внутри каждой k-ой компоненты и между всеми компонентами матрицу E всегда можно представить в блочно-диагональной форме.

Матрица инциденций E обеспечивает полное описание коммуникационного графа (графовой модели) ТКС.

Для ориентированных и неориентированных графов ТКС с односторонними или двусторонними связями можно определить матрицу смежности узлов Q размерности N´ N. Элементы q_ij этой матрицы на пересечении i -ой строки и j -ого столбца определяются как число рёбер (односторонних или двусторонних связей), ориентированных от узла i к узлу j (в случае односторонних связей) или инцидентных одновременно i -ому и j -ому узлу ТКС (в случае двусторонних связей). Если q_ij = 0, то это означает, что i -ый и j -ый узел не связаны рёбром.

Степени матрицы смежности Q¹, Q², …, Q^k несут важную информацию о существовании 2-, 3-, …, k-звенных маршрутов между любыми узлами ориентированного графа ТКС с односторонними свзями, а именно: элементы матрицы Q^k равны числу ориентированных k-звенных маршрутов между соответствующими узлами ТКС.

Таким образом, для ТКС с ориентированными связями каждый узел достижим из любого другого узла ориентированным маршрутом, состоящим из k рёбер (односторонних связей).

По графу ТКС, узлы которого перенумерованы, можно построить матрицу маршрутов (коммуникационных путей) Р. Строки этой матрицы соответствуют ориентированным маршрутам из первого узла a₁ в последний a_N, а столбцы - рёбрам графа ТКС. При этом элементы p_ij матрицы маршрутов P принимают значение 1 или 0 в зависимости от того, принадлежат ли данное ребро графа данному маршруту или нет.