4.4. Критерии корректности распределяющих карт маршрутизации

Рассмотрим любую СРКМ. Предположим, что она корректна. Тогда, если , то любой маршрут, определяемый СРКМ, является не более чем (N-1)-звенным. В противном случае в этих маршрутах существовали бы циклы, т.е. СРКМ определяла бы бесконечные маршруты, что противоречит определению её корректности.

Тогда критерий корректности СРКМ можно сформулировать в виде следующей теоремы.

Теорема 4.4.1: СРКМ корректна тогда и только тогда, когда любой определяемый ею маршрут передачи потоков данных для каждой пары узлов “источник-получатель” не содержит циклов.

Докажем сначала необходимость. Пусть СРКМ корректна и для некоторой пары “узел-источник ” и “узел-получатель ” определяет маршрут с содержащимся в нем циклом. Тогда любой маршрут, отличный от данного тем, что содержит этот цикл более, чем один раз, также будет входить в множество маршрутов, определяемых СРКМ. Так как число циклов можно увеличивать до бесконечности, то, следовательно, в этом множестве будут содержаться и бесконечные маршруты, что противоречит условию корректности СРКМ.

Теперь докажем достаточность. Согласно (4.3.3) любой конечный маршрут, определяемый СРКМ, будет заканчиваться в узле-получателе, так как при этом в остальных узлах интенсивность входящего потока будет равна интенсивности исходящего, а узел-получатель будет поглощать весь поток. Поскольку число узлов в графе конечно, то любой ациклический маршрут, определяемый СРКМ, будет конечным, т.е. СРКМ будет корректной.

Теорема 4.4.1. доказана. По существу она определяет критерий корректности СРКМ в терминах структуры допустимых маршрутов.

Рассмотрим теперь матричную интерпретацию корректности СРКМ. Пусть в графе G(A,R,W) имеется N узлов, т.е. . Расширим СРКМ следующим образом:

. (4.4.1)

Зафиксируем узел-получатель a_j и построим матрицу следующего вида:

. (4.4.2)

Из (4.3.3) и (4.4.2) следует, что сумма элементов матрицы (4.4.2) в каждой строке, кроме j-й, равна единице, а в j-й строке все элементы нулевые. Так как в графе G(A,R,W) нет дуг вида (a_i, a_i), то из (4.3.1) и (4.4.1) следует, что все диагональные элементы матрицы (4.4.2) будут нулевыми.

Теорема 4.4.2. СРКМ корректна тогда и только тогда, когда для любых и справедливо следующее соотношение:

. (4.4.3)

Докажем сначала необходимость. Пусть СРКМ корректна. Зафиксируем узел-получатель . Рассмотрим элементы матриц вида

. (4.4.4)

Рассуждая по аналогии с анализом коммуникационных возможностей ТКС по её матрице смежностей, можно утверждать, что если , то существует l-звенный маршрут из узла в a_j через , прокладываемый СРКМ.

Таким образом, если предположить, что уравнение (4.4.3) не выполняется, т.е. для некоторого узла верно, что , то существует циклический маршрут из a_i в a_j. Однако в таком случае из теоремы 4.4.1. следует, что СРКМ не корректна, что противоречит условию. Это означает, что требование (4.4.3) должно выполняться.

Докажем теперь достаточность. Пусть для рассматриваемой СРКМ выполняется уравнение (4.4.5). Это означает, что маршруты, определяемые СРКМ и состоящие не более, чем из (N-1) звеньев, будут ациклическими. Так как любой конечный маршрут в графе с N узлами будет не более, чем (N-1)-звенным, а любой цикл маршрута, определяемого СРКМ, не может проходить через узел-получатель, т.е. тоже будет не более, чем (N-1)-звенным, то из (4.4.3) следует, что все маршруты, определяемые СРКМ, будут ациклическими.

Таким образом, из теоремы 4.4.1. следует, что СРКМ будет корректна.

Теорема 4.4.2. доказана. По существу она определяет критерий корректности СРКМ в матричных терминах уравнения “корректности” (4.4.3).