Реализация метрик на множестве графов
Вернуться к списку проектовНа главную страницу курсаЗаказчик
Москин Николай Дмитриевич, доцент кафедры Информатики и математического обеспечения. Эл.почта: moskin@petrsu.ru.Аннотация проекта
1. Требуется разработать программу, которая позволяет подсчитывать расстояние между графами с упорядоченными вершинами на основе максимального общего подграфа. На вход подается множество графов, представленных в заданном формате, на выходе - матрица расстояний между ними. При тестировании рекомендуется проверить свойства метрики. Алгоритм и формат должны быть оптимизированы под задачу для достижения наилучшей скорости вычисления расстояния.
2. Также необходимо разработать генератор графов определенного вида. На входе:
- диапазон числа вершин
- диапазон числа ребер (либо необязательное условие)
- диапазон степеней вершин (либо необязательное условие)
- ориентированный/неориентированный граф
- дополнительное условие, что это дерево или лес
Если при вводе данных какие-то два условия противоречат друг другу, то надо вывести сообщение об этом. На выходе - представление графов в заданном формате для задачи п.1.
