Графовые модели компьютерных сетей с односторонними, двусторонними и смешанными связями

ТКС представляет собой множество из N узлов хранения и передачи данных (сообщений) с некоторым числом каналов связи между ними.

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

A= { a₁, a₂, …., a_N }. (3.1)

Здесь a_i - i- ый узел ТКС и N=|A|, т.е. мощность (объём) множества A.

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

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

Односторонние связи между узлами a_i и a_j ТКС будем обозначать следующим образом

a_i ® a_j или a_j ® a_i , i¹ j, (3.2)

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

Двухсторонние связи между узлами a_i и a_j ТКС имеют вид

a_i «a_j, i¹ j. (3.3)

Эти связи не создают отношения доминирования между связанными узлами ТКС.

Единственное ограничение, которое накладывается на связи узлов ТКС, заключается в том, что никакой узел не имеет связи с самим собой, т.е. в узлах ТКС не существует внутренних обратных связей вида

a_i ® a_i, или a_i «a_i, i=1, 2, …, N. (3.4)

Например, в случае телефонных ТКС естественная недопустимость связей (3.4) означает, что абонент (узел) сети не может созвониться (связаться) с самим собой.

Графовой моделью (ГМ) ТКС будем называть её изображение в виде неориентированного или направленного (ориентированного) коммуникационного графа (КГ), называемого также орграфом. В прикладных задачах число узлов и связей (рёбер) графа ТКС всегда конечно. Для локальных ТКС это число не велико, а для глобальных ТКС оно может иметь большие значения [1–3, 6.69].

На рис. 3.1 изображены три простейшие графовые модели ТКС со смешанными связями вида (3.2) и (3.3).

Рис. 3.1. Примеры графовых моделей ТКС со смешанными связями

На изображении ТКС в виде коммуникационного графа точками обозначаются узлы, рёбрам соответствуют связи между ними, а стрелки указывают отношения доминирования для узлов с односторонними связями (3.2) или двусторонние связи (3.3). Например, на рис. 3.1, а) узел a₁ имеет односторонние связи с узлами a₂ , a₃ и a₄ и доминирует над ними, а узлы a₂ и a₃ имеют двухсторонюю связь (без доминирования).

Ориентированную графовую модель ТКС с односторонними связями будем обозначать через . Она состоит из непустого множества A узлов (вершин) вида (3.1), множества доминирующих связей R, построенной над множеством пар элементов из A, и отображения множества R на множество (A´ A)= . Элементы A и R являются соответственно узлами (вершинами) и рёбрами (связями). Отображение задаёт отношение доминирования между парами связанных узлов коммуникационного графа, а ориентированным отображением . Если rÎ R соответствует ребру между узлами s и f, а , то ребро (связь) r имеет начальный узел s и конечный узел f, т.е. имеет место односторонняя связь вида

s® f. (3.5)

Таким образом, для ТКС с односторонними (доминирующими) связями справедливо соотношение

. (3.6)

Если задана ориентированная графовая модель ТКС вида (3.6), то соответсвующий неориентированный граф для ТКС с двусторонними связями имеет вид

, (3.7)

где

F (r) = и , если . (3.8)

Для описания локальных свойств структуры ориентированных графовых моделей ТКС, заметим, что если между узлами ТКС имеют место соотношения (3.5), то соответствующие связи направлены от узла s к узлу f. В этом случае связь (ребро) r является положительно инцидентной её конечному узлу f.

Число связей (рёбер), положительно инцидентных узлу f, будем называть положительной степенью узла f для ТКС с односторонними связями и обозначать через q⁺ (r). Аналогично введём понятие и обозначение отрицательной степени узла q^- (r). Тогда двусторонняя связь, инцидентная узлу f, будет положительно и отрицательно инцидентной с этим узлом ТКС.

Поскольку каждая односторонняя (доминирующая) связь является положительно инцидентной одному узлу ТКС и отрицательно инцидентной также одному узлу ТКС, то справедливо уравнение “баланса” вида [19, 69]

, (3.9)

где M= |R| означает число односторонних (доминирующих) связей ориентированного графа (3.6). Поэтому для ориентированных графовых модeлей ТКС имеет место соотношение

. (3.10)