Контрольная «Анализ графовой модели»,
Дискретная математика в Казани

В сфере своих профессиональных или личных интересов в печатных изданиях (книга, атлас, журнал, газета) или в интернете (обязательно с указанием выходных данных источника – адрес сайта и пр.) отыскать проблему, приводящую к задачам на графах. Число вершин которой не менее 11, ребер не менее 21, каждое ребро нагружено натуральным числом. Запишите весовую матрицу (1 балл) и нарисуйте диаграмму графа (1 балл) 1. Минимальное остовное дерева: • Исследовать два алгоритма построения минимального остовного дерева на своем графе. По шагам построить минимальное остовное дерево (3 балла) • В результате привести построенный граф (дерево выделить) и указать сумму длин его ребер. Сделать выводы об эффективности алгоритмов (сравнить) (3 балла) 2. Кратчайший маршрут: • Указать начальный узел. Исследовать алгоритм Дейкстры построения кратчайшего маршрута на своем графе. По шагам найти кратчайшие маршруты из начального узла во все остальные, составить пошаговые таблицы, отражающую алгоритм решения задачи (3 балла) • В результате привести соответствующие маршруты, их протяженность (2 балла) 3. Обход графа • Исследовать два метода обхода граф (в глубину и в ширину). По шагам найти последовательность обхода вершин (2 балла) • В результате указать порядок обхода, количество шагов каждого алгоритма. Сделать сравнительный анализ алгоритмов (2 балла) 4. Задача инспекции дорог (китайского почтальона) • Найти длину оптимального маршрута китайского почтальона на своём графе (3 балла) • Найти маршрут минимальной длины, который использует каждое ребро хотя бы один раз и возвращается в начальную вершину (3 балла) 5. Задача коммивояжёра • Найти в своем графе подграф с 5-6 вершинами, который является полным графом, либо достроить до такого (2 балла) • Использовать алгоритм ближайшего соседа, чтобы найти верхнюю границу для задачи коммивояжёра(3 балла) • Удалить одну вершину из графа и найдите нижнюю границу для задачи коммивояжёра (3 балла)