Yurii Nosov » Публикация

Аннотация Рассматриваются максимальные внешнеплоские графы с двумя симплициальными вершинами (МВП-графы) с экстремальными значениями индекса Винера. Определены нижняя 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. Для нижней и верхней оценок индекса Винера произвольных и решётчатых МВП-графов определены экстремальные графы, на которых эти оценки достигаются. Полученные результаты могут быть использованы для классификации фигур в изображениях, представленных МВП-графами, и для классификации изомеров сопряжённых полиеновых углеводородов.