АЛГОРИТМЫ БЫСТРОГО ПОИСКА ДЛЯ ДВУХ ЗАДАЧ О МЕТРИЧЕСКИХ ХАРАКТЕРИСТИКАХ ВЗВЕШЕННЫХ ГРАФОВ

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