Задания для аудиторной работы. № 1. Построить остовное дерево наименьшего веса для следующих графов:
№ 1. Построить остовное дерево наименьшего веса для следующих графов:
а) б)
в) г)
№ 2. Дан граф П с 7 вершинами, где заданы длины ребер:
а)AB=7, AD=12, AM=5, BE=11, BK=9, BM=7, CM=6, CD=10, EM=5, EK=12, DM=5, KM=6, AK=6;
б) AB=6, AC=11, AM=4, BE=12, BK=10, BM=8, CM=5, CD=9, EM=7, EA=13, DM=4, KM=7, EC=6.
Построить остовное дерево графа П, не выполняя построение исходного графа.
№ 3. Известны длины ребер графа П: АБ=7, АД=12, АМ=5, БГ=11, БК=9, БМ=7, ВМ=6, ВД=10, ГМ=6, ГК=12, ДМ=5, КМ=6, АК=6. Найти кратчайшее расстояние:
а) от вершины А до всех остальных и восстановить путь от А до всех вершин графа;
б) от вершины М до всех остальных и восстановить путь от М до всех вершин графа;
в) от вершины Г до всех остальных и восстановить путь от Г до всех вершин графа.
№ 4. Дана сеть П. Найти максимальный поток через сеть.
а) б)
в) г)
Задания для самостоятельной работы
№ 1. Построить остовное дерево наименьшего веса для следующих графов:
а) б)
в) г)
№ 2. Дан граф П с 7 вершинами, где заданы длины ребер:
а) AB=9, BC=5, CD=2, DE=8, EF=3, FG=7, AG=2, AM=3, AH=5, BM=8, BK=4, CK=3, DK=9, EK=9, MK=6, KH=8, EH=6, FH=1,GH=4;
б) AB=7, AK=9, AM=6, AH=2, AG=4, BK=5, BM=7, BC=4, CD=3, CM=9, DM=4, DE=8, KM=2, MH=3, ME=6, DE=8, EH=5, EF=4, FG=9, GH=8.
Построить остовное дерево графа П, не выполняя построение исходного графа.
№ 3. Известны длины ребер графа П: AB=7, BC=5, CD=4, DE=7, EF=8, FG=6, AG=5, AH=2, BH=9, GH=4, HK=7, BK=3, CK=9, DK=8, KM=5, DM=9, KF=8, FM=2. Найти кратчайшее расстояние
а) от вершины А до всех остальных и восстановить путь от А до всех вершин графа;
б) от вершины М до всех остальных и восстановить путь от М до всех вершин графа;
в) от вершины C до всех остальных и восстановить путь от C до всех вершин графа.
№ 4. Дана сеть П. Найти максимальный поток через сеть.
а) б)
Литература
Основная
1. Бабаш, А. Криптография / А. Бабаш, Г. Шанкин. – М. : Солон-Пресс, 2007. – 512 с. – ил.
2. Громкович, Ю. Теоретическая информатика / Ю. Громкович. – 3-е изд. – СПб. : BHV, 2010. – 336 с.
3. Могилев, А. В. Практикум по информатике / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – М. : Академия, 2005. – 608 с.
4. Новиков, Ф. А. Дискретная математика для программистов / Ф. А. Новиков. – СПб. : Питер, 2009. – 384 с. – ил.
5. Острейковский, В. А. Информатика. Теория и практика / В. А. Острейковский. – М. : Оникс, 2008. – 608 с. – ил.
Дополнительная
1. Алгоритм Дейкстры. – Режим доступа: algolist.manual.ru/maths/graphs/shortpath/dijkstra.php
2. Алгоритм Флойда. – Режим доступа: algolist.manual.ru/maths/graphs/shortpath/floyd.php
3. Белова, И. М. Компьютерное моделирование / И. М. Белова. – Режим доступа: window.edu.ru/window/
4. Будко, В. Н. Информационная безопасность и защита информации : конспект лекций / В. Н. Будко. – Режим доступа: window.edu.ru/window/
5. Иванов, Б. Н. Дискретная математика. Алгоритмы и программы : учеб. пособие / Б. Н. Иванов. – М. : Лаборатория базовых знаний, 2001. – 288 с.
6. Информатика : учеб. / под ред. проф. Н. В. Макаровой. – 2-е изд. – М. : Финансы и статистика, 1998. – 768 с.
7. Кассами, Т. и др. Теория кодирования / Т. Кассами. – М. : Мир, 1978. – 876 с.
8. Могилев, А.В. Информатика / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – М. : Академия, 2004. –848 с.
9. Брукшир, Дж. Г. Введение в компьютерные науки. Общий обзор / Дж. Г. Брукшир. – 6-е изд. – М. : Вильямс, 2001. – 688 с.
10.Нахождение максимального пропускного потока. – Режим доступа: algolist.manual.ru/maths/graphs/netflow.php
11. Нахождение на графе минимального остовного дерева. – Режим доступа: algolist.manual.ru/maths/graphs/span.php
12. Основы современных компьютерных технологий : сборник / под. ред. проф. А. Д. Хомоненко. – СПб. : Корона принт, 1998. – 448 с.
13. Рыжиков, Ю. И. Информатика : лекции и практикум / Ю. И. Рыжиков. – СПб. : Корона принт, 2000. – 256 с.
14. Кузнецов, С. Д. Методы сортировки и поиска / С. Д. Кузнецов. – Режим доступа: algolist.manual.ru/
15. Сергиевская, И. М. Математическая логика и теория алгоритмов : учебное пособие / И. М. Сергиевская. – Режим доступа: window.edu.ru/window/
16. Тарасевич Ю.Ю. Математическое и компьютерное моделирование: Учебное пособие - М.: Едиториал, 2003. - 144с.
17. Тарасевич Ю.Ю. Элементы дискретной математики для программистов. window.edu.ru/window/
18. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа. 2001. – 384 с.
Учебное издание
Поиск по сайту:
|