La cantidad de métodos de 3 colores de un gráfico

Question

Dado un grafo con a $2n$ nodos, denominados por $u_1,u_2\cdots u_n$$v_1,v_2\cdots v_n$.

La gráfica está dada así: $\forall 1\le i\le n$, hay una arista entre el$u_i$$v_i$, y también hay una arista entre el $u_i$ $u_{i+1}$ $v_i$ y $v_{i+1}$($u_{n+1}$ se considera como $u_1$, así como el $v_{n+1}$). Mi pregunta es, ¿cuántos método hay para el color de la gráfica con tres colores?

Haciendo algún experimento, indicar el número de método por $C(n)$, sé que sigue una ecuación de recurrencia(lo sé por un experimento de resultado de pruebas de $n=3,4,\cdots 10$, no dando una precisión de la prueba) $C(n)=2C(n-1)+5C(n-2)-6C(n-3),C(3)=12,C(4)=114,C(5)=180$. He tratado de inducción, pero sin ninguna idea de probar esta ecuación de recurrencia, las sugerencias o soluciones son bienvenidas. Gracias por la atención!

Answer 1

Llame a los tres colores $0$, $1$, $2$. Cada peldaño $(u_i,v_i)$ de su "circular de la escalera", a continuación, puede ser de color en uno de los seis caminos $01$, $12$, $20$, $10$, $21$, $02$. Suponga $(u_0,v_0)$ es de color $01$. Cada admisible para colorear completo de la escalera, a continuación, corresponde a un camino cerrado $\gamma$ de la longitud de la $n$ comienza y termina en el nodo $01$ en los siguientes auxiliares gráfico:

Recuento de un movimiento hacia la izquierda a lo largo de una pierna de uno de los triángulos como $+1$ y un movimiento hacia la derecha como $-1$. Si $\gamma$ contiene $m\leq n$ movimientos a lo largo de un triángulo de piernas, contando $x_i\in\{-1,1\}$ $\ (1\leq i\leq m)$, a continuación, debemos tener $$\sum_{i=1}^m x_i=0\quad({\rm mod}\ 3)\ .\qquad(*)$$ Dado $m$ es fácil comprobar por inducción que el número de soluciones de $(*)$ es $$b_m={1\over3}\bigl(2^m +2(-1)^m\bigr)\ .$$

El camino cerrado $\gamma$ contienen un número par de cambios desde el exterior hacia el interior del triángulo, o viceversa. Dado $k$ $0\leq k\leq\lfloor{n\over2}\rfloor$ $2k$ saltar veces puede ser elegido en ${n\choose 2k}$ maneras.

Caer el supuesto de que el peldaño $(u_0,v_0)$ es de color $01$ por lo tanto, obtener un total de $$C(n)=6 \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} b_{n-2k}=2 \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k}\bigl(2^{n-2k}+2(-1)^n\bigr)$$ tales caminos, resp., admisible el color de nuestra circular de la escalera.

El uso de la fórmula $$2\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} x^{2k}=(1+x)^n+(1-x)^n$$ esto puede ser simplificado a $$C(n)=3^n+2(-1)^n\>2^{n+1} +1\ .$$ La conjetura de recurrencia para el $C(n)$ ahora puede comprobarse a posteriori. Sería bueno tener un "directo" prueba de ello.

Answer 2

Vamos $a_n$, $b_n$, $c_n$ y $d_n$ denotar los números de las rutas en Cristiano gráfico que comienzan a $01$ y final en $20$, $02$, $01$ y $10$, respectivamente. (Por simetría, $a_n$ $b_n$ son también los números de las rutas que comienzan en $01$ y final en$12$$21$, respectivamente). La ampliación de las rutas de acceso por uno de los bordes de los rendimientos de las siguientes recurrencias para $n\ge1$:

$$ a_n=a_{n-1}+b_{n-1}+c_{n-1}\;,\\ b_n=a_{n-1}+b_{n-1}+d_{n-1}\;,\\ c_n=a_{n-1}+a_{n-1}+d_{n-1}\;,\\ d_n=b_{n-1}+b_{n-1}+c_{n-1}\;. $$

La suma de los dos primeros de la mano derecha lados es igual a la suma de los dos últimos derecha lados, por lo $a_n+b_n=c_n+d_n=:f_n$$n\ge1$; luego suma rendimientos $f_n=3f_{n-1}$$n\ge2$.

Restando la segunda ecuación de la primera rendimientos $a_n-b_n=c_{n-1}-d_{n-1}$$n\ge1$, y luego restando el cuarto de la tercera y la sustitución de $a_{n-1}-b_{n-1}$ rendimientos $g_n=-g_{n-1}+2g_{n-2}$$n\ge2$,$g_n:=c_n-d_n$.

Con $a_0=0$, $b_0=0$, $c_0=1$, $d_0=0$ y $a_1=1$, $b_1=0$, $c_1=0$, $d_1=1$ los valores iniciales son $f_1=1$, $g_0=1$, $g_1=-1$, y las recurrencias pueden ser resueltos por el método aplicado en mi otra respuesta. El resultado es $3f_n=3^n$$3g_n=1-(-2)^{n+1}$, y así

$$C(n)=6c_n=3(f_n+g_n)=3^n-(-2)^{n+1}+1\;.$$

Answer 3

El método estándar para resolver este tipo de recurrencia es hacer que el ansatz $C(n)=\lambda^n$ y resolver el resultante ecuación característica, $\lambda^3-2\lambda^2-5\lambda+6=0$. La solución de $\lambda=1$ puede ser adivinado y deja fuera, dejando $\lambda^2-\lambda-6=0$ con soluciones de $\lambda=-2$$\lambda=3$. La solución general se obtiene como una superposición lineal de estas soluciones, $C(n)=c_1+c_2(-2)^n+c_33^n$. Sus valores iniciales rendimiento de un sistema de ecuaciones lineales,

$$ \begin{align} c_1-8c_2+27c_3=12\;,\\ c_1+16c_2+81c_3=114\;,\\ c_1-32c_2+243c_3=180\;, \end{align} $$

con la solución $c_1=1$, $c_2=2$, $c_3=1$. Por lo tanto el número de coloraciones es

$$C(n)=1-(-2)^{n+1}+3^n\;.$$

Este resultado también está en lo correcto $n=1$ $n=2$ (si interpretamos los bordes de $u_1$ $u_1$ $v_1$ % # % en el caso de $v_1$ como auto-bucles de la prevención de los vértices de tener cualquier color), por lo que, a posteriori, la solución de la recurrencia podría haber sido simplificado mediante el uso de $n=1$, $C(1)$ y $C(2)$ como valores iniciales en su lugar.