Действия с графами

Задание :

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

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

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

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

2. Кратчайший маршрут:

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

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

3. Обход графа 

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

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

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

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

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

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

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

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

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

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

Оформить решение задач в виде презентации (3 балла)

Предоставлены 2 примера, можно выбрать любой, граф по которому нужно делать тоже прикреплён.

В этом задании нужно набрать хотя-бы 15 баллов, больше можно не делать.