Графы_графы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оформить решение задач в виде презентации

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