Задача синтеза графа электрической сети наименьшей стоимости

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

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

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

Граф наименьшей длины можно построить, пользуясь следующим алгоритмом.

1. Прежде всего соединяются две вершины с наиболее коротким соединяющим ребром .

2. На втором шаге присоединяется самое короткое из оставшихся ребер .

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

Каждое дерево , построенное таким образом, будем называть экономическим деревом графа. Его длина равна сумме длин отдельных ребер.

.

Задания:

Таблица 3.1

РП
X
Y

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

· при условии прокладки сети в любом месте плоскости пола цеха (метрика Евклида);

· при условии прокладки сети под прямыми углами в пределах существующей сетки (метрика Вебера);

· изобразить спроектированные сети.

Методические указания

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

.

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

.

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