Circuitos de Euler para el gráfico

Question

¿Cuántos circuitos de Euler diferentes hay en el gráfico que comienza en $A$ y luego visita $D$ como el siguiente vértice inmediato?

Mi respuesta es $16$ y supongo que he contado todos los circuitos de Euler posibles. Me pregunto si he omitido otros caminos posibles, y me gustaría saberlo.

Answer 1

Creo que $16$ parece ser el valor correcto. También he contado y obtenido $16$ como respuesta.

Answer 2

Tienes razón.

Obsérvese que dicho circuito de Euler debe utilizar $e_2$ . Así que se puede reducir el problema a encontrar el número de Euler senderos a partir de $C$ y terminando en $A$ en $G - D$ .

Piensa en un camino de Euler en este caso como una secuencia de cinco aristas $e_{i_1}e_{i_2}\cdots e_{i_5}$ . Tal vez una de las formas más fáciles de contar es señalar una arista, digamos $e_3$ y contar el número de secuencias válidas con $e_3$ en la primera posición, luego en la segunda, y así sucesivamente. Como empezamos en $C$ se puede notar que una secuencia que representa un camino de Euler sólo puede tener $e_3$ en la primera, tercera y quinta posición. Se obtiene

1. Primero: $4$ senderos. Recorrido $e_3$ . Hay $4$ formas de pasar de $A$ a $C$ , de vuelta a $A$ , es decir, dos opciones de $A$ a $B$ , dos opciones de $B$ a $C$ y el camino de vuelta está determinado.

2. Tercero: $8$ senderos. Puedes ir $CBCABA$ de los cuales hay cuatro formas, o $CBACBA$ otras cuatro formas.

3. Quinto: $4$ senderos, similar al primer caso.

Aunque esta respuesta es larga, al menos al pensar de esta manera puedes estar seguro de que has agotado todas las posibilidades en tu recuento. Creo que en general es difícil ( $NP$ -) para contar el número de circuitos de Euler en un grafo no dirigido dado.