Дискретная математика, алгоритмы на графах

Алгоритмы на графах

Задание 6. Продолжите работу над проблемой из задания 5,нагрузив каждое ребро графа натуральным числом. Запишите весовую матрицу и нарисуйте диаграмму взвешенного графа (4 балла)

 а) Минимальное остовное дерево:

• Исследуйте два алгоритма построения минимального остовного дерева на своем графе. По шагам постройте минимальное остовное дерево (3 балла).

• В результате приведите построенный граф (дерево выделите) и укажите сумму длин его ребер. Сделайте выводы об эффективности алгоритмов (2 балла).

 б) Кратчайший маршрут:

• Укажите начальный узел. Исследуйте алгоритм Дейкстры построения кратчайшего маршрута на своем графе. По шагам найдите кратчайшие маршруты из начального узла во все остальные, составьте пошаговые таблицы, отражающие алгоритм решения задачи (3 балла).

• В результате приведите соответствующие маршруты и их протяженность (2 балла).

 в) Обход графа 

• Исследуйте два метода обхода графа (в глубину и в ширину). По шагам найдите последовательность обхода вершин (3 балла).

• В результате укажите порядок обхода, количество шагов каждого алгоритма. Сделайте сравнительный анализ алгоритмов (2 балла).

 г) Задача инспекции дорог (китайского почтальона)

• Найдите в своем графе подграф с 7-8 вершинами, у которого лишь 2 (или 4) вершины имеют нечетную степень (2 балла).

• Найдите длину оптимального маршрута китайского почтальона на найденном подграфе (3 балла)

• Найдите маршрут минимальной длины, который использует каждое ребро хотя бы один раз и возвращает в начальную вершину (3 балла)

 д) Задача коммивояжёра

• Найдите в своем графе подграф с 5-6 вершинами, который является полным графом, либо достройте до такого (2 балла).

• Используйте алгоритм ближайшего соседа, чтобы найти верхнюю границу для задачи коммивояжёра (3 балла).

• Удалите одну вершину из графа и найдите нижнюю границу для задачи коммивояжёра (3 балла).

 Важно! Входные данные должны определяться согласно реальным данным. При оценивании работы содержательной стороне задачи и ее сложности будет уделяться особое внимание.