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

Рассматриваются максимальные внешнеплоские графы с двумя симплициальными вершинами (МВП-графы) с экстремальными значениями индекса Винера. Определены нижняя W^L_n = n^2−3n+3 и верхняя W_n^U = (4n^3+6n^2−4n−3+3(−1)^n)=48 оценки индекса Винера произвольных МВП-графов порядка n. Для решётчатых МВПграфов (РМВП-графов), т. е. для графов, уложенных на решётке из равносторонних треугольников без «дыр» и пересечений, доказано, что верхняя оценка индекса Винера совпадает с верхней оценкой индекса Винера произвольных МВП-графов. Нижняя оценка W_n^[L] индекса Винера РМВП-графов определяется следующим образом: W_n^[L] = (n^3 + 6n^2 − 15n + 26)=18, если (n − 4) mod 3 = 0 и W_n^[L] = (n^3 + 6n^2 − 9n + 2 − 2(−1^)q)=18, если (n − 4) mod 3 = q, где q = 1; 2. Для нижней и верхней оценок индекса Винера произвольных и решётчатых МВП-графов определены экстремальные графы, на которых эти оценки достигаются. Полученные результаты могут быть использованы для классификации фигур в изображениях, представленных МВП-графами, и для классификации изомеров сопряжённых полиеновых углеводородов.
Челяб. физ.-матем. журн., 4:3 (2019), С.285–322. УДК 519.176; DOI: 10.24411/2500-0101-2019-14304