Методические указания к задаче 1

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

вторичной сети), а ребра (ветви), соединяющие узлы, линиям связи первичной сети или пучкам каналов вторичной сети. В зависимости от свойств линий связи,

ребра могут быть ориентированными (направленными) или неориентированными

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

Для передачи информации в сети от узла коммутации УК _i к УК _j должен быть

использован путь , который представляется упорядоченным набором ребер и узлов, входящих в данный путь. Рангом пути г( ) называется число составляю-щих его ребер графа (линий связи сети).

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

большим индексом, то оно обозначается символами, например, a, b, c…. В про-

тивном случае - , ….

Сечением сети по отношению к узлам i и j называется минимальная совокуп-ность ребер, которые нужно изъять из сети с тем, чтобы узлы УК _i к УК _j оказались

в разных, не связанных между собой, частях сети.

Существуют различные методы отыскания путей в графе сети. Рассмотрим графический и матричный метод отыскания путей.

Графический метод является одним из наиболее простых и поддающихся машинизации способов построения дерева путей. Этот способ позволяет опреде-лить все простые пути от одного заданного узла ко всем остальным узлам сети и состоит из построения дерева путей и просотру по этому дереву каждого пути.

Дерево путей для заданного узлу i строится по графу сети с использованием следующего алгоритма:

1. Отмечаем узел i и выбираем смежные с данным узлом узлы графа сети.

2. Получаем узлы узлы первого яруса по отношению к узлу i.

3. Для образования узлов r-го яруса (r = 2, 3, …, h, где h – максимально допустимое число переприемных участков в пути):

а) поочередно рассматриваем узлы (r – 1)-го яруса;

б) для каждого узла k в (r – 1) –ом ярусе выбираем поочередно смежные узлы;

в) исключаем номера узлов, относительно которых были образованы подмножества узлов в предыдущих ярусах, связанных узлом k. Оставшиеся узлы

соответствуют подмножеству узлов r-го яруса, образованного узлом k.

4. Построение дерева путей продолжается до заданного h-го яруса.

Имея дерево путей относительно узла i, легко проследить любой из возможных

путей с заданным числом переприемных участков r (рангом пути) между фиксированным узлом i и произвольным узлом j. Для этой цели:

1. В r-ом ярусе дерева, образованного относительно узла i, находим заданный конечный узел j.

2. Выписываем номера узлов, относительно которых образованы подмножества,

связанные с выбранным узлом j. Выписанные узлы принадлежат пути от узла i к узлу j.

 

Пример

В качестве примера построим дерево путей для узла 6 сети, представленной виде графа на рисунке 5.

 

 

Рис.5. Структура сети

 

Определим множество путей от узла 6 к другим узлам сети графическим мето-дом. Выписываем исходный узел 6, который относится к нулевому ярусу. По графу сети определяем смежные с узлом 6 узлы – 1, 2, 4 и 5, которые образуют узлы первого яруса. Для узла 1 выбираем узлы 2 и 6. Так как узел 1 связан с узлом 6 нулевого яруса, то во втором ярусе записываем только узел 2. Для узла 2 в под-множество узлов второго яруса попадают узлы 3 и 5. Для узла 4 в подмножество узлов второго яруса попадает узлы 3. Для узла 5 в подмножество узлов второго яруса попадает узел 4. Аналогичным образом определяются подмножество узлов

третьего и последующих ярусов. Узлы смежных ярусов связываются между собой

соответствуюшими ребрами графа сети с учетом исключения путей с повторяю-щимися узлами в этих путях.

На рисунке 7 приведено дерево путей для узла 6.

Используя данное дерево путей, запишем пути не более третьего ранга от

узла 6 до узла 5:

= ; = h; = h.

 

Рис.6. Дерево путей ранга r ≤ 3 для узла 6

 

Матричный метод основан на составлении структурной матрицы B, с последующим ее разложением. Матрица B – квадратная матрица, строки и столб-цы которой сопоставлены узлам сети. Связь внутри узла отображается единицей (1). Если связи между узлами нет, то вхождение матрицы равно нулю (0).

Значения матрицы B рассматриваются как элементы булевой алгебры с двумя значениями: 1- соединение есть, 0 – соединения нет. Поэтому матрицу B преобра-зуют как булеву матрицу, применяя к ней аппарат булевой алгебры. При этом будем использовать следующие основные правила и законы булевой алгебры.

1) ( b) = - закон поглащения;

2) 1 =1; 1 = ;

3) 0 = ; 0 = 0;

4) = 0; = 1;

5) = ; = - закон поглащения.

В дальнейшем знак логического умножения будем опускать. Знак логичес-кого сложения соответствует параллельному существованию путей в сети между узлами сети. Знак логического умножения будем рассматривать как после-довательное соединение элементов сети в том или ином пути.

Множество путей m_ij может быть найдено раскрытием минора структурной матрицы B, путем вычеркивания i-го столбца и j-ой строки в матрице В, и последующим разложением полученного определителя.

При вычислении определителей матриц учитываем следующее:

а) если в каждой строке (столбце) определителя есть хотя бы одна единица, то

определитель равен 1;

б) если в определителе строка (или столбец) состоит из одних нулей, то опреде-

литель равен нулю;

в) если строка (столбец) содержит одну единицу, а остальные нули, то ее (его)

можно вычеркнуть;

г) для определения номера строки на последующем шаге разложения определи-теля, необходимо выбрать любое ребро графа сети из строки определителя, соот-ветствующей рассматриваемому узлу на данном шаге разложения определителя. Номер строки на следующем шаге разложения определяется номером узла, с которым выбранное ранее ребро связывает рассматриваемый узел графа сети.

Рассмотрим пример определения путей в сети от узла i до узла j матричным методом.

 

Пример

Определим совокупность путей от узла 6 до узла 5 матричным методом, используя структуру сети представленную на рисунке 5.

Структурная матрица B для рассматриваемого примера имеет вид:

 

Узлы
						f
			b	0	h	g
				c
						k
						m

 

 

B=

 

Для определения множества путей m₆₅ из матрицы B вычеркнем столбец 6 и строку 5, поскольку узел 6 является исходящим, а узел 5 – входящим. Получаем

определитель, представленный на рис. 7а. Обращаемся к строке 6 определителя

(рис.7а), так как узел 6 является исходящим. Анализ строки 6 показывает, что узел 6 связан с узлами 1, 2, 4 и 5 соответственно ребрами , , и . Поэтому разложение определителя 7а осуществим по указанным ребрам ( , , и ). В полученных определителях (рис.7 б, в, г, д), обращаемся, соотвественно, к строке 1, строке 2 и строке 4. Определитель 7д равен 1, так как в каждой строке определителя имеется по одной единицы.

Далее проведем разложение определителей 7б, 7в и 7г по ненулевым членам соответственно 1-ой, 2-ой и 4 ой строкам. Определители 7ж, 7е равны нулю, так как в каждой строке и столбце указанных определителей имеются нули. Опреде-литель 7и равен единице, так как в каждой строке определителя имеется по одной единицы. Разложение определителей 7е и 7к осуществим соотетственно по ненулевым членам 2-ой строки и 3-ей строки. Получаем определители 8л и 8м. После разложения определителя 7л получаем 0, а после разложения определителя 7м получаем 1. Окончательно получим выражение:

m₆₅= h h h .

Таким образом, от узла 6 к узлу 5 могут быть использованы четыре простых пути:

= ; = h; = h; = h.

Следовательно, множество путей ранга не более 3-его (r ≤ 3) от узла 6 к узлу 5, полученных как графическим, так и матричным методами, совпадают.

Последовательность разложения структурной матрицы B при определении путей от узла 6 к узлу 5 представлена на рис. 7.

Узлы
			b	0	h
				c

 

m₆₅ =

=

 

а)

Узлы
		b		h
			c

Узлы
		b		h
			c

 

=

б) в)

Узлы
			b	h

Узлы
			b
				c

 

=

 

 

г) д)

Узлы
	b		h
		c

Узлы
		c

=

 

 

е) ж)

 

Узлы
			c

 

Узлы
		c

b h

 

з) и)

 

Узлы
			h

Узлы
	c

= b

 

 

к) л)

Узлы
		c

h h =

 

м)

= h h h .

 

Рис.7. Определение путей от узла 6 до узла 5 матричным методом.

 

Для нахождения сечений (квазисечений, т.е. сечения, рассекающие пути до определенного ранга), следует заменить функцию m_ij на двойственную, заменив

операции логического сложения (коньюнкции) на операции логического умноже-ния (дизъюнкции) и наоборот. Затем произвести упрощение полученного выраже-ния. Каждое слагаемое данного выражения и будет искомое сечение.

 

Пример

Определим множество квазисечений для множества путей r ≤ 3 от узла 6 до узла5. Из рассмотренного выше примера имеем:

 

m₆₅= h h.

 

Заменим функцию m₆₅ на двойственную S₆₅ и, произведя операции умножения и сложения, получим слагаемые, определяющие квазисечения между узлами 6 и5.

S₆₅ = ( )( h)( h) = ( h)( h) =

= h h h h.

Удаление ребер из графа сети, входящих в любое из полученных слагаемых, делает сеть несвязанной по отношению к узлам 6 и 5 при использовании путей ранга не более трех.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: