Подсчитайте количество связующих деревьев быстро

19

t(G)Gnt(G)O(n3)QGJ11n2det(J+Q)QGJ1

Интересно, есть ли способ вычислить t(G) быстрее. (Да, есть более быстрые, чем O(n3) алгоритмы для вычисления определителя, но меня интересует какой-то новый подход.)

Он также заинтересован в рассмотрении специальных семейств графов (может быть, планарных).

Например, для циркулянтных графов t(G) может быть вычислено в O(nlgn) арифметических операциях через тождество t(G)=1nλ1λn1 , где λi - ненулевые собственные значения матрицы Лапласа группы G , которые можно быстро вычислить для циркулянтных графов. (Представьте первую строку в виде полинома, а затем вычислите ее по n корням единицы - этот шаг использует дискретное преобразование Фурье и может быть выполнен за O(nlgn) арифметических операций.)

Большое спасибо!

Finsky
источник
Сергей, я попытался отредактировать твой вопрос, чтобы улучшить ясность. Пожалуйста, убедитесь, что я правильно понял ваш вопрос и не внес никаких ошибок.
Тайсон Уильямс
1
Вот один более общий пример граф семей , где найти сложность можно сделать быстрее: графы Кэлей для абелевых групп грамм с образующим набором S , так что S-1знак равноS . Мы знаем, что собственными значениями такой матрицы являются ΣчасSχ(час) , где χ - разные характеры группы. Все символы легко найти (для получения дополнительной информации обратитесь к этой статье ), вычисление этих символов является N мерным БПФ (см. Главу Брант и др. О БПФ), то есть может быть сделано в О(NЛ.Г.N) .
Финский
Для получения дополнительной информации о графиках Кэли см. Эту книгу .
Финский
1
Делать линейную алгебру с лапласианом, а не с общей матрицей часто проще. Интересно, может ли это быть актуально?
Гил Калай
Не могли бы вы, пожалуйста, быть более конкретными, если это возможно, привести несколько примеров, даже если они не имеют прямого отношения к обсуждаемой теме. Спасибо.
Финский

Ответы:

12

Оно известно , что для ограниченной древесной ширины, Татта полинома может быть оценены в любом с помощью арифметических операции. Если связно, то .граммT(грамм;Икс,Y)(Икс,Y)О(N)граммt(G)=T(G;1,1)

Раду Куртиканский
источник