12.2 Элементы математического аппарата анализа и синтеза Графы, их свойства и способы представления

При решении задач анализа и синтеза сетей связи различных типов широко используется вспомогательный теоретический объект, называемый конечным графом. Рассмотрим некоторые важные для дальнейшего свойства графов и стандартные методы работы с ними. Конечным графом G принято называть конечный набор n узлов А={а₁.... ai,    , аn}, некоторые из которых попарно соединены ребрами {ветвями), образующими множество В. Любых два узла a_i,a_jєA,;i≠j могут быть соединены некоторым числом х≥0 ориентированных и неориентированных ребер, образующих пучок {a_ia_j}. Неориентированное ребро будет обозначаться через , ориентированное от a_i к a_j —символом ; символ (a_ia_j) без стрелки будет означать, что наличие или отсутствие ориентации несущественно. Граф называется простым (некратным) и обозначается PG, если для любых a_{i ,} a_j є A пучок {a_ia_j} содержит не более одного ребра каждого из трех возможных способов ориентации, и кратным, если это условие не выполняется. В частных случаях, когда все ребра графа ориентированы либо все ребра не имеют ориентации, граф называется, соответственно, ориентиро-ванным или неориентированным и обозначается символом или .В против-ном случае граф называется смешанным. Ориентированный граф называется симметрическим, если в нем каждому ребру сопутствует ребро встречной ориентации, и антисимметрическим, если ребра встречной ориентации отсутствуют. Ребра называются инцидентными узлу a_i, ребро - исходящим из a_i, a - входящим (заходящим) в a_j. Отсюда возникают следующие локальные конфигурационные характеристики графа, относящиеся к отдельному узлу a_i: число ребер, инцидентных узлу ai, называется его рангом (степенью), а числа ориентированных ветвей, исходящих из a_i и входящих в него, — соответственно полурангами (полустепенями) исхода и захода. Цепью, соединяющей узлы a_i и a_i, называется последовательность ветвей (a_i a_k), (a_ka_l)… (a_ra_j) не обязательно согласованной ориентации. Путем μ_ij из узла a_i в узел a_i  называется цепь, соединяющая a_i и a_j, в которой ориентация всех ориентированных ветвей соответствует направлению движения от a_i к a_j. Путь называется ациклическим (самонепересекающимся), если через любой узел сети он проходит не более одного раза. Будем говорить, что a_i и a_j связаны, если одновременно существуют пути из узла a_i  в узелa_j и из a_j в a_i. Граф или его компонент (подграф) называется связным, только если все его узлы попарно связаны, в противном случае имеет место несвязность. Сечением или разрезом графа (сети связи) называется минимальная совокупность ветвей (ребер), разделяющих граф (сеть) на две несвязные между собой части (под-

сети, подграфа). Под емкостью сечения понимается суммарная емкость входящих в

него ветвей (ребер). Сечение с минимальной емкостью называется минимальным сечением. Для определения минимального сечения используются методы исследования потоковых графов. Конфигурация простого неориентированного или ориентированного графа может быть представлена булевской матрицей размера n*n (n - число узлов графа), называемой матрицей смежности. Ее строки и столбцы соответствуют n узлам из множества A. В случае графа элемент этой матрицы β_ij принимает значение 1 только при наличии ребра  ; для графа при наличии ребра (а_iа_j) имеем

β _ij = β_ji =1. При отсутствии ребра (а_iа_j) - β_ij принимает значение 0. Иногда вершинам и ребрам графа G приписываются числа, называемые весом. В зависимости от решаемой задачи в качестве весов может использоваться: длина; стоимость; пропускная способность, выраженная числом каналов или допустимой скоростью передачи информации; пропускаемая нагрузка (например, в Эрлангах) при заданном качестве обслуживания; время задержки передаваемого сообщения и т.п. В ряде случаев в качестве весов могут быть использованы: вероятности потерь вызова, надежностные показатели (например, коэффициент готовности) и т.п. Если веса присваиваются только ребрам графа, то граф называется графом c взвешенным ребрами. Если веса присваиваются только вершинам, то граф называется графом с взвешенными вершинами. Если веса присваиваются и ребрам и вершинам, то граф называется просто взвешенным графом.

Для алгебраического представления графов удобно использовать следующие основные матрицы:

• Структурная матрица B графа G c n узлами. Это квадратурная матрица порядка n, в которой каждому узлу a_i соответствует i – ая строка и i- ый столбец: B = || b_ij ||. Вхождения b_ij определяются по следующему правилу:

1 при i = j

b_ij = b_ij в случае, если есть непосредственная связь от узла a_i к узлу a_j.

0, если такой непосредственной связи нет.

• Матрица длин ребер L = || l_ij ||, где l_ii = 0; l_ij – длина ребра от узла a_i до узла a_j; l_ij = ∞,если между a_i и a_j нет ребра.

• Матрица пропускных способностей элементов сети C = || c_ij ||. Под пропускной способностью будем понимать либо максимальное число бит, которое может быть пропущено каналами данного ребра в единицу времени, либо обслуженную нагрузку.

• Матрица прямых каналов U = || u_ij ||, вхождение которой u_ij – число каналов, начинающихся в узле a_i и кончающихся в узле a_j независимо от того, через какие еще транзитные или сетевые узлы эти каналы проходят. Такая матрица уже характеризует возможности сети по установлению связи, если считать, что узлы являются коммутационными.

• Матрица надежности P = || p_ij || , где p_ij – вероятность нахождения элемента сети в работоспособном состоянии.

• Матрица стоимостей Ц = || ц_ij ||, где ц_ij – стоимость ребра между узлами a_i и a_j, ц_ii – стоимость узла. В стоимость ребра может быть включена стоимость каналообразующей, а иногда и части коммутационной аппаратуры узлов a_i и a_j.

Используя характеристики ребер и вершин графа, можно получить соответствую-щие характеристики для отдельных путей. Для пути μ_st = {b_sl,b_lm, … ,b_pt} между вершиной s и t, содержащего ребра b_sl,b_lm, … и b_pt, в зависимости от поставленной задачи, могут быть получены различные параметры. Например:

- Ранг r (μ_st ) пути - число входящих в него ребер.

- Длина пути l (μ_st ) – сумма длин всех ребер, образующих данный путь.

l (μ_st ) = ∑ l_ij .

b _ij Є μ_st

- Пропускная способность пути c(μ_st) при использовании сети для передачи инфор-мации только от узла s к узлу t определяется наиболее узким местом – минимальной пропускной способностью ребер, образующих путь.

c( μ_st ) = min c(b_ij ).

b_ij Є μ_st

- Под пропускной способностью сечения понимается суммарная емкость входящих в него ребер.

Используя теорию графов можно решить множество весьма важных сетевых задач. К ним можно отнести:

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

• Определение самых коротких по длине или самых надежных путей между любыми узлами графа сети.

• Определение метрики графа (диаметра, медианы, радиуса), что может быть использовано при проектировании сетей связи.

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

• Решение задачи коммивояжера, что позволяет оптимизировать первичные сети кольцевой структуры.

• Определение максимальной пропускной способности некоммутируемых и коммутируемых сетей и т.п.