Коммуникабельность полносвязных компьютерных сетей со смешанными связями

Рассмотрим ТКС из N узлов со смешанными связями, имеющую полносвязную топологию. В этом случае между любыми двумя узлами ТКС существуют односторонние или двухсторонние связи вида (3.2) или (3.3) и не существует связей вида (3.4).

Возникает вопрос: существует ли в этой ТКС по крайней мере один узел, который связан с каждым из остальных узлов ТКС однозвенным или двузвенным маршрутом? Положительный ответ на этот вопрос означает, что в ТКС с полносвязной топологией имеется один или несколько узлов, которые могут послать каждому другому узлу ТКС или получить от каждого другого узла ТКС однозвенное или двузвенное сообщение.

Теорема 3.1. Предположим, что ТКС имеет полносвязную топологию и состоит из N узлов c произвольными (смешанными) связями. Тогда существует по крайней мере один узел ТКС, который может

1) послать любому другому узлу ТКС однозвенное или двузвенное сообщение, т.е. между ними существует одно- или двузвенный маршрут;

2) получить от любого другого узла ТКС однозвенное или двузвенное сообщение, т.е. между ними существует одно- или двузвенный маршрут.

Сначала докажем первое утверждение теоремы с помощью следующей леммы [69].

Лемма 3.1. Если узел a₁ не может послать однозвенное или двузвенное сообщение каждому из остальных узлов ТКС, т.е. a₂, a₃, …., a_N, то число узлов ТКС, которыми узел a_i, i¹ j, может послать однозвенное сообщение, по меньшей мере на 1 больше числа узлов ТКС, которым узел a_i, i¹ j, может послать однозвенное сообщение.

Для доказательства этой леммы заметим, что из условия теоремы 1 следует, что

(i) если узел a₁ не может послать узлу a_i, i¹ j однозвенное сообщение (т.е. если неверно, что a₁ ®a_i), то

a_i ®a₁, (3.56)

(ii) если узел a₁ не может послать узлу a_i, i¹ j двузвенное сообщение (т.е. если для всех k неверно, что a₁ ®a_k ®a_i), то из a₁ ®a_k следует также, что

a_i ®a_k. (3.57)

Действительно, если a₁ ®a_k, то неверно, что a_k ®a_i. Тогда ввиду полносвязности ТКС (по условиям теоремы 3.1) справедливо соотношение (3.57), т.е. узел a_i доминирует над узлом a_k.

Согласно утверждению (ii), если узел a₁ может передать однозвенное сообщение какому-нибудь другому узлу a_k ТКС, то тому же узлу a_k может передать однозвенное сообщение также и узел a_i, i¹ 1, i¹ k. C учётом условия (i) отсюда следует, что узел a_i может передать по крайней мере на одно однозвенное сообщение больше, чем узел a₁.

Используем лемму 1 для доказательства теоремы 1. Пусть

. (3.58)

Назовём r_i рангом i -ой строки коммуникационной матрицы C для полносвязной ТКС. Предположим, что ранг r₁ является максимальным среди оcтальных рангов (3.58) (Этого всегда можно добиться соответствующим переименованием узлов a₁, a₂, …., a_N ТКС).

Докажем, что в этом случае для узла a₁ справедливо первое утверждение теоремы 3.1. Предположим противное. Тогда существует узел a_i, i > 1, которому a₁ не может передать однозвенное или двузвенное сообщение. В этом случае, число узлов ТКС, которым узел a_i может передать однозвенное сообщение, по крайней мере на 1 больше числа узлов ТКС, которым узел a₁ может передать однозвенное сообщение. Отсюда следует, что r_i > r₁. Но это противоречит предположению о том, что

. (3.59)

Полученное противоречие завершает доказательство утверждения теоремы 1.

Аналогичным образом доказывается второе утверждение теоремы 1 [69].

Теорему 3.1 можно переформулировать на языке коммуникационных матриц ТКС.

Теорема 3.2. Пусть С - коммуникационная матрица ТКС с полносвязной топологией, состоящей из N узлов с произвольными (смешанными) свзями. Тогда в матрице

S⁽²⁾ = C + C² (3.60)

существует

1) хотя бы одна строка, все элементы которой (за исключением элементов на главной диагонали) больше 0, т.е.

(3.61)

2) хотя бы один столбец, все элементы которого обладают свойством (3.61).

Следствие 3.1. В условиях теоремы 3.2 справедливы следующие утверждения:

1) узел ТКС, который имеет максимальную сумму элементов строки коммуникационной матрицы С, может передавать однозвенные или двузвенные сообщения каждому из остальных узлов ТКС, т.е. между этими узлами существует одно- или двузвенный маршрут;

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

В качестве примера рассмотрим полносвязную ТКС со смешанными связями, изображённую на рис.3.1, а). Для этой ТКС выполнены условия теоремы 3.1 и поэтому справедливы её первое и второе утверждения.

Коммуникационная матрица рассматриваемой ТКС C_a имеет вид (3.7). Её первая, третья и четвёртая строки имеют максимальную сумму элементов, равную 2. Поэтому узлы a₁, a₃ и a₄ могут передавать однозвенное или двузвенное сообщение каждому узлу этой ТКС, т.е. между этими узлами сушествуют одно- или двузвенные маршруты.

Однако узел a₂ может передавать узлу a₁ только трёхзвенное сообщение. Для второго столбца матрицы C_a сумма его элементов является максимальной и равна 3. Поэтому узел a₂ может получить однозвенное или двузвенное сообщение от остальных узлов ТКС.

Узлы a₃ и a₄ такжемогут получить однозвенные или двузвенные сообщения от остальных узлов ТКС. Однако узел a₁ не обладает этим свойством.