Задания для самостоятельного решения
1. С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D .
2. С помощью алгоритма фронта волны найти расстояния в ориентированном графе D : диаметр, радиус и центры.
Примечание: самый длинный путь в графе найти при помощи алгоритма фронта волны.
3. Найти минимальный путь в нагруженном графе по методу Форда-Беллмана.
| 
| 
| а)из вершины  ввершину 
| б) из вершины  ввершину 
| в) из вершины  ввершину 
|
4. Найти Эйлерову цепь в неориентированном графе.
5. Найти минимальное остовное дерево в неориентированном нагруженном графе.
6. Методом ветвей и границ найти оптимальный путь коммивояжёра при следующей матрице стоимости.
|
| 1
|
| 3
| 4
| 5
| 6
| | 1
| ¥
| 13
| 7
| 5
| 2
| 9
| | 2
| 8
| ¥
| 4
| 7
| 5
| 17
| | 3
| 8
| 4
| ¥
| 3
| 6
| 2
| | 4
| 5
| 8
| 1
| ¥
| 0
| 1
| | 5
| 2 1
| 6
| 1
| 4
| ¥
| 9
| | 6
| 10
| 0
| 8
| 3
| 7
| ¥
| 1 ® 5 ® 3 ® 4 ® 6 ® 2 ® 1 |
Расстояние равно 15
| |
| 1
| 2
| 3
| 4
| 5
| 6
| | 1
| ¥
| 6
| 4
| 8
| 7
| 14
| | 2
| 6
| ¥
| 7
| 11
| 7
| 10
| | 3
| 4
| 7
| ¥
| 4
| 3
| 10
| | 4
| 8
| 11
| 4
| ¥
| 5
| 11
| | 5
| 7
| 7
| 3
| 5
| ¥
| 7
| | 6
| 1 4
| 1 0
| 10
| 11
| 7
| ¥
| 1 ® 2 ®6 ®5 ® 4 ® 3 ® 1
Расстояние равно 36
| |
| 1
| 2
| 3
| 4
| 5
| 6
| | 1
| ¥
| 2
| 2
| 3
| 3
| 3
| | 2
| 2
| ¥
| 1
| 1
| 1
| 3
| | 3
| 2
| 1
| ¥
| 3
| 3
| 3
| | 4
| 3
| 1
| 3
| ¥
| 3
| 3
| | 5
| 3
| 1
| 3
| 3
| ¥
| 1
| | 6
| 3
| 3
| 3
| 3
| 1
| ¥
| 1 ® 3 ®2 ® 4 ® 6 ® 5 ® 1
Расстояние равно 11
|
| а)
| б)
| в)
|
СПИСОК ЛИТЕРАТУРЫ
1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М.: Наука, 1987. -598 с.
2. Бахвалов Н.С. Численные методы. Часть 1. -М.: Наука, 1973. -631 с.
3. Самарский А.А. Введение в численные методы. -М.: Наука, 1987. -286 с.
4. Калиткин Н.Н. Численные методы. -М.: Наука, 1978. -512 с.
5. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. Т. I, II. -М.: Наука, 1987. -600 с.
6. Житников В.П., Шерыхалина Н.М., Ураков А.Р. Линейные некорректные задачи. Верификация численных результатов. Учебное пособие. -Уфа: УГАТУ, 2002. -91 с.
7. Smith D.A., Ford W.F. Acceleration of linear and logarithmic convergence. – SIAM J. Numer. Anal., 1979, v. 16. -P. 223-240.
8. Smith D. A., Ford W. F. Numerical comparisons of non-linear convergence accelerations. – Mathematics of Computation, 1982, v. 38, 158. -P. 481–499.
9. Прудников А.П., Бычков Ю.А., Маричев О.И. Интегралы и ряды. –М.: Наука, 1981. -800 с.
Составители: ЖИТНИКОВ Владимир Павлович
ФЕДОРОВА Галина Ильясовна
ГАЛИМОВ Амир Камилович
ТЕОРИЯ ГРАФОВ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по подготовке к контрольным работам по дисциплине
«Дискретная математика»
Редактор Соколова О.А.
Подписано в печать 18.12.2003. Формат 60х84 1/16.
Бумага офсетная. Печать плоская. Гарнитура Таймс.
Усл.печ.л. 2,8. Усл.кр.–отт. 2,8. Уч.–изд.л. 2,7.
Тираж 100 экз. Заказ №
Уфимский государственный авиационный технический университет
Редакционно-издательский комплекс УГАТУ
450000, Уфа–центр, ул.К.Маркса, 12
|
|
Обсуждений еще не было, будьте первым... ↓↓↓
|
|
|
Популярное:
©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (223)
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы
|
(0.006 сек.)
2020-03-17
223
Обсуждений (0)
