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

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

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

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

Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer

Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.

Что умеет делать SeoHammer

— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.

SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.

Зарегистрироваться и Начать продвижение

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

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

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

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

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

.

Задания:

Таблица 3.1

РП
X
Y

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

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

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

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

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

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

.

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

Сервис онлайн-записи на собственном Telegram-боте

Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.

Для новых пользователей первый месяц бесплатно.

Зарегистрироваться в сервисе

.

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