Формализация описания структуры асу (графическое, матричное и множественное представление)

18. 
    Формализация описания структуры АСУ (графическое, матричное и множественное представление).
    

Принцип представления структуры в виде графа чрезвычайно прост. Чаще всего элементам системы ставят в соответствие вер­шины графа, а связям — ребра.

Это наиболее наглядный способ представления отношений между элементами, его недостаток — относительная сложность использования ЭВМ для анализа.

Матрица смежности вершин для неориентированного графа имеет вид: ,

где п — число вершин графа,

Для ориентированного графа матрица смежности задается следующим образом: ,

Матрица инциденций: ,

где п — число вершин, т — число ребер, определяется следую­щим образом:

Для неориентированного графа:

Для ориентированного графа:

В этом случае для ориентированного графа G(V) задается множество вершин К и соответствие G, которое показывает, как свя­заны между собой вершины. Для каждой вершины I соответствие G определяет множество вершин G(i), в которые можно непос­редственно попасть из вершины _i. Это множество называется множеством правых инциденций.

Множество определяет все вершины, из которых можно

непосредственно попасть в вершину _i. Это множество называется множеством левых инциденций.

Ориентированный граф задается перечисле­нием (списком) множеств вида G(i), либо множеств вида для всех вершин графа. Такой способ оказывается наиболее компак­тным и эффективным при задании исходной информации о структуре для решения задач синтеза, особенно для иерархичес­ких структур.

Степень вершины. Число ребер, инцидентных вершине / не­ориентированного графа, называют степенью вершиныи обозна­чают p(i)_.

Число дуг ориентированного графа, которые имеют началь­ной вершиной вершину i, называют полустепенью исхода вершиныи обозначают через . Аналогично, число дуг, которые имеют своей конечной вершиной вершину, называют полусте­пенью захода вершины j и обозначают через

любых вершин графа i и j существует цепь из вершины i в вер­шину j.

Для ориентированных графов вводится дополнительное по­нятие сильной связности. Граф G(V) называется сильно связным, если для любых вершин графа i,j существует путь из вершины i в вершину j.

Порядковая функция на графе

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

• 
  в подмножество нулевого уровня включаются все вер­шины _i для которых (иначе говоря, для которых не существует множества левых инциденций, или, еще про­ще, — вершины, в которые ниоткуда нельзя попасть). Про­водится последовательная нумерация этих вершин: 1, 2, …, i;
  
• 
  в подмножество первого уровня включаются все верши­ны i, для которых , т. е. для которых вершины уровня N_Q являются множеством левых инциденций. Про­водится последовательная нумерация этих вершин: i+1, i+2,…,i+r;
  
• 
  в подмножество второго уровня включаются все верши­ны i, для которых , Проводится последова­тельная нумерация вершин:
  

• 
  в подмножество третьего уровня включаются все вер­шины i, для которых . Проводится последовательная нумерация вершин и т. д.