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



жүктеу 31.2 Kb.
Дата21.07.2016
өлшемі31.2 Kb.

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

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



Способы формализованного задания графа

А. Графическое представление.

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



Б. Матричное представление.

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

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

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



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

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

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



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





В. Множественное представление.

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

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

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

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

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

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



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

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

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

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

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



Алгоритм упорядочения сводится к следующему:

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

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

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

i+r+1, i+r+2,…,i+r+p;

Данный процесс повторяется до тех пор, пока не будут про­нумерованы все вершины графа.


©dereksiz.org 2016
әкімшілігінің қараңыз

    Басты бет