Остовные деревья с максимальной суммой произведений степеней вершин

Abstract

Задача, рассматриваемая в настоящей работе, возникла в области биоинформатики. Исходная постановка задачи такова: имеется множество людей, недавно заболевших некоторым инфекционным заболеванием. Требуется восстановить историю распространения эпидемии, т.е. установить, с кого началась инфекция, и кто кого заразил. Теоретико-графовой моделью рассматриваемой задачи служит остовное дерево графа, описывающего процесс распространения эпидемии, которое обладает максимальной суммой произведений степеней вершин, где суммирование производится по всем рѐбрам дерева. В работе рассматриваются структурные и алгоритмические свойства оптимальных остовных деревьев, а также устанавливается вычислительная сложность нахождения соответствующих теоретико-графовых параметров.