Понедельник, 10 ноября, ауд. 106. Начало в 18:00.
Докладчик: В.А. Буслов (СПбГУ).
Тема: Экстремальные леса и иерархическая структура взвешенного орграфа.
Abstract
Рассматриваются остовные подграфы взвешенного орграфа, являющиеся лесами, состоящими из k деревьев, и имеющие минимальный вес среди всех k-компонентных лесов. При увеличении количества дуг (уменьшении числа деревьев) обнаруживаются "родственные связи" между минимизирующими лесами с разным количеством компонент, которые позволяют алгоритмизировать процесс построения лесов. При этом возникают вложенные алгебры подмножеств множества вершин, порождаемые множествами вершин деревьев минимизирующих лесов. Число различных алгебр подмножеств определяется определяется из неравенств выпуклости, которым удовлетворяют минимальные веса при различных k (числе компонент). Каждая Алгебра подмножеств, в свою очередь, позволяют построить из исходного графа "укрупнённый" граф, вершинами которого являются элементарные множества соответствующей алгебры, а веса специальным образом высчитываются. Такой граф сохраняет как бы общие черты предыдущего, всё более огрубляя взгляд на исходный орграф, но оставляя его существенные черты для данного уровня укрупнения.
