Методы и алгоритмы дискретной математики для решения задач оптимизации, характеризации и распознавания : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель Р.И. Тышкевич

Abstract

Объектом исследования являются задачи и алгоритмы для графов и булевых функций. Целью проекта является разработка методов и алгоритмов дискретной математики для решения задач оптимизации, характеризации и распознавания, формулируемых в терминах теории графов и теории булевых функций. В результате проведенных исследований расширена область применения теории алгебраической декомпозиции графов. Разработаны линейные алгоритмы распознавания классов униграфов и наследственных униграфов. Предложена релаксация известной NP-полной задачи распознавания графов одного из подклассов полярных графов C, приводящая к полиномиальному алгоритму. Получены оптимальные -раскраски всех неразложимых униграфов, а также ряда их композиций с произвольными оптимально раскрашенными графами. Установлена связь общей задачи -раскраски с известной задачей нахождения гамильтонова пути. На основе методов алгебраической декомпозиции графов в классах (1, 2)-полярных графов, (1, 2)-разложимых графов и униграфов доказана гипотеза ХартсфилдаРингеля об антимагичности связных графов. Получены характеризации (или доказана конечная характеризуемость) в терминах запрещенных порожденных подграфов и установлена сложность задачи распознавания для классов графов пересечений ребер гиперграфов ограниченных ранга и кратности при дополнительных условиях. Разработаны алгоритмы оптимизации полиномиального представления различных классов булевых функций. Полученные аналитические представления были использованы при синтезе вычислительных устройств, предназначенных для реализации этих классов булевых функций, зависящих от относительно небольшого числа переменных. Результаты работы могут быть использованы при решении различных оптимизационных, характеризационных и распознавательных задач дискретной математики, возникающих как в теории, так и в ее приложениях (в частности, при оптимизации радиосетей, проектировании сетей связи и интегральных схем). Некоторые из полученных результатов могут быть использованы в учебном процессе.