La Matriz de Árbol Teorema para Ponderado de los Gráficos.

Question

Estoy interesado en la forma general de la Matriz de Kirchoff Árbol Teorema para ponderado de los gráficos, y, en particular, lo interesante ponderaciones uno puede elegir.

Deje $G = (V,E, \omega)$ ser un grafo ponderado donde $\omega: E \rightarrow K$, para un determinado campo K; supongo que la gráfica es sin bucles.

Para cualquier spanning tree $T \subseteq G$ el peso del árbol es dado ser, $$m(T) = \prod_{e \in T}\omega(e)$$ y el árbol polinomio (estadísticos o suma) de la gráfica se da a ser la suma de todos los árboles de expansión en G, $$P(G) = \sum_{T \subseteq G}m(T)$$ La combinatoria de laplace de la gráfica de G es dada por $L_G$, donde: $$L_G = \begin{pmatrix} -\sum_{k = 1}^n\omega(e_{1k}) & \omega(e_{12}) & \cdots & \omega(e_{1n}) \\\ \omega(e_{12}) & -\sum_{k = 1}^n\omega(e_{2k}) & \cdots & \omega(e_{2n})\\\ \vdots & \vdots & \ddots & \vdots \\\ \omega(e_{1n}) & \omega(e_{2n}) & \cdots & -\sum_{k = 1}^n\omega(e_{nk}) \end{pmatrix} $$

donde $e_{ik}$ es la arista entre los vértices $i$$k$, si no hay ningún borde que existe, a continuación, la entrada es 0 (es el mismo que considera el grafo completo de n vértices con una mayor ponderación de la función que da el peso de 0 a cualquier borde no en G). La matriz de árbol teorema dice que el árbol polinomio es igual al valor absoluto de cualquier cofactor de la matriz. Es decir,

$$P(G) = \det(L_G(s|t))$$

donde $A(s|t)$ denota la matriz obtenida al eliminar la fila $s$ y la columna $t$ a partir de una matriz A.

Por la elección de diferentes ponderaciones que uno esperaría encontrar interesantes propiedades de un grafo G. Dos aplicaciones sencillas para dar a la ponderación de todos los 1. A continuación, el teorema nos permite contar el número de árboles de expansión con facilidad (esto produce que el estándar de la declaración de la Matriz de Árbol Teorema para los gráficos). Alternativamente, dando a cada borde de una clara formal símbolo como su etiqueta, a continuación, mediante el cálculo de la correspondiente determinante, la suma obtenida se puede leer como una lista de todos los árboles de expansión.

Mi pregunta es si hay otros interesantes ponderaciones que puede ser utilizada para obtener otras propiedades interesantes de los gráficos, o para los problemas aplicados.

Answer 1

Muy interesante la ponderación se obtiene trabajando con dirigió multigraphs (dimgraphs). 7 u 8 años, he aplicado la matriz de árbol teorema aplicado a dimgraphs en conjunción con la MEJOR teorema de proporcionar una teoría de la estructura para el equilibrio termodinámica de la hibridación para oligoméricas (corto) de las hebras de ADN.

Brevemente, el SantaLucia modelo de hibridación de ADN toma un número finito de palabras $w$ en cuatro letras (a, C, G, T) y asociados a varios termodinámico características (por ejemplo, la energía libre $\Delta G$ de hibridación), basado en la secuencia. Suponiendo que las palabras son cíclicos (que no es justo, pero también no es una mala aproximación a la práctica), uno ha $\Delta G (w) = \sum_k \Delta G (w_kw_{k+1})$ cuando el índice de $k$ es cíclico y el 16 de parámetros $\Delta G(AA), \dots, \Delta G(TT)$ se dan.

Suponiendo que para la conveniencia de que el $\Delta G(\cdot,\cdot)$ son independientes sobre $\mathbb{Q}$, no es difícil ver que $\Delta G$ de los proyectos desde el espacio de todas las palabras de longitud $N$ a el espacio de dimgraphs en 4 vértices (de nuevo, a, C, G, T) con $N$ bordes, donde (por ejemplo) un borde de la a a la G corresponde a la larga AG. El uso de la matriz de árbol y las MEJORES proporciona una expresión funcional para el número de palabras de longitud $N$ con un determinado número de AA, AC, ... y del TT, y por lo tanto para el que desee $\Delta G$.

Yendo un paso más allá, se puede utilizar generalizada de Euler-Maclaurin identidades para la evaluación de las sumas de las funciones de celosía polytopes para caracterizar el espacio de todos (cíclica) de palabras de longitud $N$ $\Delta G$ acostado en un rango estrecho. De esta forma, se completa la teoría de la estructura y se muestra cómo se puede construir secuencias de ADN haber deseado termodinámicos y propiedades combinatorias. Entre otras cosas, he usado esto para el diseño de un protocolo para (como David Harlan Madera) "la simulación de recocido simulado por recocido de ADN".

Answer 2

Para firma de gráficos tenemos una matriz interesante-árbol teorema. Firmado un gráfico es un gráfico con el adicional de la estructura de borde de signos (pesos) ser +1 o -1. Decimos que un ciclo en una firma gráfica es equilibrado si el producto de los bordes en el ciclo es +1. Una firma gráfica es equilibrado si todos sus ciclos están en equilibrio. Otherise, decimos firmado un gráfico es desequilibrada.

Decimos que un subgrafo $H$ conectado un firmada gráfico de $G$ es un esencial de árbol de expansión de $\Gamma$ si

1) $\Gamma$ es equilibrado y $H$ es un árbol de expansión de $G$, o

2) $\Gamma$ está desequilibrada, $H$ es un abarcan subgrafo y cada uno de los componentes de $H$ es un unicyclic gráfico con el único ciclo de tener signo -1.

La matriz de árbol teorema de signos gráficos se expresa de la siguiente manera:

Deje $G$ ser conectado firmado el gráfico de $N$ vértices y deje $b_k$ el número de esencial que abarca subdiagramas que contengan $k$ ciclos negativos. Entonces

$$ \det(L(G))=\sum_{k=0}^n 4^k b_k.$$

Para algunas referencias:

T. Zaslavsky, Firmado Gráficos, Discreto Appl. Matemáticas, 4 (1982), 47-74.

S. Chaiken, Una combinatoria de prueba de todos los menores de la matriz de árbol teorema. SIAM J. Algebraicas Discretas Métodos, 3 (1982), 319-329.

Firmado gráficos se utilizan en el giro de vidrio teoría y aplicaciones de la red.

Considerando mixto gráficos, que son gráficos que tienen algunos bordes como grafo, obtenemos la misma teoría. Este es inmediata, ya que la matriz definiciones son idénticas para firma de gráficos y mixto gráficos. Este parece escapar de muchas de las personas que estudia las propiedades de la matriz de mezcla de gráficos sin embargo. Ver:

R. Bapat, J. Grossman y D. Kilkarni, la generalización de la Matriz de Árbol Teorema de mezcla de Gráficos, Lin. y Mult. Lin. Álgebra, 46 (1999), 299-312.