• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

О производящих функциях и предельных теоремах, связанных с максимальными независимыми множествами в графах-решетках

В настоящей работе рассматриваются количественные характеристики максимальных независимых множеств в графах-решетках. В ней используются методы комбинаторного анализа, перечислительной комбинаторики, математического анализа и линейной алгебры. Получен явный вид производящих функций количества максимальных независимых множеств в цилиндрических и тороидальных решетках ширины 4,5,64,5,6. Доказано, что пределы корней mnmn-ой степени из количества (максимальных) независимых множеств в прямоугольных, цилиндрических и тороидальных m×nm×n-решетках существуют и равны. Количественные аспекты максимальных независимых множеств в графах-решетках применительно к цилиндрическим и тороидальным решеткам ранее не рассматривались. Кроме того, существование пределов корней mn-ой степени из количества максимальных независимых множеств в m×nm×n-решетках также не было доказано. Таким образом, настоящая работа является дальнейшим развитием перечислительной комбинаторики.