Encontrar la trayectoria de Euler utilizando potencias de adyacencia

Question

Contexto: Estoy estudiando un curso de introducción a la Matemática Aplicada Discreta, y soy nuevo en el contexto de los gráficos.

Sabiendo que un grafo se puede representar como una matriz de adyacencia, digamos que tenemos el grafo

$G = \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0\\ \end{bmatrix}$

Sé que podemos mirar $G^n$ para encontrar el número de caminos que conectan dos vértices cualesquiera dados por $n$ caminos recorridos. Tratando de usar $G^{vertexes}$ En este caso, pensé que podía comprobar cuántas soluciones posibles para un circuito de Euler había en función del vértice elegido inicialmente.

Rápidamente me di cuenta de que había un fallo en mi pensamiento: esto permitía que tanto las trayectorias como los vértices se repitieran en la trayectoria, lo que no está permitido en la definición de un ciclo euleriano.

Sé que puedo ver si existe un ciclo euleriano contando el número de vértices del grafo que tienen aristas Impares y pares que unen otros vértices.

• Si todos los vértices tienen un número par, o exactamente dos impares, de líneas conectadas, debe existir al menos un ciclo euleriano.
• Si hay exactamente uno, o más de dos vértices desiguales, el ciclo euleriano no existe.

Esto no me dice nada sobre dónde debe estar la posición inicial (a no ser que haya dos desiguales), ni la trayectoria del camino.

¿Existe alguna propiedad que pueda utilizar para limitar la cantidad de repeticiones de caminos/vértices, utilizando la técnica de la exponenciación, para ver qué posición inicial es válida? ¿Hay alguna otra cosa que deba saber sobre los circuitos eulerianos?

Answer 1

Mi comentario anterior con las matrices de probabilidad de la cadena de Markov era un poco apresurado y sólo me daba el número exacto en algunos casos especiales.

---

En su lugar, le presentaré un algoritmo más exacto.

Necesitaremos un par de bloques de construcción :

1. Matriz de adyacencia $\bf M$ de dimensión $N\times N$ .
2. Multiplicación de matrices.
3. Producto de Hadamard/Schur (por elementos) $(\otimes)$ .
4. Una matriz específica de eliminación de circuitos ${\bf O}={\bf 1 1} ^T{\bf - I}$ , Donde $\bf 1$ es el vector columna de $N$ los.

( $\bf O$ es básicamente una matriz unitaria invertida lógicamente, $0$ en la diagonal y $1$ en todos los demás lugares)

Ahora define la matriz : $$\cases{{\bf T}_0 = {\bf M}\\{\bf T}_{k+1} = {\bf M}({\bf O \otimes T}_k)}$$

A continuación, calcula la suma $${\bf s}=\sum_{k=0}^{N-1} \text{diag}({\bf T}_k)$$

Donde diag es el operador que hace un vector a partir de los elementos diagonales. Por ejemplo $$\text{diag}\left(\begin{bmatrix}1&2&13\\2&3&4\\13&4&5\end{bmatrix}\right) = [1,3,5]^T$$

Puede observar que si $\bf O$ era la matriz llena de unos entonces ${\bf T}_k = {\bf M}^{k-1}$ (la "potencia" ordinaria de la multiplicación de matrices iteradas), que es lo que te diste cuenta que no podía ser el caso. Así que sólo tuvimos que hacer una modificación bastante menor a su primera idea.

Casi me olvido de mencionar que el $\bf s$ El vector será un vector que contendrá los enteros de cuántas trayectorias desde la posición hasta la misma posición pasando por cualquier nodo en el camino como máximo 1 vez .