- •Кафедра электрификации и автоматизации производства
- •Кафедра электрификации и автоматизации производства
- •Реферат
- •Содержание
- •Введение
- •1 Общие положения проектирования асу в чс
- •Расчёт центра асу чс
- •1.2 Построение генплана района
- •1.3 Применение теории графов для оптимизации информационной сети
- •1.4 Построение минимального остовного дерева
- •Программа «жадного» алгоритма
- •2.1 Оценка характеристик пропускной способности асу в чс
- •2.2 Технико – экономический анализ внедрения асу в чс
- •2.3 Разработка схемы технической реализации асу в чс
- •2.4 Выбор перечня технических средств для организации асу в чс
- •Заключение
- •Список использованных источников
1.4 Построение минимального остовного дерева
Минимальным остовным деревом называется дерево с минимальным общим весом его рёбер.
Минимум
остовных деревьев графа Г
= (X, U,
Ф)
можно найти, применяя процедуру
исследования рёбер в порядке возрастания
их весов. Другими словами, на каждом
шаге выбирается новое ребро с наименьшим
весом, не образующее циклов с уже
выбранными рёбрами. Процесс продолжается
до тех пор, пока не будет выбрано
–1
ребро. Рассмотренная процедура называется
«жадным» алгоритмом
,
разработана
французским учёным Краскалем в 1956г.,
использовалась при проектировании
французских электрических сетей.
Пользуясь алгоритмом Краскаля для поиска минимального остовного дерева на графе возможных соединений схемы информационной сети, можно найти схему соединений всех объектов по критерию минимума суммы всех расстояний от одного объекта до другого. Согласно алгоритму Краскаля:
- сортируем все рёбра графа (соединения между объектами в порядке возрастания расстояния между ними);
- берём ребро с минимальной стоимостью и проверяем не образует ли это ребро с ранее рассмотренными рёбрами цикла или петли;
- если не образует цикла или петли добавляем к ранее уже выбранным последующие рёбра;
- проделываем эту последовательность пока не будут соединены все вершины полного графа.
Реализация данной схемы может быть выполнена следующим образом. Для каждой вершины Х= {хь х2,.... хп} графа Г = (X,U,Ф) формируются начальные тривиальные компоненты связности:
где
i=j,
I=1,2,…,
Компоненты
являются
деревьями, объединение
которых даёт
начальное
приближение строящегося остовного
дерева Г0
= (X,
,Ф).
Включение в строящееся остовное дерево Г0 выбранного ребра на очередном шаге «жадного» алгоритма выполняется слиянием
и
двух
компонент
,
,
которым принадлежит по вершине нового
ребра, и включением самого ребра в
объединённое множество
рёбер.
Процесс роста объединения
компонент
к остовному дереву Г0=(Х,
U0,
Ф)
продолжаем до тех пор, пока не будет
включено
–
1
ребро.
Справедливость «жадного» алгоритма является следствием следующих двух лемм.
Лемма 1. Пусть Г=(Х, U, Ф) – связный неориентированный граф и
Г
=(Х,
Ф)
–
произвольное остовное дерево для него.
Тогда:
1). V
Х
cуществует
единственная между ними цепь в Г0;
2). если к Г добавить ребро из U/U , то возникнет ровно один цикл.
Лемма
2.
Пусть Г
=(Х, U,
Ф)
–
связный неориентированный граф, для
каждого ребра
определён вес
и
–
компоненты связности «жадного» алгоритма,
объединение которых
,
согласно алгоритму, растёт к остовному
дереву Г0=(Х,
U0,
Ф),
где i
= 1,2,…,k
и
Пусть
следующим найденным для включения
ребром является ребро Е =(х,у) наименьшего
веса из оставшихся U
и пусть
Тогда найдётся остовное дерево Г
для Г =(Х, U,
Ф), содержащее рёбра
вес
которого не больше любого другого
остовного дерева, содержащего ребра у
U
.
Используя алгоритм Краскаля, построим минимальное остовное дерево (информационную сеть, обладающую минимальной длиной).
