1. Построение моделей телекоммуникационной сети.

1.1.Исходные данные, согласно варианту 01, приведены в таб. 1. 1 в которой первая и вторая строка содержат номера пунктов, соединенных линиями связи, а в третей строке содержатся весовые характеристики этих линий

Н.В.	1	1	1	1	1	2	2	3	3	4	5	5	6	6	6	7	8	8	9
К.В.	2	4	5	7	8	3	4	6	7	6	6	8	7	8	9	10	9	10	10
Вес	15	20	25	6	43	95	30	12	10	35	71	63	50	18	48	21	90	15	10

Таблица 1.1 – Исходные данные.

Исходная телекоммуникационная сеть содержит 10 пунктов и 19 линий, которые обеспечивают связь между пунктами в обоих направлениях.

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

а) Графовая модель.

Рисунок 1.1 – Графовая модель представления телекоммуникационной сети.

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

Один из наиболее распространенных дискретных представлений графа является матрица смежности. Эта матрица А=[а_i,j], размером (nx n) элементов, которые могут принимать значения: а_i,j = 1, если в графе существует дуга между вершинамиiиj; а_i,j= 0, в противном случаи.

	1	2	3	4	5	6	7	8	9	10
1	0	1	0	1	1	0	1	1	0	0
2	1	0	1	1	0	0	0	0	0	0
3	0	1	0	0	0	1	1	0	0	0
4	1	1	0	0	0	1	0	0	0	0
5	1	0	0	0	0	1	0	1	0	0
6	0	0	1	1	1	0	1	1	1	0
7	1	0	1	0	0	1	0	0	0	1
8	1	0	0	0	1	1	0	0	1	1
9	0	0	0	0	0	1	0	1	0	1
10	0	0	0	0	0	0	1	1	1	0

Таблица 1.2 – Матрица смежности.

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

Матрица инцидентности – это матрица отображающая отношение инцидентности ребер и вершин графа. Между вершинами и соединенными с ней дугами существует инцидентность. Эта матрица B_i,jмогут принимать значения (0,1).

	1	2	3	4	5	6	7	8	9	10
1 – 2	1	1	0	0	0	0	0	0	0	0
1 – 4	1	0	0	1	0	0	0	0	0	0
1 – 5	1	0	0	0	1	0	0	0	0	0
1 – 7	1	0	0	0	0	0	1	0	0	0
1 – 8	1	0	0	0	0	0	0	1	0	0
2 – 3	0	1	1	0	0	0	0	0	0	0
2 – 4	0	1	0	1	0	0	0	0	0	0
3 – 6	0	0	1	0	0	1	0	0	0	0
3 – 7	0	0	1	0	0	0	1	0	0	0
4 – 6	0	0	0	1	0	1	0	0	0	0
5 – 6	0	0	0	0	1	1	0	0	0	0
5 – 8	0	0	0	0	1	0	0	1	0	0
6 – 7	0	0	0	0	0	1	1	0	0	0
6 – 8	0	0	0	0	0	1	0	1	0	0
6 – 9	0	0	0	0	0	1	0	0	1	0
7 – 10	0	0	0	0	0	0	1	0	0	1
8 – 9	0	0	0	0	0	0	0	1	1	0
8 – 10	0	0	0	0	0	0	0	1	0	1
9 – 10	0	0	0	0	0	0	0	0	1	1

Таблица 1.3 – Матрица инцидентности

г) Матрица весов.

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

	1	2	3	4	5	6	7	8	9	10
1	∞	15	∞	20	25	∞	6	43	∞	∞
2	15	∞	95	30	∞	∞	∞	∞	∞	∞
3	∞	95	∞	∞	∞	12	10	∞	∞	∞
4	20	30	∞	∞	∞	35	∞	∞	∞	∞
5	25	∞	∞	∞	∞	71	∞	63	∞	∞
6	∞	∞	12	35	71	∞	50	18	48	∞
7	6	∞	10	∞	∞	50	∞	∞	∞	21
8	43	∞	∞	∞	63	18	∞	∞	90	15
9	∞	∞	∞	∞	∞	48	∞	90	∞	10
10	∞	∞	∞	∞	∞	∞	21	15	10	∞

Таблица 1.4 – Матрица весов.

г) Список дуг (ребер)

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

R₁ = (1,1,1,1,1,2,2,3,3,4,5,5,6,6,6,7,8,8,9)

R₂ = (2,4,5,7,8,3,4,6,7,6,6,8,7,9,10,9,10,10)

е) Структура смежностей.

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

1: 2,4,5,7,85: 1,6,89: 6,8,10

2: 1,3,46: 3,4,5,7,8,910: 7,8,9

3: 2,6,77: 1,3,6,10

4: 1,2,68: 1,5,6,9,10

Дать письменный ответ на следующие ключевые вопросы:

1. Какие задачи принадлежат к классу задач синтеза, и какие – к классу анализа?

2. Для чего используют модельное представление сети?

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

4. Что называют графом? Ориентированным графом? Не ориентированным графом?

5. В чем состоит отличительная особенность сетевой модели?

Ответы:

1. Задача синтеза состоит в виде оптимальной топологии сети, оптимального количества и места расположения узлов коммутации.

Задача анализа состоит в нахождении оптимальных путей передачи информации, определение совокупности путей заданной транзитивности, оценки пропускной способностью сети, вероятность установления соединения между узлами и т.д. Также к задаче анализа относится расчет характеристики параметров сети в целом, а также отдельных ее элементов (пропускной способности, качества обслуживания и т.п.).

2. Модельное представление сети используется для того, чтобы выявлять и обнаруживать наиболее существенные элементы и связи между ними, не отвлекаясь от деталей. Основное представление – граф.

3. В качестве математической модели телекоммуникационной сети используется граф. Граф может изображаться в геометрическом (точки соединения ребрами) и дискретном (матрицы) видах.

4. Графом называется некоторая совокупность точек и связывающих ребер. Граф в котором задается направление дуг, называется ориентированным. В противном случаи – неориентированным.

5. Отношение смежности отражает вершины соединенные между собой ребром. Отношение инцидентности отражает связь между вершиной и соединенным с ней ребром.

6. Отличительной чертой сетевой модели является то, что каждой дуге (ребру) графа поставлено в соответствие некоторое числовое значение, называемое весом. Такой граф называется взвешенным. При необходимости веса могут быть приписаны также вершинам графа. Весовые характеристики могут выступать расстояния, пропускная способность, стоимость и т.д.