КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Алгоритм Краскала нахождения остова минимального веса
|
|
|
|
Задача об остове минимального веса (о кратчайшем остове):
в связном взвешенном графе 
порядка 
найти остов минимального веса.
Алгоритм Краскала, решающий эту задачу, заключается в следующем.
1. Строим граф 
, присоединяя к пустому графу на множестве вершин 
ребро 
минимального веса.
2. Если граф 
уже построен и 
, то строим граф 
, где 
- ребро графа G, имеющее минимальный вес среди ребер, не входящих в 
и не составляющих циклов с ребрами из .
Следующая теорема утверждает, что алгоритм Краскала всегда приводит к остову минимального веса:
при i < n – 1 граф Ti+ 1 всегда можно построить. Граф Tn- 1 будет являться остовом минимального веса в графе (G,w).
Доказательство:
Граф Ti имеет ровно i ребер и потому при i < n – 1 является несвязным. А, так как, граф G связен, то в нем есть по меньшей мере одно ребро, не составляющее циклов с ребрами графа Ti. Итак, нужное ребро Ui+ 1существует и граф Ti+ 1можно построить.
В качестве иллюстрации рассмотрим взвешенный граф, изображенный на рисунке. 3.18.
Полагаем 
. Среди оставшихся ребер минимальный вес имеет, например, ребро 
. Однако оно не пригодно для построения, поскольку составляет цикл с двумя предыдущими рёбрами. Можно взять 
.
Итак, рёбра 
составляют остов минимального веса. А сам вес остова равен 10.
1 3 5
· ·
1 2 4 4
· · ·
4 5 2 3 3
1 5
· ·
1 2 4
· · ·
4 2 3 3
Рисунок 3.18 – Граф и его остов минимального веса
3.5 Выполнение работы
Каждый студент получает номер задания для написания программы, реализующей конкретную задачу. Инструментарий не ограничивается.
Программа должна предусматривать ввод элементов графа, применение анимации (прорисовку графов) и выдачу результатов.
3.6 Содержание отчета
1. Наименование и цель работы
2. Краткие теоретические сведения
3. Описание программы
4. Схема алгоритма
5. Текст программы
6. Контрольный пример
7. Выводы
3.7 Контрольные вопросы
1. Дать определение графа.
2. Что такое взвешенный и ориентированный граф?
3. Основные шаги алгшоритмов:
- Дейкстры,
- Форда-Фалкерсона,
- Флери,
- транспортной задачи,
- задачи о коммивояжере,
- Краскала.
4. Чем отличается Эйлеров цикл от Гамильтонового?
4 ЛАБОРАТОРНАЯ РАБОТА № 4
|
|
|
|
|
Дата добавления: 2015-08-31; Просмотров: 731; Нарушение авторских прав?; Мы поможем в написании вашей работы!