Пример. Выбор перспективного центра обработки информации для размещения баз данных

Выбор перспективного центра обработки информации для размещения баз данных.

Структура вычислительной сети определяется графом (рис. 5.4).

Рис. 5.4. Структура вычислительной сети

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

Таблица 5.4.

Веса при рёбрах графа

Вершины графа
		0.1	0.2	0.05
			0.3			0.1
					0.25		0.1
							0.3	0.15
						0.1				0.25
											0.35
									0.2
									0.1
										0.35		0.1
											0.3	0.15
												0.1

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

1. Присвоим веса =1 вершинам графа .

2. Определим соответствие относительно корневой вершины , воспользовавшись рис. 5.4 либо таблицей 5.4. Нетрудно заметить, что .

3. Обновим веса вершин . Так как начальные веса =1, то их новые значения определяются первой строкой таблицы 5.4, т.е. =0.1, =0.2, =0.05.

4. Определим минимальное значение . Таким значением является =0.05, которому соответствует вершина . Поэтому включим вершину и ребро в строящейся кратчайший остовный граф. Отметим этот факт утолщённым ребром на рисунке 5.4.

5. По аналогии с пунктами 2, 3 построим соответствие относительно вершины и обновим веса вершин . Для этого обратимся к четвёртой строке таблицы 5.4. Имеем: =0.3, =0.15.

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

.

Этому условию соответствует вершина , так как =0.1.

7. Определим и обновим их веса =0.1, а свой вес не меняет. Вес при вершине остаётся равным 0.2, так как вес при ребре равен 0.3 и больше (смотри вторую строку таблицы 5.4).

8. Найдём минимальное значение . Ему соответствует значение =0.1. На этом основании присоединим вершину и ребро к строящемуся остовному графу.

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