Una vez estaba interesado en el regreso caminos en grafos cúbicos . Pero estoy aún más curioso que el número de formas sin retroceder, que significa hacer un paso adelante y uno atrás (que pueden ser bueno para el baile), por ejemplo, $1\to 2\to 1$.
La solución con las potencias de la matriz de adyacencia no parece funcionar aquí. ¿Alguien sabe una solución?
Llame a un paseo reducido si no dar marcha atrás. Si $A=A(X)$ para un gráfico de $X$, definir $p_r(A)$ a ser la matriz (de la misma orden de las $A$) que $(p_r(A)_{u,v})$ es el número de la reducción de los paseos en $X$$u$$v$. Observar que $$ p_0(A)=I,\quad p_1(A) =A,\quad p_2(A) = A^2-\Delta, $$ donde $\Delta$ es la matriz diagonal de valencies de $X$. Si $r\ge3$ tenemos la recurrencia $$ Ap_r(A) = p_{i+1}(A) +(\Delta-I) p_{i-1}(A). $$ Estos cálculos se realizaron en primer lugar por Norman Biggs, quien observó la implicación de que $p_r(A)$ es un polinomio en a$A$$\Delta$, de grado $r$$A$.
Si $X$ es cúbico, $\Delta=3I$ y queremos que los polinomios $p_r(t)$ la satisfacción de la recurrencia $$ p_{i+1}(t) = tp_r(t)-2p_{i-1}(t). $$ con $p_0=1$$p_1=t$. Si mis cálculos son correctos, entonces $2^{-r/2}p_r(t/\sqrt{2})$ es un polinomio de Chebyshev.
Usted puede hacerlo con una matriz de adyacencia, pero los estados son ahora las combinaciones de los nodos y de donde vinieron. Aparte de la partida de vértice, por un cúbicos gráfica hay tres veces más. No es un extra para la puesta en vértice como no viene de ninguna parte para el inicio. El número de longitud de $n$ rutas de volver a empezar es la suma de los tres estados diferentes que representan el inicio de la $n^{\text{th}}$ de la potencia de esta matriz.
Agregado: Si su cúbicos gráfico es $K_4$ con nodos 1,2,3,4 y se empieza en 1, los estados se $1(start), 1 (came from 2), \ldots 2(came from 1), 2(came from 3),\ldots 4(came from 3)$, para un total de $13$ de ellos. Se calcula una matriz de adyacencia como de costumbre. Cada estado tendrá tres salientes y bordes (excepto para el inicio de uno) tres o cuatro entrantes bordes. A continuación, puede tomar los poderes de ella para encontrar el número de rutas de acceso a cualquier estado. Si desea rutas de regreso a $1$ de la longitud de la $n$, agregar 1 (venía de 2), 1 (vino de 3), y 1 (vino de 4) los valores de la $n^{\text{th}}$ de la potencia de la matriz de adyacencia.
Como en Chris Godsil respuesta, voy a utilizar $A$ para denotar la matriz de adyacencia y $\Delta$ para denotar la matriz diagonal de un vértice grados.
Un bonito estándar de inclusión-exclusión enfoque puede ser formulada de la siguiente manera. Definir $P(a,b,n,\{j_1,\ldots,j_k\})$ a ser el conjunto de rutas de $a$ $b$de la longitud de la $n$ en el que cada uno de los pasos de $j_1,\ \ldots,\ j_k\in\{2,3,\ldots,n\}$ invierte el paso anterior. A continuación, el número de caminos de longitud $n$ sin cambios es $$ \lvert P(a,b,n,\{\})\rvert-\sum_{j=2}^n\lvert P(a,b,n,\{j\})\rvert+\sum_{2\le j<k\le n}\lvert P(a,b,n,\{j,k\})\rvert-\sum_{2\le j<k<\ell\le n}\lvert P(a,b,n,\{j,k,\ell\})\rvert+\ldots $$
Ahora, la tarea es calcular los $\lvert P(a,b,n,\{j_1,\ldots,j_k\})\rvert$ general $\{j_1,\ldots,j_k\}$. Sabemos que $\lvert P(a,b,n,\{\})\rvert$ $(a,b)$ elemento $A^n$. Desde una reversión en el paso $j$ implica que el mismo vértice es visitado después de la $(j-2)^\text{nd}$$j^\text{th}$, $\lvert P(a,b,n,\{j\})\rvert$ $(a,b)$ elemento $A^{j-2}\Delta A^{n-j}=A^{j-2}(3I)A^{n-j}=3A^{n-2}$.
Se complican las cosas cuando hay múltiples reversiones. Considerar el conjunto de caminos con $k-1$ consecutivos de retrocesos, $k\ge2$, comenzando en el paso $j$, $$P(a,b,n,\{j,j+1,j+2,\ldots,j+k-2\}).$$ Si $v_i$ es el vértice visitado después de la $i^\text{th}$ paso $v_{j-2}=v_j=v_{j+2}=v_{j+4}=\ldots$ (llamamos a esto el incluso de la secuencia) y $v_{j-1}=v_{j+1}=v_{j+3}=v_{j+5}=\ldots$ (llaman a esto la extraña secuencia). En el caso de que $k$ es incluso, el vértice visitado después de la reversión final, $v_{j+k-2}$, es en el de la secuencia. Esta situación es similar a la $k=2$ de la situación analizada en el párrafo anterior y el número de rutas es el $(a,b)$ elemento de $$ A^{j-2}\Delta^{n-(k-2)-j}=A^{j-2}(3I)A^{n-(k-2)-j}=3A^{n-k}. $$ Si $k$ es impar, entonces $v_{j+k-2}$ es en la extraña secuencia y el número de $k$-paso de rutas de unirse a $v_{j-2}$ $v_{j+k-2}$es el mismo que el número de paso de rutas de unirse a $v_{j-2}$$v_{j-1}$, es decir, está dada por la matriz de adyacencia. De ahí que el número de $n$-paso de rutas de unirse a $a$ $b$ $(a,b)$elemento de $$ A^{j-2}AA^{n-(k-2)-j}=A^{n-k+1}. $$
En el caso más general tenemos que manejar conjuntos de rutas tener varias secuencias de consecutivos de retrocesos. Un conjunto de inversiones que contiene varias secuencias puede ser reducido a las longitudes de las secuencias. Así, por ejemplo, si $n=10$ y el conjunto de cambios es $\{2,3,4,6,9,10\}$, luego de este conjunto puede ser representado como la suma de $4+2+1+3$ desde
Un segundo ejemplo: el conjunto de las reversiones $\{3,6,7,8\}$ está representado por la suma de $1+2+1+4+1+1$ (de nuevo con $n=10$). El conjunto de cambios es representado por la suma $1+1+\ldots+1$ ($n$ términos). Desde cada inversión agregada para el conjunto combina dos términos en la suma, un conjunto de $r$ reversiones está representado por una suma de $n-r$ términos.
Ahora vemos lo que se necesita hacer para calcular $$ \sum_{2\le j_1<\ldots<j_r\le n}\lvert P(a,b,n,\{j_1,\ldots,j_r\})\rvert. $$ Representar cada conjunto $\{j_1,\ldots,j_r\}$ por una suma de enteros positivos por un total $n$. El número de longitud de $n$ rutas de $a$ $b$correspondiente a ese conjunto es igual a la $(a,b)$ elemento del producto $3^eA^o$ donde $e$ es el número de incluso los términos en la suma y $o$ es el número impar de términos en la suma. Ejemplos: la longitud de la $10$ rutas con reveses $\{2,3,4,6,9,10\}$ son enumerados por $(3I)(3I)AA$; aquellos con reveses $\{3,6,7,8\}$ son enumerados por $A(3I)A(3I)AA$.
Sigue a enumerar las sumas de $n-r$ términos positivos por un total $n$. La respuesta es un coeficiente binomial, pero necesitamos enumerar nuestra sumas de acuerdo a los números de pares e impares términos. Aquí es donde las cosas se ponen difíciles. Hacer las definiciones $$ \begin{aligned} \mathcal{E}&:=\text{sum of even terms,}\\ \mathcal{J}&:=\frac{1}{2}\mathcal{E},\\ \mathcal{O}&:=n-2\mathcal{J}=\text{sum of odd terms.} \end{aligned} $$ Tenga en cuenta que la paridad de la suma de los impares términos de la paridad del número de términos raros. Por lo tanto $\mathcal{O}-o$ es incluso y definimos $$ \mathcal{K}:=\frac{\mathcal{S}-o}{2}, $$ que es la suma de los números obtenidos restando $1$ de cada uno de los términos raros y, a continuación, reducir a la mitad. Esto implica $$ \begin{aligned} o&=\mathcal{O}-2\mathcal{K}=n-2\mathcal{J}-2\mathcal{K}\\ e&=n-r-o=2\mathcal{J}+2\mathcal{K}-r. \end{aligned} $$ Desde $\mathcal{J}$ es la suma de $e$ términos positivos, $e\le\mathcal{J}$ y, por tanto,$\mathcal{K}\le(r-\mathcal{J})/2$.
Ahora por un estándar de estrellas-y-bares argumento, el número de sumas de $e$ positivo incluso los números de un total $\mathcal{E}$ es $$ \binom{(\mathcal{J}-e)+(e-1)}{\mathcal{J}-e}=\binom{\mathcal{J}-1}{r-\mathcal{J}-2\mathcal{K}}. $$ El número de sumas de $o$ positivo números impares por un total $\mathcal{O}$ es $$ \binom{\mathcal{K}+(s-1)}{\mathcal{K}}=\binom{n-2\mathcal{J}-\mathcal{K}-1}{\mathcal{K}}. $$ En la formación de la totalidad de la suma, el par y el impar de términos se pueden intercalar en $$ \binom{o+e}{s}=\binom{n-r}{n-2\mathcal{J}-2\mathcal{K}} $$ maneras.
La incorporación de estos resultados en la inclusión-exclusión suma da el resultado de que el número de longitud de $n$ rutas de $a$ $b$sin invertir los pasos es la $(a,b)$ elemento de $$ \sum_{i=0}^{n-1}(-1)^r\sum_{\mathcal{J}=0}^{\lfloor n/2\rfloor}\sum_{\mathcal{K}=0}^{\lfloor(r-\mathcal{J})/2\rfloor}3^{2\mathcal{J}+2\mathcal{K}-r}A^{n-2\mathcal{J}-\mathcal{K}}\binom{\mathcal{J}-1}{r-\mathcal{J}-2\mathcal{K}}\binom{n-2\mathcal{J}-\mathcal{K}-1}{\mathcal{K}}\binom{n-r}{n-2\mathcal{J}-2\mathcal{K}}. $$
Discusión: Esta respuesta no es tan bonito como el de las respuestas que se han dado por Chris Godsil y Ross Millikan, pero quería ver cómo podrían funcionar las cosas utilizando un método de contraste. Como en el método utilizado aquí, Chris Godsil la respuesta de los usos de inclusión-exclusión. Lo hace mediante la construcción del conjunto de la longitud de la $n$ caminos sin invertir pasos por la ampliación de un conjunto de rutas más cortas desde que revertir los pasos ya han sido excluidos. La fórmula resultante que involucran polinomios de Chebyshev puede ser expresada en términos relativamente simples sumas, como se discutió en un seguimiento posterior. En contraste, mi método produce un poco desagradable, el triple de la suma. La principal razón por la que puedo ver por la sencillez de Chris Godsil respuesta es que en ninguno de los términos de la inclusión-exclusión suma ¿tienes revertir los pasos que "interactuar", es decir, que son consecutivos, mientras que en mi de la solución de esto sucede y debe ser tratada.
Adenda: En mi respuesta para el seguimiento post (desplácese hacia abajo para ver la nueva respuesta), yo se derivan de la suma que recibe de Chris Godsil respuesta usando el principio de inclusión-exclusión nonrecursively. En lugar de los conjuntos de $P(a,b,n,\{j\})$, empiezo con los juegos de una definición ligeramente diferente, elegido de manera que los sets consecutivos etiquetados revertir los pasos, como $P(a,b,n,\{j,j+1\})$, están vacías. La simple suma de la forma de la respuesta se cae de forma natural.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
