Cuente rápidamente el número de árboles de expansión

Supongamos que $t(G)$ denota el número de árboles de expansión en un gráfico con vértices. Hay un algoritmo que calcula en operaciones aritméticas . Este algoritmo es para calcular , donde es el laplaciano de y es la matriz que consiste únicamente en 's. Para obtener más información sobre este algoritmo, vea Biggs: teoría de gráficos algebraicos o esta pregunta de Math SE . $G$ $n$ $t(G)$ $O(n^3)$ $\frac{1}{n^2} \det(J + Q)$ $Q$ $G$ $J$ $1$

Me pregunto si hay alguna forma de calcular $t(G)$ más rápido. (Sí, hay algoritmos más rápidos que $O(n^3)$ para calcular determinantes, pero estoy interesado en algún enfoque nuevo).

También está interesado en considerar familias especiales de gráficos (¿planar, tal vez?).

Por ejemplo, para gráficos circulantes, se puede calcular en operaciones aritméticas través de la identidad , donde son valores propios distintos de cero de la matriz laplaciana de , que pueden calcularse rápidamente para gráficos circulantes. (Representa la primera fila como un polinomio y luego calcular en raíces -ésimos de unidad - este paso utiliza la transformación discreta de Fourier y se puede hacer en las operaciones aritméticas.) $t(G)$ $O(n \lg n)$ $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$ $\lambda_i$ $G$ $n$ $O(n \lg n)$

¡Muchas gracias!

graph-theory graph-algorithms counting-complexity spectral-graph-theory Finsky
fuente

Sergey, intenté editar tu pregunta para mejorar la claridad. Compruebe que entendí su pregunta correctamente y no introduje ningún error.

Tyson Williams el

Aquí es un ejemplo más general de las familias gráfico donde la complejidad de encontrar se puede hacer más rápido: grafos de Cayley para grupos abelianos con los generadores establecen , tal que . Sabemos que los valores propios de dicha matriz son , donde son caracteres diferentes del grupo. Todos los personajes son fáciles de encontrar (para más información consultar este documento ) el cálculo de esos personajes es FFT-dimensional (ver Cormen et al capítulo sobre FFT), es decir, se puede hacer en .

G

$G$

S

$S$

S^{- 1} = S

$S^{-1} = S$

\sum_{h \in S} χ (h)

$\sum_{h \in S} \chi (h)$

χ

$\chi$

n

$n$

O (n \lg n)

$O(n \lg n)$

Finsky

Para obtener más información sobre los gráficos de Cayley, vea este libro .

Finsky

Hacer álgebra lineal con la matriz laplaciana en lugar de una matriz general es a menudo más fácil. Me pregunto si esto puede ser relevante.

Gil Kalai

Podría, por favor, ser más específico, si es posible, proporcionar algunos ejemplos, incluso si no está directamente relacionado con el tema en discusión. Gracias.

Finsky

Cuente rápidamente el número de árboles de expansión

Respuestas: