Степени вершин. Р-графы. Понятие связности.

Для неориентированного графа вводится понятие: локальная степень вершины X – число ребер инцидентных вершине x.

Обозначается:

Если четно, то вершина тоже и наоборот.

Граф называется однородным степени n, если локальная степень всех вершин для любого .

Для ориентированного графа: множество дуг, исходящих из вершины x_i записывается и называются локальной степенью вершины или полустепень исходящей вершины x_i.

Ориентированный граф называется однородным, если все локальные степени имеют одно и тоже значение:

, для любого

Если , то вершина x является изолированной.

Если , а , то эта вершина является входом.

Если , – вершина является выходом.

Неориентированный граф является связанным, если любые x_i, x_j можно соединить цепью, следовательно для ориентированного графа вводятся понятия сильно связанного графа.

Граф сильно связан, если любые x_i, x_j существуют из x_i в x_j.

 

23. Способы представления графов

1. Матрица смежности

Для неориентированного графа симметрична. Ее вид зависит от выбора алгебраической нумерации вершин. Для ориентированного их можно подобрать так, что матрица будет треугольной.

Свойства матрицы смежности для ориентированного графа:

1) каждый нулевой столбец соответствует источнику

2) каждая нулевая строка – строку

3) если все элементы главной диагонали равны 0, то в графе нет петель

4) появление единицы для любого x_i,_j. i=j соответствует петле

5) матрица не симметрична

2. Матрица инцидентности

В неориентированный

в ориентированный

Ребра должны быть пронумерованы!

3. Матрица изоморфности

В строках через запятую представлены номера входных дуг с плюсом и номера с выходом с минусом.

Пример:

 

 

Структурный анализ ИС. Уровни описания связей.

Структура – совокупность элементов системы и связей между ними.

Модель структуры системы должна отображать отношение элементов как между собой, так и с внешней средой. Система часто является многоуровневой:

Общее задание структуры анализа состоит в том, что исходя из заданного описания элементов системы и связей между ними получают некоторое представление о свойствах системы в целом и о свойствах ее подсистемы.

Уровни описания связей.

Различают 3 уровня описания связей между элементами в системе:

1)определяет наличие связей в системе

2)изучение направленности связей

3)изучение вида и направления сигналов, определяющих взаимодействие между элементами

С помощью графов

1. Неориентированные графы системы, где вершины – это элементы, ребра – связи между элементами. На этом этапе возникают следующие задачи:

a) определение целостности системы(связности).

Если система не связана, то выделение изолированных подсистем

Б) выделение циклов

В) определение минимальной и максимальной последовательности элементов, которые соответствует заданной задаче.

2. Ориентированный граф, где направление дуг соответствует направлению связей.

Основные задачи:

А) определение связности системы

Б) топологическая декомпозиция системы с выделением сильно связанных подсистем

В) перечисление входных и выходных полюсов, определение углов, приема выдачи информации

Г) определение уровней в структуре и определение их взаимосвязей

Д) определение минимальных и максимальных путей

Е) определение топологических характеристик значимости элементов

Ж) получение информации о слабых местах структуры

3. Раскрывается состав и характер сигналов взаимосвязей элементов между собой и с внешней средой.

 

 

25.Матричный алгоритм определения путей и контуров в структуре

Наиболее простой способ определения путей и контуров в системе – матрично-алгоритмический. Они строятся путем последовательного взаимодействия в степень матрицы смежности.

«1» в матрице смежности А говорит о наличии путей между i-той и j-той вершинами длины пути = 1. Если возвести матрицу А в квадрат, то наличие единиц в позиции i,j означает путь между этими вершинами длиной 2.

Элемент i,j определяет число путей длиной к от i к j. Таким образом можно определить вершины входящие в контур и его дину. Но для определения конкретного вида контура необходим дополнительный алгоритм.

«–» низкое быстродействие

«+» просто и наглядно

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

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