Сложность и методы решения задач, связанных с поиском специальных деревьев в графе: магистерская диссертация / Андрей Владимирович Клицунов; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Дугинов О. И.

Abstract

Цель работы—рассмотреть специальные деревья с различными свойствами, определить класс вычислительной сложности задачи поиска этого специальногодеревавпроизвольномграфелибовграфеизнекоторогоспециального класса, если класс задачи определён, рассмотреть точные (если возможно) или приближённые алгоритмы поиска, а также предложить свои варианты решения. Также целью работы является поиск некоторых необходимых условий существования в графе специального дерева, а также определение класса вычислительной сложности задач, которые соответствуют этим необходимым условиям. Ещё в цель работы входит более подробное рассмотрение задачи распространения информации в сети, её классической постановки и других постановок, определение класса этих задач по вычислительной сложности. Методы исследования—построение полиномиальных сведений, изучение подходов к построению эвристических алгоритмов, работа с научными материалами. Результаты—построен ряд полиномиальных сведений, доказывающий NPтрудность рассматриваемых задач поиска в графе специальных деревьев, а также получены некоторые результаты для специальных классов графов. Более подробно была рассмотрена задача распространения информации в сети, её классическая и другие варианты постановки. Был построен ряд полиномиальных сведений задачи 3-Выполнимость к распознавательным версиям постановок этой задачи. Построен полиномиальный алгоритм для задачи Целевое Множество в одном из специальных классов графов.