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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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