Conte o número de árvores abrangidas rapidamente

19

Seja o número de árvores que se estendem em um gráfico com vértices. Existe um algoritmo que calcula em operações aritméticas . Este algoritmo é computado , onde Q é o Laplaciano de G e J é a matriz que consiste apenas em 1 's. Para obter mais informações sobre esse algoritmo, consulte Biggs - Teoria dos grafos algébricos ou esta questão da matemática SE .G n t ( G ) O ( n 3 ) 1t(G)Gnt(G)O(n3)QGJ11 1n2det(J+Q)QGJ1 1

Gostaria de saber se existe alguma maneira de calcular t(G) mais rapidamente. (Sim, existem algoritmos mais rápidos que O(n3) para determinantes da computação, mas estou interessado em alguma nova abordagem.)

Também está interessado em considerar famílias especiais de gráficos (planares, talvez?).

Por exemplo, para gráficos circulantes, t(G) pode ser computado em operações aritméticas O(nlgn) através da identidade t(G)=1 1nλ1 1λn-1 1 , onde λEu são autovalores diferentes de zero da matriz laplaciana de G , que podem ser calculados rapidamente para gráficos circulantes. (Represente a primeira linha como um polinômio e depois calcule-a na n ésima raiz da unidade - esta etapa usa a transformação Discrete Fourier e pode ser feita em operações aritméticas O(nlgn) .)

Muito obrigado!

Finsky
fonte
Sergey, tentei editar sua pergunta para melhorar a clareza. Verifique se entendi sua pergunta corretamente e não introduzi nenhum erro.
Tyson Williams
11
Aqui está um exemplo mais geral de famílias gráfico onde encontrar complexidade pode ser feito mais rápido: gráficos Cayley para grupos abelianos G com geradores definir S , tal que S-1 1=S . Sabemos que os valores próprios dessa matriz são hSχ(h) , onde χ são caracteres diferentes do grupo. Todos os caracteres são fáceis de encontrar (para obter mais informações, consulte este documento ). O cálculo desses caracteres é FFT n dimensional (consulte Cormen et al capítulo sobre FFT), ou seja, pode ser feito em O(nlgn) .
Finsky
Para mais informações sobre os gráficos de Cayley, consulte este livro .
Finsky
11
Frequentemente, é mais fácil fazer álgebra linear com o Laplaciano do que com uma matriz geral. Gostaria de saber se isso pode ser relevante.
Gil Kalai
Você poderia, por favor, ser mais específico, se possível, fornecer alguns exemplos, mesmo que não estejam diretamente relacionados ao tópico em discussão. Obrigado.
Finsky

Respostas:

12

É conhecido que, para de treewidth limitada, o Tutte polinomial pode ser avaliado em qualquer utilizando as operações aritméticas. Se estiver conectado, então .GT(G;x,y)(x,y)O(n)Gt(G)=T(G;1,1)

Radu Curticapean
fonte