Дискретная математика

                                             Теория графов

Задание 5. В сфере своих профессиональных или личных интересов в печатных изданиях (книга, атлас, журнал, газета) или в интернете (обязательно с указанием выходных данных источника – адрес сайта и пр.) найдите проблему, приводящую к построению графа, число вершин которого не менее 11, ребер не менее 21 (5 баллов).

а) Нарисуйте диаграмму вашего графа (2 балла).

б) Проверьте ваш граф на "планарность". Нарисуйте его плоское изображение, если это возможно (2 балла).

в) Постройте матрицу смежности вашего графа. Найдите все пути длиной три из выбранной вершины (3 балла).

г) Найдите вектор степеней вершин. Проверьте ваш граф на "эйлеровость"(3 балла).

д) Нарисуйте подграф вашего графа, состоящий из всех вершин исходного графа и являющийся деревом. Запишите его матрицу смежности (4 балла).

е) Проверьте ваш граф на "двудольность"(3 балла).

ж) Какие ещё свойства графа вы можете отметить? (3 балла)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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