Рассматривается инвариант W(G) связных неориентированных графов G, равный сумме расстояний между всеми парами вершин графа G. Предлагается эффективный алгоритм расчёта матрицы расстояний и индекса Винера максимальных внешнеплоских графов с большим количеством вершин. Временная сложность алгоритма O(n2). Алгоритм удобен как для ручного расчёта индекса Винера небольших графов, так и для расчёта индекса Винера графов, сгенерированных компьютерной программой.
ПДМ, 2015, 3(29), С.95–109. УДК 519.17;