Приводимый (параллельно-последовательный) граф
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Ордена Трудового Красного Знамени федеральное государственное образовательное бюджетное учреждение высшего образования
Московский технический университет связи и информатики
(МТУСИ)
Кафедра Сетей связи и систем коммутации
Сборник методических указаний
Для проведения лабораторно-практических занятий по дисциплине
СЕТИ СВЯЗИ
Москва, 2012
План УМД на 2010/2011 уч. год
Сборник методических указаний
для проведения лабораторно-практических занятий по дисциплине
СЕТИ СВЯЗИ
Составитель: А.П.Пшеничников, канд. техн. наук, профессор
Издание утверждено Советом факультета С и СС. Протокол № 9
от 24.05.2011г.
Рецензент Ц. Ц. Михайлова, канд. техн. наук, доцент
Тема 1
Структурные матрицы сетей и операции с ними
Цель работы
Изучить и практически освоить описание структурных параметров сетей связи с использованием математического аппарата булевой алгебры. Путем преобразования структурных матриц получить перечень путей, сечений и квазисечений.
Задание
2.1. Ознакомиться по [1] с основными определениями структурного анализа сетей связи: граф сети, путь, ранг пути, способы записи путей, сечение, квазисечение, правила булевой алгебры.
2.2. Изучить методы получения множества путей и сечений из структурной матрицы.
|
|
|
2.3. Получить задание у преподавателя. Варианты заданий приведены на рис. 1.4, 1.5 и в таблицах 1.1, 1.2.
2.4. Согласно полученному варианту задания провести анализ сети:
· записать структурную матрицу сети;
· визуально по схеме графа найти и записать все возможные пути от узла i к узлу j; номера узлов i и j взять из таблиц 1.1 и 1.2 в соответствии с номером варианта задания;
· определить пути ранга r£ 3 для заданной пары узлов;
· путем преобразования структурной матрицы найти и записать все пути от узла i к узлу j и все пути ранга r £ 3;
· по структурной матрице построить дерево путей с корнем в узле i ранга r £ 3 для связи с узлом j и сравнить полученный результат с результатами, полученными при выполнении предыдущих пунктов;
· используя аппарат булевой алгебры, найти квазисечения между узлами i и j для множества путей с рангом r£ 3.
Теоретическая часть
Структура сети (ее топология) - это совокупность связей между элементами сети, отражающая их взаимодействие.
Для изучения структурных свойств сети ее представляют в виде графа G ={ A , B } .
Граф задается множеством вершин А = { a 1 , a 2 ,…, ai ,…, an } и множеством ребер В = { bij }, соединяющих вершины графа, i , j =1,n , где n – число вершин графа.
|
|
|
Таким образом, станциям и узлам сети ставятся в соответствие вершины, а линиям передачи – рёбра. Ребру может быть приписан вес или совокупность весов, характеризующих его свойства, например, длина в километрах, пропускная способность в числе каналов и т.п. Так как каналы могут быть одностороннего и двустороннего занятия, то и соответствующие им ребра будут направленными (ориентированными) и ненаправленными (неориентированными).
На рис. 1.1 приведены примеры ориентированных и неориентированных графов.
а) неориентированный граф б) ориентированный граф в) смешанный граф
Рис. 1.1. Ориентированные и неориентированные графы
Если две вершины графа соединены ребром, то они называются смежными. При этом вершины а1 и а2 называются инцидентными этому ребру, а ребро – инцидентным этим вершинам. Аналогично два разных ребра называются смежными, если они имеют общую вершину. Число ребер, инцидентных данной вершине, называются рангом (степенью) вершины. Вершина ранга 1 называется оконечной (тупиковой, висячей). Вершина ранга 0 называется изолированной.
Путь m st из вершины а s в вершину а t- это упорядоченная последовательность ребер, начинающаяся в а s , заканчивающаяся в а tи не проходящая дважды через одну и ту же вершину, причем в промежуточной вершине конец предыдущего ребра совпадает с началом последующего (условие непрерывности каналов в сети). Обычно путь записывается перечнем ребер, образующих этот путь m k st = b sl b lm …, b qt, где k –порядковый номер пути.
|
|
|
Рангом пути r ( m st ) называют число ребер, образующих этот путь. Минимальный ранг пути равен 1, максимальный – n-1, когда путь проходит через все вершины, где n – число вершин графа.
Все пути от а s к а t образуют множество путей mst, а совокупность двух множеств, соответствующих противоположным направлениям, - множество всех путей между а s и аtM st = mst È mts . Для ненаправленных графов
М st = mst = mts .
Связным называется такой граф, любые две вершины которого связаны хотя бы одним путем. Граф называется h – связным, если любые две вершины связаны независимыми путями, число которых не менее h. Независимыми называются такие пути, которые не включают одни и те же ребра (независимые по ребрам) или одни и те же вершины (независимые по вершинам). Часто понятие связности относят к заданным вершинам а s и а t (hst - связность).
|
|
|
Сечением s графа называется совокупность ребер, которые надо изъять, чтобы нарушилась его связность. Сечением s st по отношению к вершинам а s и а t называются такие сечения, при которых вершины а s и а t оказываются в разных подграфах. Рангом сечения вершины i r ( s i ) называется число входящих в него ребер. Подграфом графа G = { A , B } называют граф, все вершины которого принадлежат множеству А, а все ребра – множеству В.
Квазисечением называют сечение, рассекающее пути только до определенного ранга.
Проиллюстрируем приведенные определения на примере. Граф на рис. 1.2 содержит 5 вершин и 7 ребер. Ранг вершины (число ребер, опирающихся на данную вершину) для приведенного примера - не более трех.
Рис. 1.2. Сечения графа
|
|
|
|
|
|
| |
| |
|
Пользуясь этими обозначениями, запишем все пути от вершины 1 к вершине 4:
|
m 1 1,4 = abc = m 1 1,2,3,4 ; m 2 1,4 = ed = m 2 1,5,4 ;
|
m 3 1,4 = h = m 3 1,4 ; m 4 1,4 = agd = m 4 1,2,5,4 .
|
|
m14 = { abc È ed È h È agd }. (1.1)
|
mr £ 2 14 = { ed È h }. (1.2)
На рис. 1.2 приведены три различных сечения I , II , III:
|
|
s I = { aeh }; s II = { chd }; s III = { bhd }.
Для анализа сети, т.е. нахождения путей и сечений, используют структурную матрицу В. В – квадратная матрица, строки и столбцы которой сопоставлены с вершинами сети. Связь внутри вершины (для i = j) отображается единицей. Если связи между вершинами нет, то элемент матрицы равен 0. Для сети рис. 1.2 имеем:
|
B = | 1 | 2 | 3 | 4 | 5 | |
| 1 | 1 | a | 0 | h | e | |
| 2 |  a
| 1 | b | 0 | g | |
| 3 | 0 |  b
| 1 | c | 0 | |
| 4 | 0 | 0 |  c
| 1 | d | |
| 5 | e
| 0 | 0 |  d
| 1 |
Таким образом, элементы матрицы:
0, если связи между вершинами нет;
1 , если i = j;
|
bij , если связь между вершинами есть и i > j .
Элементы матрицы могут рассматриваться как булевы переменные с двумя значениями: 1 – соединение есть, 0 – соединение отсутствует. Поэтому матрицу В преобразуют как булеву, применяя к ней аппарат булевой алгебры, используя три операции: логическое произведение (конъюнкция), которое обозначается точкой (при записи обычно опускается), логическое сложение (дизъюнкция), для которой применяется символ È, инверсия (черта над переменной или функцией).
В булевой алгебре 1 È 1 = 1, а отсюда следуют следующие преобразования (правила):
Правила булевой алгебры:
1. a È ab = a ; a ( a È b ) = a - правило поглощения;
2 . 1 È a = 1; 1a = a;
3. 0 È a = a; 0a = 0;
|
|
5 . a = a.
Законы булевой алгебры:
1. Переместительный (коммутативный)
a È b = b È a ; ab = ba .
2. Сочетательный (ассоциативный)
a È (b È c) = (a È b) È c; a (bc) = (ab) c.
3. Распределительный (дистрибутивный)
a È ( b c ) = ( a È b ) ( a È c ).
4. Закон повторения (тавтологии)
a È a È … È a = a; aa…a = a.
5.
|
|
|
|
|
|
Закон инверсии (отрицания)
a È b È … È d = a b … d; ab…d = a È b È … È d .
6.
|
|
|
|
= 1; aa = 0.
При вычислении определителей (детерминантов - det) матриц учитывается следующее:
· если в det поменять местами две строки (столбца) или транспонировать его, то его значение не изменится;
· если в каждой строке (столбце) det есть хотя бы одна 1, то det = 1;
· если в det строка (или столбец) состоит из одних нулей, то det = 0;
· если строка (столбец) в det содержит один элемент с единицей, а остальные – нули, то ее (его) можно вычеркнуть.
Множество путей mij проще всего может быть найдено раскрытием минора структурной матрицы В, получаемого путем вычеркивания i–го столбца и j–ой строки в матрице В, и последующим разложением полученного определителя по строке. Например, пусть требуется найти множество путей m 14 в примере рис. 1.2. Процесс раскрытия полученного определителя проведем по ненулевым членам 1-ой строки и далее продолжим процесс:
| → | a | 0 | h | e | |||||||||||||||||||||
| 1 |
| 0 | g | → | b | 0 | g |
| 1 | b | g |
| 1 | b | 0 | |||||||||
| m 14 = | b |
| c | 0 | = a |
| c | 0 | È h | b | 1 | 0 | È e | b |
| c | = | ||||||||
| 0 | 0 | d | 1 | 0 | d | 1 | 0 | 0 | 1 | 0 | 0 | d | |||||||||||||
|
| ||||||||||||||||||||||||
| → | c | 0 | → |
| c | → |
| c | → |
| c | ||||||||||||||
| = a b | d | 1 | È | ag | 0 | d | È | h | È e |
| d | È | e b | 0 | d | = | |||||||||
|
|
| |||||||||||||||||||||||
| = a b c | È | ag | d | È | h | È | e | d . | (1.3) | ||||||||||||||||
|
Графический эквивалент перечня путей – дерево путей – можно построить непосредственно по матрице В. Для построения дерева путей из вершины 1 берем первую строку матрицы В и помечаем на графе вершины путей с r =1, имеющие bij ¹ 0. После того, как процесс для строки закончен и отмечены номера вершин (по номеру столбца), переходим к строке одного из тех узлов, которые расположены на линии r = 1, и продолжаем процесс аналогичным образом. При этом следует учитывать, что вершины в одном пути не должны повторяться. Дерево путей для вершины 1 показано на рис. 1.3.
Для нахождения сечений (или квазисечений, т.е. сечений, рассекающих пути только до определенного ранга) следует заменить функцию m 14 на двойственную, заменив дизъюнкцию конъюнкцией и, наоборот, – конъюнкцию дизъюнкцией.
При перемножении булевых многочленов удобно пользоваться формулой ( a È x )( a È y ) = a Èx y. Затем провести упрощение и привести выражение к дизъюнктивной нормальной форме путем исключения лишних членов, пользуясь формулой a È ab = a. Каждое слагаемое и есть искомое сечение.
Рис. 1.3. Дерево путей для вершины 1
|
|
|
|
|
|
|
|
|
|
|
|
È b g h e È c g h e È d b h È d c h. (1.4)
4. Варианты заданий (рис. 1.4, рис. 1.5)
Рис. 1.4. Граф для вариантов 1-10 Рис. 1.5. Граф для вариантов 11-20
Таблица 1.1 (к рис.1.4)
| № вар. № узла | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| i | 1 | 2 | 1 | 2 | 1 | 4 | 4 | 6 | 6 | 6 |
| j | 2 | 1 | 3 | 6 | 6 | 2 | 6 | 1 | 4 | 2 |
Таблица 1.2 (к рис. 1.5)
| № вар. № узла | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| i | 1 | 2 | 2 | 6 | 5 | 1 | 7 | 1 | 7 | 6 |
| j | 2 | 1 | 3 | 1 | 4 | 6 | 5 | 7 | 4 | 4 |
Содержание отчета
1. Вариант задания: граф сети и исходные данные из таблицы для своего варианта.
2. Структурная матрица сети.
3. Множество всех путей из вершины iв вершину jи путей ранга r £ 3.
4. Преобразования структурной матрицы для нахождения множества путей.
5. Дерево путей.
6. Преобразования структурной матрицы, необходимые для нахождения квазисечений для заданной пары узлов.
Литература
1. Теория сетей связи./ Под ред. В.Н. Рогинского. – М.: Радио и связь, 1981. – 192 с.
Тема 2.
Структурная надежность сетей связи
Цель работы
Изучить и практически освоить методы расчета структурной надежности сетей связи.
Задание
1. Ознакомиться с основными показателями надежности сетей связи и методами расчета структурной надежности.
2. Рассчитать структурную надежность сети между заданной парой узлов при условии, что вероятности безотказной работы ребер сети одинаковы и равны 0,9.
Теоретическая часть
Основные определения
Надежностью называется свойство системы связи выполнять свои функции в заданных условиях эксплуатации. Нарушение работоспособности системы называется отказом. Живучесть системы связи характеризует ее устойчивость против действия причин, лежащих вне системы и приводящих к значительным повреждениям некоторой части ее элементов. Причины могут быть стихийные и преднамеренные.
Основные показатели надежности системы связи:
ТО - наработка системы на отказ – математическое ожидание случайной величины промежутка времени между двумя отказами;
ТВ - среднее время восстановления работоспособности системы;
КГ = ТО / (ТО+ ТВ) - коэффициент готовности системы – вероятность того, что в стационарном процессе эксплуатации в произвольный момент времени система окажется работоспособной.
Для телефонной сети общего пользования и неприоритетных абонентов между любыми двумя оконечными телефонными станциями обычно принимают КГ ³ 0,9.
Различают аппаратную надежность и структурную надежность сети. Последняя зависит не только от надежности линий и узлов, но и схемы их соединения между собой.
Структурной надежностью графа при связи от вершины s к вершине t называется вероятность исправного состояния хотя бы одного пути из заданного множества путей mst.
Имея множество путей или сечений (квазисечений), можно найти структурную надежность сети связи.
Будем считать, что узлы абсолютно надежны. Под надежностью ребра ijпонимается вероятность его безотказной работы (коэффициент готовности). Надежность k-го пути m k st оценивается вероятностью работоспособного состояния всех ребер, образующих этот путь.
Последовательный граф
Пусть путь состоит из n последовательно соединенных ребер (рис. 2.1).
 |
Рис. 2.1. Последовательный граф (путь)
Пронумеруем эти ребра от 1 доn. Обозначим коэффициент готовности i-го ребра, i =1, n, через r i . Тогда коэффициент готовности пути m s t
n
pst= П r i. (2.1)
i =1
Параллельный граф
|
 |
Рис. 2.2. Параллельный граф
Коэффициент готовности графа при связи от вершины s к вершине t в этом случае рассчитывается по формуле
n
Р st = 1 – П ( 1 – r i ) . (2.2)
i =1
Приводимый (параллельно-последовательный) граф
Приводимым называется граф, структура которого может быть представлена в виде комбинаций последовательных и параллельных соединений (рис. 2.3).
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 2.3. Приводимый (параллельно-последовательный) граф
Коэффициент готовности графа при связи от вершины s к вершине t рассчитывается в следующей последовательности:
1) Параллельные ребра с коэффициентами готовности r 2 и r 3 заменяются эквивалентным ребром с коэффициентом готовности:
Р12 = 1 – (1 - r 2 ) (1 - r 3 ).
При этом граф рис. 2.3 преобразуется в граф рис. 2.4.
 |
Рис. 2.4. Граф после первой процедуры свертки
2) Последовательные ребра 12 , 2 t и 13 , 3 t заменяются эквивалентными ребрами с коэффициентами готовности:
Р12 t = P 12 r 4 и Р13t = r 6 r 7 .
При этом граф рис. 2.4 преобразуется в граф рис. 2.5.
 |
Рис. 2.5. Граф после второй процедуры свертки
3) Параллельные ребра с коэффициентами готовности Р12 t , r 5 и Р13 tзаменяются эквивалентным ребром с коэффициентом готовности:
Р1 t = 1 – (1 - Р12 t ) (1 - r 5 ) (1 - Р13 t ).
При этом граф рис. 2.5 преобразуется в граф рис. 2.6.
|
|
|
|
|
 |
Рис. 2.6. Граф после третьей процедуры свертки
4) Последовательные ребра с коэффициентами готовности r 1 и Р1 t заменяются эквивалентным ребром с коэффициентом готовности
Р st = r 1 Р1t .
Это и есть искомый коэффициент готовности.
Дата добавления: 2019-03-09; просмотров: 513; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!