русс | укр

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

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

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

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


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

Определения и свойства.


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


Остовные деревья минимальной стоимости.

Определение 1. Свободным деревом называется связный граф без циклов.

Остовным деревом графа называется свободное дерево , содержащее все вершины графа .

Теорема 1. (Свойства свободных деревьев)

1. Каждое свободное дерево, имеющее n вершин (n≥1), имеет ровно n-1 ребро.

2. При добавлении в любое свободное дерево нового ребра образуется цикл.

Определение 2. Пусть - помеченный граф, для каждого ребра его метка (стоимость) равна . Стоимостью остовного дерева

В этом разделе рассматриваются методы нахождения остовных деревьев минимальной стоимости.

Типичное применение остовных деревьев минимальной стоимости можно найти при разработке коммуникационных сетей. Здесь вершины графа представляют города, ребра - возможные коммуникационные линии между городами, а стоимость ребер соответствует стоимости коммуникационных линий. В этом случае остовное дерево минимальной стоимости представляет коммуникационную сеть, объединяющую все города коммуникационными линиями минимальной стоимости.

Теорема 2. (Свойство остовных деревьев минимальной стоимости).

Пусть — связный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через подмножество множества вершин . Если — такое ребро наименьшей стоимости, что и , тогда для графа существует остовное дерево минимальной стоимости, содержащее ребро .

Доказательство. Допустим противное: не существует остовного дерева минимальной стоимости для графа , содержащего , то есть для любого остовного дерева , содержащего его стоимость не минимальна.

Рассмотрим произвольное остовное дерево , имеющее минимальную стоимость. В частности, для него

(1)

Добавим к дереву ребро , получим , - граф с циклом. Цикл содержит ребро , соединяющее и , а также некоторое ребро , соединяющее и . (рис. 5.1.1)



Причем, по выбору ребра , справедливо .

Рис. 5.1.1.

Удалим ребро из дерева .

Так как удаление ребра привело к разрыву цикла, то - свободное дерево, содержащее все вершины , следовательно - остовное дерево графа , содержащее , стоимость которого . Однако, выбирая в (1) , получим . Противоречие. Значит допущение неверно. Теорема доказана.

 

Существуют различные способы построения остовных деревьев минимальной стоимости. Многие из них основаны на теореме 2. Далее будут рассмотрены два таких алгоритма.

 



<== предыдущая лекция | следующая лекция ==>
Транзитивное замыкание | Листинг 5.2.1. Эскиз алгоритма Прима


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


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

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

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


 


Полезен материал? Поделись:

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

 
 

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

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