Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Ориентированные маршруты, связность и диаметр графовых моделей компьютерных сетей
Ориентированным k-звенным маршрутом на графовой модели ТКС будем называть последовательность различных (т.е. не повторяющихся) связей (рёбер) r1, r2, …., rk, (3.11) таких, что для соответствующей последовательности k+1 узлов (где первые k элементов различны) ТКС a1,., ak+1 (3.12) справедливы соотношения ai® ai+1, i=1, 2, …, k. (3.13) Например, для графовой модели ТКС, изображённой на рис. 2.2, a) и b), последовательности узлов a1, a3, a4, a2 и a3, a4, a2, a1 образуют 3-звенные маршруты. Ориентированный маршрут в ТКС является замкнутым, если a1= ak+1, (3.14) и незамкнутым, если a1¹ ak+1. (3.15) Замкнутый маршрут соединяет узлы ТКС a1 и ak+1. Заметим, что незамкнутый (замкнутый) ориентированный маршрут в ориентированном графе ТКС с односторонними связями определяет соответствующий незамкнутый (замкнутый) маршрут в соответствующем неориентированном графе ТКС с двусторонними ли смешанными связями. Однако в общем случае обратное утверждение может быть неверно. Например, на рис. 3.1.а), узлы a1, a4, a2 образуют 2-звенный незамкнутый маршрут, но из-за различной ориентации дуг не образуют ориентированный маршрут между вершинами a1 и a2. В то же время существует 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)
|