Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/158029
Title: | Методы и алгоритмы дискретной математики для решения задач оптимизации, характеризации и распознавания : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель Р.И. Тышкевич |
Authors: | Тышкевич, Р. И. Метельский, Ю. М. Перез Чернов, А. Х. Суздаль, С. В. Супрун, В. П. Калачев, В. Н. Лубашева, Т. В. Максимович, О. В. Петрович, Р. А. Тимофеева, В. А. Шацов, Р. П. |
Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
Issue Date: | 2015 |
Publisher: | Минск : БГУ |
Abstract: | Объектом исследования являются задачи и алгоритмы для графов и булевых функций. Целью проекта является разработка методов и алгоритмов дискретной математики для решения задач оптимизации, характеризации и распознавания, формулируемых в терминах теории графов и теории булевых функций. В результате проведенных исследований расширена область применения теории алгебраической декомпозиции графов. Разработаны линейные алгоритмы распознавания классов униграфов и наследственных униграфов. Предложена релаксация известной NP-полной задачи распознавания графов одного из подклассов полярных графов C, приводящая к полиномиальному алгоритму. Получены оптимальные -раскраски всех неразложимых униграфов, а также ряда их композиций с произвольными оптимально раскрашенными графами. Установлена связь общей задачи -раскраски с известной задачей нахождения гамильтонова пути. На основе методов алгебраической декомпозиции графов в классах (1, 2)-полярных графов, (1, 2)-разложимых графов и униграфов доказана гипотеза ХартсфилдаРингеля об антимагичности связных графов. Получены характеризации (или доказана конечная характеризуемость) в терминах запрещенных порожденных подграфов и установлена сложность задачи распознавания для классов графов пересечений ребер гиперграфов ограниченных ранга и кратности при дополнительных условиях. Разработаны алгоритмы оптимизации полиномиального представления различных классов булевых функций. Полученные аналитические представления были использованы при синтезе вычислительных устройств, предназначенных для реализации этих классов булевых функций, зависящих от относительно небольшого числа переменных. Результаты работы могут быть использованы при решении различных оптимизационных, характеризационных и распознавательных задач дискретной математики, возникающих как в теории, так и в ее приложениях (в частности, при оптимизации радиосетей, проектировании сетей связи и интегральных схем). Некоторые из полученных результатов могут быть использованы в учебном процессе. |
URI: | http://elib.bsu.by/handle/123456789/158029 |
Registration number: | № гос. регистрации 20113523 |
Appears in Collections: | Отчеты 2015 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Отчет Тышкевич 20113523.doc | 2,22 MB | Microsoft Word | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.