![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задача синтеза графа электрической сети наименьшей стоимости
Большое практическое значение имеет следующая задача, которую можно сформулировать в виде задачи о построении графа электрической сети наименьшей стоимости. Пусть имеется несколько узлов Если имеются три вершины Из всего вышесказанного можно сделать очень важный вывод: граф наименьшей длины всегда имеет конфигурацию типа дерева, он не содержит циклов, т.к. если бы он содержал циклы, то всегда можно было бы удалить одно из ребер, а вершины все же остались бы соединенными. Т.о. для соединения Граф наименьшей длины можно построить, пользуясь следующим алгоритмом. 1. Прежде всего соединяются две вершины с наиболее коротким соединяющим ребром 2. На втором шаге присоединяется самое короткое из оставшихся ребер 3. На каждом из следующих шагов добавляем самое короткое из оставшихся ребер Каждое дерево
Задания: Таблица 3.1
Для заданных координат установки распределительных пунктов цеха (табл. 3.1) промышленного предприятия спроектировать сеть минимальной стоимости, приняв в качестве меры расстояния между ними: · при условии прокладки сети в любом месте плоскости пола цеха (метрика Евклида); · при условии прокладки сети под прямыми углами в пределах существующей сетки (метрика Вебера); · изобразить спроектированные сети. Методические указания При выполнении первого пункта задания используется метрика (правило вычисления расстояния) Евклида. При этих условиях для любых двух точек, заданных своими координатами т.
При выполнении второго пункта задания используется метрика Вебера. При этих условиях для любых двух точек, заданных своими координатами т.
При реализации алгоритма Краскала необходимо определиться с числом ребер, из которых в дальнейшем выбирают ребра, образующие минимальный остов графа. Это число определяется по следующему правилу: пусть
|