Вопросы перечисления независимых множеств в графах-решетках

Вопрос графов широко изучается математиками в связи с быстрым развитием компьютерных технологий в двадцатом и двадцать первом веке. Для решения различных задач разработано множество алгоритмов для разных типов графов. Исследование решетчатых графов является одной из актуальных тем для развития науки как естественной, так и компьютерной. В ходе данной работы будут рассмотрены решетчатые графы, а также его независимые наборы с шагом 3. Для определения ключевых фактов мы будем использовать мультиметодный дизайн исследования. Сначала мы рассмотрим независимые наборы вершин с шагом 1 в рамках известной теории. Потом мы проанализируем методы для вычислений общего числа независимых наборов вершин. Для решения нашей задачи нам будет необходимо адаптировать известные алгоритмы для нашей задачи. В частности, мы рассмотрим адаптацию метода передаточной матрицы для вычисления общего числа независимых наборов вершин i(m,n) и вычисления общего числа максимальных независимы наборов вершин β(m,n) для решетчатого графа G размера m × n.