1. По Рис.64 и Рис.65 видно, что при любых количествах вершин в графе чем больше количество p-медиан, тем быстрее работают алгоритмы, как точный алгоритм поиска p-медиан в графе, так и приближенный алгоритм Тейтца и Барта.
2. По Рис.64 и Рис.65 можно судить о том, что точный алгоритм для поиска p- медиан в графе работает дольше, чем приближенный алгоритм Тейтца и Барта.
3. По результатам тестируемых примеров в Примере 11 в Табл.13 и Табл.14, а также в Примере 12 в Табл.17 и в Примере 13 в Табл.18 наблюдаются расхождения в наборах медиан, выданных точным и приближенным алгоритмами поиска p-медиан в графе. Это говорит о том, что в редких случаях приближенный алгоритм Тейтца и Барта дает неверные ответы.
Итак, в ходе выполнения работы создано Windows-приложение, реализующее:
1) ввод матрицы расстояний между вершинами графа вручную, считывание расстояний между вершинами графа из файла или заполнение матрицы расстояний псевдослучайными числами;
2) реализован алгоритм поиска внешней и внутренней медианы в графе;
3) реализован приближенный алгоритм Тейтца и Барта для поиска p-медиан в графе;
4) реализован точный алгоритм поиска p-медиан в графе;
5) разработан пользовательский интерфейс, содержащий 13 кнопок с названиями соответствующих операций;
6) были проведены численные эксперименты по проверке работоспособности точного алгоритма поиска p-медиан в графе, установлено, что алгоритм из-за ограничения памяти не работает при количестве вершин более 65;
7) были проведены численные эксперименты по сравнению результатов приближенного и точного алгоритмов, показано, что для небольших графов (до 25 вершин) алгоритмы давали одинаковые результаты, а для графов с большим количеством вершин погрешность не превосходила 2%.
При работе с приложением пользователю видно, с каким графом он работает, потому что матрица расстояний данного графа выводится в окне визуализации. Можно также увидеть и матрицу кратчайших расстояний между вершинами графа, если выполнить ее расчет.
Результаты работы программы можно как наблюдать в окне приложения, так и вывести их в текстовый файл.

Купить