Читайте также:
|
|
Формулировка задачи
Разработать формализованное представление структуры, изображенной на рис. 1.
Структуру отобразить рассмотренными способами. Выделить пути, циклы, контуры, степени вершин, полустепени исходов и заходов.
Рисунок 1. Структура системы управления
Способы формализованного задания графа.
Принцип представления структуры в виде графа чрезвычайно прост. Чаще всего элементам системы ставят в соответствие вершины графа, а связям — ребра.
Рассмотрим некоторые основные определения, непосредственно связанные с задачами структурного анализа АСУ.
А. Графическое представление.
Это наиболее наглядный способ представления отношений между элементами, его недостаток — относительная сложность использования ЭВМ для анализа.
Для рисунка 1 графическое представление системы имеет вид:
Б. Матричное представление.
Для ориентированного графа матрица смежности
задается следующим образом:
Для рисунка 1 матрица смежности имеет вид, представленный на таблице 1.
Таблица 1. Матрица смежности
вершины вершины | |||||
Матрица инцидентности:
где n – число вершин;
m – число ребер, определяется следующим образом:
Для ориентированного графа:
Матрица инцидентности для рисунка 1 имеет вид представленный в таблице 2:
Таблица 2. Матрица инцидентности
ребра вершины | |||||||
-1 | |||||||
-1 | -1 | -1 | |||||
-1 | |||||||
-1 | |||||||
-1 |
В. Множественное представление.
В этом случае для ориентированного графа G(V) задается множество вершин V и соответствие G, которое показывает, как связаны между собой вершины. Для каждой вершины i соответствие G определяет множество вершин G(i), в которые можно непосредственно попасть из вершины i. Это множество называется множеством правых инциденций.
Множество G-1(i) определяет все вершины, из которых можно непосредственно попасть в вершину i. Это множество называется множеством левых инциденций.
Таким образом, ориентированный граф задается перечислением (списком) множеств вида G(i), либо множеств вида G-1(i) для всех вершин графа. Такой способ оказывается наиболее компактным и эффективным при задании исходной информации о структуре для решения задач синтеза, особенно для иерархических структур.
Для рисунка 1 множественное задание структуры:
G(l) = (2,3), G(2) = 0, G(3) = (5,4), G(4) = (2), G(5) = (1,2).
G-1(1) = (5), G-1(2) = (1, 5, 4), G-1(3) = (1), G-1(4) = (3), G-1(5) = (3).
Г. Определение пути, контура.
Путем называется такая последовательность дуг, когда конец каждой предыдущей дуги совпадает с началом последующей. Например, для графа рисунка 1 последовательность дуг (1, 3), (3, 4), (4, 2) является путем. Понятие пути обычно используется для ориентированных графов.
Контуром называется такой конечный путь, у которого начальная вершина первой дуги совпадает с конечной вершиной последней i -ой дуги. Например, для графа на рисунке 1 последовательность дуг (1, 3), (3, 5), (5, 1) есть контур.
Длиной пути называют число дуг, входящих в путь графа.
Д. Определение полустепени исхода и захода.
Число дуг ориентированного графа, которые имеют начальной вершиной вершину i, называют полустепенью исхода вершины i и обозначают через р+(i). Аналогично, число дуг, которые имеют своей конечной вершиной вершину i, называют полустепенью захода вершины i и обозначают через р–(i). Для графа, представленного на рисунке 1:
Самостоятельно решить задачи представленные в вариантах. Построить граф системы, матрицу смежности, матрицу инцидентности. Определить пути, контуры, длины путей, полустепени исхода и полустепени захода вершин.
Дата добавления: 2014-12-15; просмотров: 115 | Поможем написать вашу работу | Нарушение авторских прав |