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

Статья

Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве

Задача о независимоммножестведлязаданногографасостоитвтом,чтобынайти размер наибольшего множества его попарно несмежных вершин. Известны многочисленные случаи NP-трудности и случаи полиномиальной разрешимости этой задачи. Для установления вычислительного статуса задачи о независимом множестве в рассматриваемом классе графов часто используются локальные преобразования графов. В данной работе рассматривается некоторый класс замен подграфов в графах, причем замены из этого класса изменяют число независимости контролируемым образом. Каждое такое локальное преобразование графов определяется некоторым шаблоном — совокупностью подмножеств множества. Очевидно, что совокупность должна быть градуируемой. Показывается, что заменяющий подграф существует для любого градуируемого шаблона.