Teoría de la gráfica: encontrar el número de rutas diferentes a través de un vértice en una gráfica completa

Question

Si G es un grafo completo de n vértices y u,v,w son tres vértices en el conjunto de vértices de G, entonces, ¿cuántas rutas diferentes, están ahí desde u a v que pasa a través de w?

Para los 3 vértices es simple, cada vértice tiene grado 2, una de las aristas que conduce directamente v - así que no hay solo 1 ruta de acceso.

Para 4 vértices, parece como si hay 3 caminos distintos ir a través de cualquier fijo vértice w.

Para 5 vértices cada vez es complicado y ya hay 3 bordes no va directamente a la v, pero pueden ir el uno al otro... así que he contado al menos 8 diferentes caminos hasta ahora y estoy pensando que tal vez eso es correcto - que de alguna manera tal vez por 3 vértices, hay un borde no va directamente a la v, y (la invención de una relación) 1^2 - 1 = 1, que es cierto. Para 4 vértices serían 2 bordes definidos, no va a v de modo que 2^2 - 1 = 3 que funciona. Luego de 5 vértices, el 3 de bordes definidos, no va a v me daría 3^2 - 1 = 8.

Así que en general me podía venir con una fórmula de $$(n-2)^{2} -1.$$ Pero esto es un tiro en la oscuridad y yo no tengo ni idea. Los pensamientos?

Gracias,

Brian

Answer 1

Deje $p_n$ denotar el número total de caminos entre el $u$ $v$ a través de algunos $w$. Su ruta de acceso puede tener en cualquier lugar entre el $3$ $n$ vértices. Si la ruta ha $k$ vértices, entonces no se $k-3$ opciones de vértices intermedios de la $n-3$ libre de vértices junto con $(k-2)!$ opciones de reordenamientos. Por lo tanto, en total se han $$p_n=\sum_{k=3}^n\binom{n-3}{k-3}(k-2)! = \sum_{k=3}^n\frac{(n-3)!}{(n-k)!}(k-2)$$ Esta es esencialmente la fórmula, pero no es una "forma cerrada" en términos de la función gamma incompleta si quieres.

Podemos reescribir la suma con $\ell = n-k$ $$p_n=(n-3)!\sum_{\ell=0}^{n-3}\frac{n-\ell-2}{\ell!}=(n-2)!\sum_{\ell=0}^{n-3}\frac{1}{\ell!}-(n-3)!\sum_{\ell=0}^{n-4}\frac{1}{\ell!}$$ Cada uno de los sumandos se pueden expresar en términos de la función gamma incompleta, es decir, $$k!\sum_{\ell=0}^{k-1}\frac{1}{\ell!} = ek\Gamma(k,\ 1)=ek(k-1)\Gamma(k-1,\ 1) + k$$ donde $e$ es la base del logaritmo natural y $\Gamma(k,\ 1)$ es la función gamma incompleta. Con la anterior, podemos simplificar como $$\begin{align}p_n &= e(n-2)\Gamma(n-2,\ 1)-e(n-3)\Gamma(n-3,\ 1) \\&=e(n-2)(n-3)\Gamma(n-3,\ 1)-e(n-3)\Gamma(n-3,\ 1) + n-2 \\&=e(n-3)^2\Gamma(n-3,\ 1)+n-2\end{align}$$

La secuencia comienza de $n=3$ $$1,\ 3,\ 11,\ 49,\ 261,\ 1631,\ \cdots$$