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

Графовая форма

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

Наш граф является неориентированным, т.к. направление дуг не указано, тогда неориентированные дуги называют ребрами. Также наш граф взвешенный, т.к. каждой дуге присвоены веса. Взвешенный граф принято называть сетью.

Приведем модель нашего графа, по индивидуальному варианту:

 

 

Рисунок 2.1 Граф построенный по индивидуальному заданию

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

Матрица смежности представляет собой матрицу A=[aij], размером (nxn) элементов, которые могут принимать значения:

аij – 1, если в графе G существует дуга между вершинами i и j;

аij – 0, - в противном случае.

Матрица смежностей графа представленного на рисунке 2.1 имеет вид:

 

 

 

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

 

Матрица весов

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

При отсутствии связи, в пустых ячейках можно записать знак бесконечности (∞), что соответствует о бесконечно большом расстоянии и невозможности установить связь.

Приведем матрицу весов для графа, отображенного на рисунке 2.1.

 

			∞			∞			∞	∞
					∞	∞	∞	∞	∞	∞
	∞			∞	∞			∞	∞	∞
			∞		∞		∞	∞	∞	∞
		∞	∞	∞			∞		∞	∞
	∞	∞								∞
		∞		∞	∞			∞	∞
		∞	∞	∞			∞
	∞	∞	∞	∞	∞		∞
	∞	∞	∞	∞	∞	∞

 

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

Для построения данной матрицы необходимо произвольным образом пронумеровать связи заданные индивидуальным заданием, сделаем это:

 

Начало ветви

Конец ветви

Вес

Нумерация

 

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

 

 

 

Узел связанный с данным

 

Данная форма представления графа показывает связь каждого узла с остальными:

Узел	Существующие связи с другими узлами
	2, 4, 5, 7, 8
	1, 3, 4
	2, 6, 7
	1, 2, 6
	1, 6, 8
	3, 4, 5, 7, 8, 9
	1, 3, 6, 10
	1, 5, 6, 9, 10
	6, 8, 10
	7, 8, 9

 

Контрольные вопросы

2.6.1 Какие задачи относятся к классу задач синтеза и какие – к классу анализа?

 

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

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

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

2.6.3

Для модельного представления сетей связи наиболее часто используются графовые модели. На основе модели объекта и ее параметров (количества пунктов и линий сети, расстояние между пунктами, пропускной способности узлов и линий сети, стоимостных параметров и т.п.) можно построить математическую модель, отражающую реальную зависимость между искомыми параметрами и независимыми переменными задачи в виде математических функций.

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

2.6.5

Формы модельного анализа бывают разных видов, для улучшенного восприятия. Графовая модель – графическое отображение модельного представления телекоммуникационной сети. Также существуют дискретные формы представления, где существующие связи характеризуются двоичным кодом (если связь присутствует – 1, если нет – 0). Данная форма представления является оптимальной для обработки информации компьютерными системами. Подробное описание дискретных способов представление было приведено выше. Когда собственно они и использовались.

 

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

 

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

 

2.6.7 Что отражает отношение смежности и инцидентности элементов графа?

 

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

 

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

 

Возможность обработать информацию в реальном времени, до того как приступить к проектированию.

 

3. Синтез сети абонентского доступа

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

 

Для решения поставленной задачи существует ряд эффективных алгоритмов. В данном случае мы будем использовать алгоритм Прима для синтеза сети минимальной стоимости.

Шаг №1. Выбираем ребро с наименьшим весом. В данном случае это ребро соединяющее узлы 3 и 7, оно имеет вес – 3.

 

Шаг №2. Отыскиваем ребро с минимальным весом, вершина которого принадлежит вершине 3 ил 7. В нашем случае это вершина 2 соединяемая с вершиной 3 ребром вес которого 7.

 

Шаг №3. По аналогии – вершина 2 соединяется с вершиной 4 ребром вес которого 9.

 

 

 

 

Шаг №4. По аналогии – вершина 2 соединяется с вершиной 1 ребро вес которого 10.

 

 

 

 

Шаг №5. По аналогии – вершина 3 соединяется с вершиной 6 вес ребра 14.

 

 

Шаг №6. Из 6-го узла ребро с наименьшим весом является ребро с весом 9 соединяющее 6-й и 8-й узлы.

 

 

Шаг №7. Из 8-го узла ребро с наименьшим весом является ребро с весом 18 соединяющее 8-й и 5-й узлы.

 

 

 

Шаг №8. Из 8-го узла ребро с наименьшим весом является ребро с весом 18 соединяющее 8-й и 9-й узлы.

 

 

 

Шаг №9. В данном случае ребро, с весом 19 которое связывает 9-й и 10-й вершины является завершающим.

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

Рисунок 3.1 Кабельная сеть минимального доступа с минимальными затратами на линейные сооружения.

 

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

Суммарное расстояние = 3+7+9+10+14+18+9+18+19= 107 км.

Стоимость = 109 * 10 = 1070 у.е.