русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Минимальное остовное дерево


Дата добавления: 2013-12-23; просмотров: 2637; Нарушение авторских прав


Если дугам приписаны стоимости dij, то стоимость остовного дерева определяется как сумма dij по всем дугам дерева. Остовное дерево с наименьшей стоимостью среди всех остовных деревьев называется минимальным остовным деревом.

Замечание 3. В общем случае минимальное остовное дерево отличается от дерева кратчайших путей.

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

Лемма 1.Пусть Va произвольный узел и еах — кратчайшая дуга среди всех дуг, смежных с Va. Тогда существует минимальное остовное дерево Т*, содержащее дугу еах.

Доказательство. Пусть Т — минимальное остовное дерево, а, А — подмножество дуг, смежных с Va, например, А = {eab, eac, ead, eax}. Предположим, что дуга еах является кратчайшей дугой, смежной с Va, но не принадлежит Т. Поскольку Т — остовное дерево, то в Т должен быть путь из Vx в Va, содержащий одну из дуг А, например, ead. Обозначим этот путь через (Pxd, eda), где Pxd — путь из Vx в Vd . Заменяя ead на еах, получим Т*. Если еах короче, чем ead, то заключаем, что Т* — остовное дерево с меньшей стоимостью.

Во-первых, в дереве Т* Va соединяется с Vx дугой еах, а с узлом Vd путем (eax,Pxd). Оставшиеся узлы Vb, Vc по-прежнему связаны с Va и, следовательно, с остальными узлами сети, значит, Т* является остовным деревом.

Во-вторых, стоимость Т* меньше, чем Т, так как еах короче, чем ead. Это противоречит предположению о том, что Т — минимальное остовное дерево. Если дуги ead и еах имеют одинаковые длины, то также можно заменить еаd на еах и получить минимальное остовное дерево Т*, содержащее еах.

Лемма 2. Если известно, что подмножество ребер, образующих поддерево F, является частью минимального остовного дерева, то существует минимальное остовное дерево, содержащее F, и минимальное ребро, соединяющее F u N-F.



Доказательство. Доказательство в точности совпадает с доказательством леммы 1, если заменить Va на F.

 

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

Можно продолжить выбор наименьшего ребра, инцидентного уже выбранной компоненте. Это алгоритм Прима для нахождения минимального остовного дерева.

Идея алгоритма следующая. Алгоритм создает последовательные связные поддеревья, путем присоединения на каждом шаге одной смежной дуги так, чтобы на каждой стадии была выбрана инциндентная дуга с самой маленькой стоимостью. Пример реализации идеи алгоритма Прима представлен на рис. 12. Если начальный узел V0, то последовательность присоединяемых дуг следующая: дуга со стоимостью 1, смежная (вертикальная) дуга со стоимостью 2, дуга (горизонтальная) со стоимостью 2, дуга со стоимостью 4, дуга со стоимостью 3. Стоимость минимального остовного дерева 12.

Рис. 12. Пример минимального остовного дерева

 

Замечание 4. Алгоритм Прима для минимального остовного дерева сходен с алгоритмом Дейкстры для нахождения кратчайших путей.



<== предыдущая лекция | следующая лекция ==>
Поиск остовного дерева в ширину и поиск в глубину | Алгоритм Прима


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.