Зачетное задание

В сфере своих профессиональных или личных интересов в печатных изданиях (книга, атлас, журнал, газета) или
интернете (обязательно с указанием выходных данных источника – адрес сайта и пр.) отыскать проблему
приводящую к одной из следующих задач на графах
(Задачу можете выбрать сами, какая по душе
1. Минимальное остовное дерево
• В сети, число узлов которой не менее 15, ребер не менее 23, каждое ребро нагружено натуральным числом
• Исследовать два алгоритма построения минимального остовного дерева на своем графе. По шагам построит
минимальное остовное дерево
• В результате привести построенный граф (дерево выделить) и указать сумму длин его ребер. Сделать вывод
об эффективности алгоритмов
• (По выбору) Написать программу или исследовать существующие библиотечные функции для реализаци
алгоритмов построения минимального остовного дерева
2. Кратчайший маршру
• В сети, число узлов которой не менее 11, ребер не менее 21, каждое ребро сети нагружено натуральны
числом, указан начальный узел
• Исследовать два алгоритма построения кратчайшего маршрута на своем графе. По шагам найти кратчайши
маршруты из начального узла во все остальные, составить пошаговую таблицу, отражающую алгорит
решения задачи
• В результате привести соответствующие маршруты, их протяженность. Сделать выводы об эффективност
алгоритмов
• (По выбору) Написать программу или исследовать существующие библиотечные функции для реализаци
алгоритмов построения кратчайшего пути
3. Максимальный пото
• В транспортной сети, число узлов которой не менее 13, ребер не менее 23, каждое ребро сет
ориентировано и нагружено натуральным числом, указаны начальный и конечный узлы (источник и сток)
• Исследовать два метода нахождения величины максимального потока из начального узла в конечный. П
шагам найти максимальный поток, составить пошаговую таблицу, отражающую алгоритм решения задачи
• В результате указать минимальное разделяющее сечение, максимальную пропускную способность сети,
также поток, позволяющий реализовать эту пропускную способность. Сделать сравнительный анали
алгоритмов
• (По выбору) Написать программу или исследовать существующие библиотечные функции для реализаци
алгоритмов поиска максимального потока
4. Критический путь (если успеем рассмотреть
• Задача о необходимости проведения комплекса работ за возможно более короткое время, в котором н
меньше 14 видов работ разной продолжительности
• Построить ориентированную сеть с привязкой ко времени
• Найти критический путь. В отчете указать критические работы, найденный критический путь и ег
продолжительность. Сделать выводы
• (По выбору) Написать программу или исследовать существующие библиотечные функции для реализаци
алгоритмов поиска критического пути
Важно! Входные данные должны определяться согласно реальным данным. При оценивании работ
содержательной стороне задачи и ее сложности будет уделяться особое внимание.