Аннотация:
Доклад будет посвящен экстремальным проблемам вероятностной комбинаторики, связанными со взвешенными графами. Кратко подобный класс задач можно описать следующим образом: элементам некоторого конечного множества приписаны положительные случайные веса, нами выделены некоторые подмножества, цель - найти выделенное подмножество с минимальным суммарным весом элементов. Одна из наиболее известных проблем описанного типа связана с нахождением минимального веса остовного дерева в полном графе при условии независимости и одинаковой распределенности весов ребер. Знаменитый результат А. Фриза показывает, что в естественных предположениях о распределении весов среднее значение искомой величины сходится к дзета-функции от 3. В докладе мы обсуждаем связь этой задачи с классическими результатами теории случайных графов, а также представляем ее обобщение, связанное с поиском минимального суммарного веса сразу для k остовных деревьев.
|
