Покрытие неориентированных графов d-выпуклыми множествами
|
СтатусДиссертация была зашищена 23 марта 2017Утверждена Национальным Советом 31 мая 2017 Автореферат – 0.76 Mb / на румынскомДиссертацияCZU 519.83
|
Ключевые слова
Неориентированный граф, d-выпуклость, d-выпуклое множество, метрический отрезок, d-выпуклая оболочка, оптимизационная задача, d-выпуклое покрытие, d-выпуклое разбиение, NP-cложность, дерево, алгоритмАннотация
Структура работы: Диссертация написана на румынском языке и содержит введение, три главы, заключение с рекомендациями, список цитируемой литературы, состоящий из 115 наименований. Работа содержит 122 страницы основного текста. Полученные результаты были опубликованы в 12 научных работах.
Область исследования: Теория графов.
Цель исследования. Цель кандидатской диссертации состоит в изучении задачи покрытия неориентированного графа d-выпуклыми множествами. Достижения поставленной цели включает в себя следующие аспекты: исследование сложности задачи покрытия неориетированного графа 2 p d-выпуклыми множествами; определение условий существования семейства d-выпуклых множества, которые покрывают неориентированный гаф; разрешение задачи покрытия графова нетривиальными d-выпуклыми множествами; разработка алгоритмов для задачи покрытия/разбиение графа d-выпуклыми множествами; вычисление максимального/минимального числа d-выпуклого покрытия.
Научная новизна и оригинальность выражается в получении теоретико-прикладных результатов благодаря которым были дополнены и обобщены известные результаты, относящиеся к задачи покрытия графов d-выпуклыми множествами, и в доказательстве NP-полноты исследуемой задачи и различных её вариаций.
Решённая важная научная задача состоит в доказательстве NP-полноты задачи покрытия/разбиения неориентированного графа d-выпуклыми множествами, которое привело к необходимости изучения условий существования p 2 d-выпуклых множеств, образующих покрытие/разбиение некоторых классов графов для последующего использования в разработке методов и эффективных алгоритмов решения прикладных задач.
Теоретическая ценность работы заключается в получении результатов связанных с NP-полнотой задачи покрытия графа двумя d-выпуклыми множествами, которые дополняют результаты, полученные другими математиками. Доказано что задача покрытия графов d-выпуклыми множествами в общем случае и в случае нетривиальных d-выпуклых множеств является NP-полной.
Практичекая ценность работы заключается в возможности использования полученных результатов для изучения d-выпуклых множеств на дискретных структурах и в получении алгоритмов для задачи покрытия/разбиения графа на d-выпуклыме множества, которые могут быть использованы для решения исследуемой задачи на практике, например для задачи кластеризации элементов множества на котором определены бинарные отношения.
Внедрение научных результатов. Полученные результаты могут быть использованы при разработке спецкурсов, связанных с решением оптимизационных задач на дискретных структурах, для студентов университетов. Представленные в работе алгоритмы реализованы в виде библиотеки алгоритмов, написанной на языке C#.
Официальные оппоненты
- Dumitru Lozovanu
доктор хабилитат, профессор, Государственный Университет Молдовы - Anatol Prisăcaru
доктор, доцент
Члены Ученого Совета
- Gheorghe Mişcoi, председатель
доктор хабилитат, профессор, Институт математики и информатики - Boris Hâncu, секретарь
доктор, доцент, Государственный Университет Молдовы - Dumitru Solomon, член
доктор хабилитат, доцент, Государственный Университет Молдовы - Emilian Guţuleac, член
доктор хабилитат, профессор, Технический Университет Молдовы - Andrei Poştaru, член
доктор, доцент
Диссертации
