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

Ориентированным k-звенным маршрутом на графовой модели ТКС будем называть последовательность различных (т.е. не повторяющихся) связей (рёбер)

r₁, r₂, …., r_k, (3.11)

таких, что для соответствующей последовательности k+1 узлов (где первые k элементов различны) ТКС

a₁,., a_k+1 (3.12)

справедливы соотношения

a_i® a_i+1, i=1, 2, …, k. (3.13)

Например, для графовой модели ТКС, изображённой на рис. 2.2, a) и b), последовательности узлов a₁, a₃, a₄, a₂ и a₃, a₄, a₂, a₁ образуют 3-звенные маршруты.

Ориентированный маршрут в ТКС является замкнутым, если

a₁= a_k+1, (3.14)

и незамкнутым, если

a₁¹ a_k+1. (3.15)

Замкнутый маршрут соединяет узлы ТКС a₁ и a_k+1.

Заметим, что незамкнутый (замкнутый) ориентированный маршрут в ориентированном графе ТКС с односторонними связями определяет соответствующий незамкнутый (замкнутый) маршрут в соответствующем неориентированном графе ТКС с двусторонними ли смешанными связями. Однако в общем случае обратное утверждение может быть неверно. Например, на рис. 3.1.а), узлы a₁, a₄, a₂ образуют 2-звенный незамкнутый маршрут, но из-за различной ориентации дуг не образуют ориентированный маршрут между вершинами a₁ и a₂. В то же время существует 1-звенный ориентированный маршрут между этими вершинами.

Ориентированную графовую модель ТКС будем называть сильносвязной, если для любой пары вершин s и f существуют ориентированный маршрут из s в f и из f в s. Сильная связанность ориентированного графа означает связность соответствующего неориентированного графа G ТКС.

Можно показать [69], что ориентированный граф ТКС с односторонними связями сильно связан тогда и только тогда, когда существует замкнутый ориентированный маршрут, в которой каждая дуга входит один раз.

Ориентированный граф ТКС с односторонними связями будем называть сильно n-связным, если для каждой пары различных узлов ТКС s и f, s ¹ f, существует, по крайней мере, n маршрутов из s в f, которые не имеют общих узлов и связей (рёбер), кроме, конечно, узлов s и f.

Для сильной n-связности ориентированного графа необходимо (но, вообще говоря, недостаточно), чтобы соответствующий неориентированный граф G был n-связным [69].

Рассмотрим ТКС с односторонними (доминирующими) связями. Если соответствующий ей ориентированный граф является сильно связным, то каждый узел ТКС может связаться с любым другим узлом ТКС, по крайней мере, одним маршрутом. Если граф сильно n-связан, то существует, по крайней мере, n различных маршрутов связи между любыми узлами ТКС. Отсюда следует, что для того, чтобы полностью прервать связь между любыми двумя узлами ТКС, необходимо разорвать каналы связи, по крайней мере, в n узлах ТКС [69].

Определим расстояние d(s, f) между двумя различными узлами s и f, s ¹ f, графовой модели ТКС как число связей (рёбер), содержащееся в ориентированном маршруте, соединяющим эти узлы. Тогда, очевидно, что

d(s, s) = 0 для всех s Î A, d(s, f) > 0, если s ¹ f, (3.16)

d(s, f)= d(f, s), d(s, a)+d(a, f)³ d(s, f), (3.17)

т.е. функция расстояния обладает всеми обычными свойствами метрики.

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

. (3.18)