Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная м...
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
С помощью матрицы смежности найти компоненты сильной связности ориентированного графа 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
21
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
14
10
10
11
7
1 26 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а)б)в)СПИСОК ЛИТЕРАТУРЫ
- Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987. -598 с.
- Бахвалов Н.С. Численные методы. Часть 1. М.: Наука, 1973. 631 с.
- Самарский А.А. Введение в численные методы. М.: Наука, 1987. 286 с.
- Калиткин Н.Н. Численные методы. М.: Наука, 1978. 512 с.
- Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. Т. I, II. М.: Наука, 1987. 600 с.
- Житников В.П., Шерыхалина Н.М., Ураков А.Р. Линейные некорректные задачи. Верификация численных результатов. Учебное пособие. Уфа: УГАТУ, 2002. 91 с.
- Smith D.A., Ford W.F. Acceleration of linear and logarithmic convergence. SIAM J. Numer. Anal., 1979, v. 16. P. 223-240.
- Smith D. A., Ford W. F. Numerical comparisons of non-linear convergence accelerations. Mathematics of Computation, 1982, v. 38, 158. P. 481499.
- Прудников А.П., Бычков Ю.А., Маричев О.И. Интегралы и ряды. М.: Наука, 1981. 800 с.
Составители:ЖИТНИКОВ Владимир Павлович
ФЕДОРОВА Галина Ильясовна
ГАЛИМОВ Амир Камилович
ТЕОРИЯ ГРАФОВ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по подготовке к контрольным работам по дисциплине
Дискретная математика
Редактор Соколова О.А.
Подписано в печать 18.12.2003. Формат 60х84 1/16.
Бумага офсетная. Печать плоская. Гарнитура Таймс.
Усл.печ.л.2,8. Усл.кр.отт.2,8. Уч.изд.л.2,7.
Тираж 100 экз. Заказ №
Уфимский государственный авиационный технический университет
Редакционно-издательский комплекс УГАТУ
450000, Уфацентр, ул.К.Маркса, 12