О двух задачах аппроксимации взвешенных графов и алгоритмах их решения

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