Семинар по алгоритмам и структурам данных ФКН

Многие алгоритмы на графах имеют большую сложность. Для некоторых задач (например, проверка на существование гамильтонова цикла) даже не придумано полиномиального по времени алгоритма. Однако большинство алгоритмов работают довольно быстро в большинстве случаев. В частности, для многих алгоритмов показано, что они работают быстро на случайных графах.

Будем называть случайным графом и обозначать через G(n,p) случайный элемент множества графов на n вершинах, каждое ребро которого появляется независимо от других с вероятностью p (вообще говоря, зависящей от n). В таких графах мы можем быстро решать сложные задачи с вероятностью, стремящейся к единице. В частности, проверка на существование гамильтонова цикла устроена очень просто: нам достаточно проверить, что степени всех вершин не менее двух.

Задача нахождения веса минимального остовного дерева, в отличие от многих других, решается довольно быстро, но случайная постановка заслуживает отдельного рассмотрения. Так, А. Фриз показал, что в полном взвешенном графе на n вершинах с независимыми одинаково распределенными весами U[0,1] по мере роста n вес минимального остовного дерева стремится к числу ?(3) = 1/13 + 1/23 + 1/33 + …

Естественно, возникает вопрос: в чем причина настолько красивого ответа? Обладают ли красивыми ответами другие подобные задачи?

На докладе мы разберём задачу поиска веса минимального объединения k остовных деревьев, не пересекающихся по ребрам, обсудим алгоритм для решения этой задачи в общем случае и получим результат (пусть, и не такой красивый), обобщающий изначальную находку Фриза.

Выступает Никита Звонков, приглашенный преподаватель департамента больших данных и информационного поиска, стажер-исследователь международной лаборатории теоретической информатики ФКН ВШЭ.

3 октября 2024

Источник: cs.hse.ru

Комментарии: