Модельное представление сети как объекта синтеза и анализа

Инфо-коммуникационная сеть как объект синтеза и анализа представляет собой совокупность пунктов сети и соединяющих их линий. В качестве математической модели такого объекта используют граф.

О п р е д е л е н и е. Графом называется некоторая совокупность точек и связывающих их стрелок.

Точки графа называются вершинами, а стрелки – дугами. Граф математически обозначается как G(N,V), где N - конечное множество вершин мощностью n, а V – конечное множество дуг мощностью m.

Вершины можно обозначить строчными буквами (i, j, k, l, s) либо цифрами (1, 2, 3, 4, 5), а дуги соответственно парами: {(i, j), (j, k), (k, l)... } либо {(1,2), (2,3), (3,4),... }, где первый индекс определяет начало, а второй – конец дуги (см.рис.5.1).

Рисунок 1. Графовая модель сети  

Граф, в котором задается направление дуг, называется ориентированным, в противном случае – неориентированным. Неориентированные дуги называются ребрами. Между двумя вершинами, соединенными дугой (ребром), существует отношение смежности (для ориентированного графа вершины i и j смежны, лишь если дуга начинается в i и направлена в j). Между вершиной и соединенными с ней дугами (ребрами) существует отношение инцидентности.

Граф, каждой дуге (ребру) которого поставлены в соответствие некоторые числовые характеристики, называемые весами, представляет собой взвешенный граф. При необходимости веса могут быть приписаны также вершинам графа. Взвешенный граф принято называть сетью (в данном случае имеется в виду сетевая модель, а не сама сеть как объект). В качестве весовых характеристик сети могут выступать расстояния, пропускная способность, стоимость и т. д. Помимо геометрического изображения в виде точек и линий, граф может быть представлен в дискретной форме. Именно эта форма используется при вводе графовой модели в ЭВМ.

Одним из наиболее распространенных дискретных представлений графа является матрица смежностей. Это матрица А= [ a_ij ], размером (n‘n) элементов, которые могут принимать значения:

а_ij = 1, если в графе G существует дуга (ребро) между вершинами i и j;

а_{i j} = 0, - в противном случае.

Матрица смежностей графа, приведенного на рис. 5.2, имеет вид:

A=	0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0

Рисунок 2. Матрица смежности

Для хранения в памяти ЭВМ матрицы смежности, как видим, необходимо n² ячеек.

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

Если перенумеровать в произвольном порядке дуги (ребра) графа G и поставить эти номера в соответствие номерам строк некоторой матрицы В= [ b_ij ], а номера столбцов оставить по-прежнему соответствующими номерам вершин графа, то в такой матрице можно отобразить отношение инцидентности элементов графа G. Элементы матрицы B_ij могут принимать значения {0, 1}.

Перенумеруем дуги для рассматриваемого графа: (i, j) - 1; (j,k) - 2; (k,l) - 3; (l,s) - 4; (s,i) - 5; (s,j) – 6; (s,k) - 7. Тогда матрица инцидентности будет иметь вид:

B =	1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1

Рисунок 3. Матрица инцидентности

Взвешенный граф (сеть) может быть в дискретном виде представлен матрицей весов W= [ w_ij ], где w_ij – вес дуги (ребра), если она существует в графе G. Веса несуществующих дуг (ребер) полагают равными ђ или 0 в зависимости от условий задачи, в которой они рассматриваются.

Если граф является разреженным (имеет малое количество дуг (ребер)), то возможно более компактное представление графа G – списком дуг (ребер). Этот список может быть реализован двумя одномерными массивами размерностью m, в первом из которых записаны начальные вершины дуг (ребер), а во втором – конечные, либо двумерным массивом, размерностью (2, m).

Например,

R₁ = (1, 3, 4, 5, 5, 2, 5)

R₂ = (2, 2, 3, 4, 1, 5, 3)

R =

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

1: 2 4: 3

2: 5 5: 1, 2, 3, 4

3: 2

Дата добавления: 2014-01-07