Семинар по алгоритмам и структурам данных ФКН "Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер"

3 октября 2024 в 18:10

Докладчик: Никита Звонков, ФКН НИУ ВШЭ

Тема: Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер

Аннотация: Многие алгоритмы на графах имеют большую сложность. Для некоторых задач (например, проверка на существование гамильтонова цикла) даже не придумано полиномиального по времени алгоритма. Однако большинство алгоритмов работают довольно быстро в большинстве случаев. В частности, для многих алгоритмов показано, что они работают быстро на случайных графах.
Будем называть случайным графом и обозначать через G(n,p) случайный элемент множества графов на n вершинах, каждое ребро которого появляется независимо от других с вероятностью p (вообще говоря, зависящей от n). В таких графах мы можем быстро решать сложные задачи с вероятностью, стремящейся к единице. В частности, проверка на существование гамильтонова цикла устроена очень просто: нам достаточно проверить, что степени всех вершин не менее двух.
Задача нахождения веса минимального остовного дерева, в отличие от многих других, решается довольно быстро, но случайная постановка заслуживает отдельного рассмотрения. Так, А. Фриз показал, что в полном взвешенном графе на n вершинах с независимыми одинаково распределенными весами U[0,1] по мере роста n вес минимального остовного дерева стремится к числу 𝝵(3) = 1/1³ + 1/2³ + 1/3³ + …. Натурально возникает вопрос: в чём причина настолько красивого ответа? Обладают ли красивыми ответами другие подобные задачи?
На докладе мы разберём задачу поиска веса минимального объединения k остовных деревьев, не пересекающихся по ребрам, обсудим алгоритм для решения этой задачи в общем случае и получим результат (пусть, и не такой красивый), обобщающий изначальную находку Фриза.

Место проведения: Покровский бульвар 11, аудитория N506