Domino los trenes preguntas

Question

Un tren es un extremo a la disposición de las fichas de dominó tal que el resto de las mitades de los vecinos de fichas de dominó tienen el mismo número de puntos.

Un "doble-$n$" domino tiene uno de cada uno de los posibles domino el uso de números enteros de $0$$n$, donde el orden no es una característica distintiva (de lo que no hay separada $0$-$2$ y $2$-$0$ dominó, por ejemplo).

Deje $f(n)$ ser el más pequeño número de trenes que puede ser formado a partir de las fichas de dominó en un doble -$n$, de tal manera que cada domino se utiliza en exactamente un tren. ¿Cuáles son los valores de $f(12)$$f(15)$?

---

¿Cómo puedo abordar este problema con la teoría de grafos?

Answer 1

Esta pregunta, en realidad, le pide que complete gráficos tienen un ciclo Euleriano. Para completar gráficos con un ciclo Euleriano la respuesta es 1. Para completar gráficos sin un ciclo Euleriano que usted necesita para encontrar una descomposición de un número mínimo de caminos. Las fichas de dominó de la forma $i,i$ puede ser exprimido en cualquier momento que usted visita vértice $i$. Se puede tomar desde allí??

Uno más de sugerencia: en la completa gráficos sin un ciclo Euleriano, cada vértice de grado impar debe ser el punto final de una ruta.

Answer 2

Tenemos que mirar a Euleriano rutas de acceso, y utilizar el conocido resultado sobre ellos usando impares y pares de vértices. Esto hace que $f(12)=1$$f(15)=8$.

Los trenes son bastante básicas, en el extraño caso (un número par de vértices) - nos 'desconectar' $\dfrac{k+1}{2}$ solo borde discontinuo gráficos, el resto de grafo es Euleriano y puede tener una ruta de acceso se unió a él en un tren, el resto forma individual trenes.

Una tal vez el más interesante de respuesta se puede llegar por la definición de un tren como un rotacionalmente simétricas ruta de acceso para el grafo completo, por ejemplo, para $n=8$ tenemos:

Si hacemos girar la imagen cuatro veces llegamos a:

lo que nos da el mínimo de cuatro trenes como sea necesario.