Аттестационная комиссия
Комиссия по аккредитации
Комиссия по экспертов
Распоряжения, инструкции
Нормативные акты
Номенклатура
Организации
Ученые советы
Семинары
Диссертации
Научные руководители
Ученые
Докторанты
Постдокторанты
CNAA logo

 română | русский | english


Покрытие неориентированных графов d-выпуклыми множествами


Автор: Buzatu Radu
Степень:доктор
Специальность: 01.01.09 - Математическая кибернетика и операционные исследования
Год:2017
Научный руководитель: Sergiu Cataranciuc
доктор хабилитат, профессор, Государственный Университет Молдовы
Институт: Государственный Университет Молдовы

Статус

Диссертация была зашищена 23 марта 2017 в ученом совете и находится на рассмотрении в Национальном Совете.

Автореферат

Adobe PDF document0.76 Mb / на румынском

Диссертация

CZU 519.83

Adobe PDF document 3.60 Mb / на румынском
149 страниц


Ключевые слова

Неориентированный граф, 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#.