В статье предложен инкрементальный алгоритм, ускоряющий синтез минимального графа смежности по исходному минимальному графу смежности и новой вершине с заданной допустимой нагрузкой; доказана корректность работы такого алгоритма. Выполнен сравнительный анализ статистических оценок сложности реализаций предложенного алгоритма и двух известных алгоритмов синтеза минимального графа смежности: жадного и прямого; результаты вычислительных экспериментов представлены в виде графиков, снабжены комментариями и выводом. В целом, на наборах со средним и большим числом вершин инкрементальный алгоритм в 3-6 раз оказался быстрее, чем прямой, и в 10-50 раз быстрее, чем жадный. На наборах с небольшим числом вершин скорость алгоритмов отличается не сильно. Отмечено, что, чем больше в наборе вершин с нагрузкой 5-9 символов, тем более велик разброс отношения скоростей сравниваемых алгоритмов. В статье также достигнуты дидактические цели: в контексте синтеза минимальных графов смежности продемонстрировано обоснованное применение методов инкрементализации алгоритмов, статистического анализа скорости работы реализаций алгоритмов, визуализации данных, полученных в результате проведения вычислительных экспериментов. С. 3-18.

The paper provides the description of an incremental algorithm that accelerates a minimal joint graph upgrade when a new node with a correct load is inserted. The algorithms correctness is proven. We compare relative performance statistical estimates for the new incremental algorithm and two known greedy and streightforward algorithms that implement minimal joint graph synthesis. The computational experiments results are represented with plots, discussed and summarized. For the middle and large sized sets of loads, the incremental algorithm is 3-6 times faster than the streight-for-ward one and 10-50 times faster than the greedy one. For the small sized sets of loads, the algorithms permormance differs less dramatically. The relative performance variation of compared algorithms are the larger the higher fraction of loads with 5-9 symbols the set of loads has. The paper also reaches didactical goals: in the context of minimal joint grah synthesis, we demonstrate a rational application of the algorithm incrementation, an example of relative algorithmical performance statistical estimates, an approach to the visualisation of performance comparison compuational experiments.