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

Аннотация Рассматриваются максимальные внешнеплоские графы (МВП-графы) с экстремальными значениями диаметра. Определены нижняя и верхняя оценки диаметра произвольных МВП-графов. Для решётчатых МВП-графов (т. е. для графов, уложенных на решётке из равносторонних треугольников без «дыр» и пересечений) доказано, что верхняя оценка диаметра совпадает с верхней оценкой диаметра произвольных МВП-графов; получена предварительная нижняя оценка диаметра. Для нижней и верхней оценок диаметра произвольных и решётчатых МВП-графов определены экстремальные графы, на которых эти оценки достигаются. Экстремальные графы с максимальным диаметром для произвольных и решётчатых МВП-графов совпадают. Полученные результаты могут быть использованы для классификации изображений, представленных МВП-графами, и для классификации изомеров сопряжённых полиеновых углеводородов.