Определение пункта в котором наиболее целесообразна установка опорного узла (УЗ) сети абонентского доступа

 

Для этой цели сформируем матрицу расстояний по соединительным путям между всеми пунктам абонентской сети.

 

											∑

 

Из расчетов видно, что установка опорного узла сети абонентского доступа возможна в двух узлах, которые получили минимальные значения суммарных расстояния. Это узлы 3-й и 6-й соответственно. Установим опорный (УО) узел в узле №3.

 

Организация абонентской сети со стационарным радиодоступом

Необходимо среди пунктов абонентской сети определить местоположение базовой станции (БС), которая по радиоканалам связывается с абонентскими пунктами (АП). Для этого исходя из исходной матрицы весов находим максимальный элемент (то есть расстояние) по строке, а потом среди них находим минимальный, тем самым, минимизировав расстояние до самого отдаленного пункта. Узел которые мы обнаружим таким образом и будет центром графа. Отсутствие значений элементов матрицы следует рассматривать как отсутствие прямой радиовидимости между ними.

Исходная матрица расстояний

											Max
			∞			∞			∞	∞
					∞	∞	∞	∞	∞	∞
	∞			∞	∞			∞	∞	∞
			∞		∞		∞	∞	∞	∞
		∞	∞	∞			∞		∞	∞
	∞	∞								∞
		∞		∞	∞			∞	∞
		∞	∞	∞			∞
	∞	∞	∞	∞	∞		∞
	∞	∞	∞	∞	∞	∞

 

Из расчета следует, что наиболее минимизированной по расстоянию вершиной является вершина 2. Установим базовую станцию в узле 2.

 

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

3.4.1 Каково назначение сети абонентского доступа?

 

Сеть абонентского доступа предназначена для организации доступа абонентского оконечного оборудования из любой точки которая эта сеть покрывает.

 

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

 

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

 

3.4.3 Какой граф называется деревом, какой покрывающим деревом?

 

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

 

3.4.4 Сформулируйте идею алгоритма Прима, обеспечивающее построение сети минимальной стоимости.

 

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

 

3.4.5 Можно ли применить алгоритм Прима для построения сети максимальной стоимости. Если да, то каким образом.

 

Для формирования сети максимальной стоимости по алгоритму Прима необходимо вместо минимального веса (расстояния) ребра брать максимальное.

 

3.4.6 Можно ли использовать алгоритм Прима при неполносвязной исходной матрице расстояний? Что это означает?

 

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

 

3.4.7 Алгоритм Прима является точным или эвристическим?

 

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

 

 

3.4.8 Какая вершина называется медианой графа? Что является исходными данными для ее определения?

 

Медиана графа это такая вершина, в которой расстояние общей длинны кабеля до всех узлов является минимальное. Исходными данными для определения медианы графа является вес ребер заданного графа (матрица расстояний).

 

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

 

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

 

3.4.10 Какая вершина называется центром графа?

 

Центр графа это вершина, которая имеет минимальное расстояние до самой отдаленной вершины графа.

 

3.4.11 Сформулируйте алгоритм определения центра графа?

 

Определение максимального расстояние по строке для каждого узла, а потом среди этих расстояний нахождение минимального, это и будет центр графа, тот узел которому принадлежит это расстояние.

 

4. Синтез межузловой связи