Dilema del compositor - Teoría de grafos

Question

Soy un compositor. Yo tengo 10, 30 segundos secciones musicales. La orquesta toca 5, cinco son interpretadas por un solista. Me gustaría darles cada una de las opciones. He escrito la pieza de manera que cada sección y los flujos en 2 secciones que los otros juegan.

La orquesta "mappings", 1=>B&B y D 2=>C + D 3=>C&E 4=>A&B 5=>A&E. El solista asignaciones son a=>2&4 B=>2&5 C=>3&4 D=>1&3 E=>1&5

Opcional estipulación: Los grupos pueden jugar en el mismo artículo dos veces, pero se debe elegir una no reproducidos sección cuando se les da la opción.

Me gustaría que la pieza para empezar con la orquesta tocando la sección 1 y el final cuando el solista ha jugado todos los A-E. El problema es que cuando escribo un diagrama de flujo, alrededor del 50% del tiempo hay una sección en la que el solista no ha jugado después de las 10 de la espalda y forths. Además, muchas maneras de salir adelante, nunca encontrará esta última sección

Así que mi pregunta es, hay alguna manera de cambiar las asignaciones (reescribir partes de la pieza), por lo que el solista se llega a jugar cada uno de sus 5 secciones.

Gracias por su tiempo.

Answer 1

Bueno, he aquí una gráfica de la situación, donde el buen sonido de los bordes están incluidos. Se trata de un bonito gráfico, si usted me pregunta. Supongo que esto es básicamente lo que su diagrama de flujo de la era.
y nuestro objetivo es encontrar los caminos, visitando cada vértice (al menos una vez). Esta es una buena visualización del problema. Actualmente hay exactamente dos rutas válidas:

1-D-3-E-5-A-4-B-2-C
1-D-3-E-5-A-2-C-4-B

Estas son las únicas vías que utiliza cada sección exactamente una vez. Si usted quiere estar seguro de que, el aviso de que un ciclo no se puede iniciar 1-B-2, ya que entonces habría que visita D, 3 - momento en el que podrían ir a la E, pero, a continuación, C sería inalcanzable, o podría ir a C-4-A, pero entonces sería forzado a repetir. También no podía empezar 1-B-5, a partir de entonces se iba a ir a la E, y se obligó a repetir a partir de entonces, o ir a Una de 2 (ya va para 4 obligaría a ir a la B siguiente), pero luego pudimos demostrar que no habría inutilizado saliente rutas de 4, lo que significa que tendría que terminar ahí, que es un problema ya que si exactamente 10 secciones fueron utilizados, terminaría con el solista. Esto es suficiente para mostrar que no sería capaz de empezar 1-B sin repetir. Del mismo modo, no se puede iniciar 1-D-3-C, ya que significaría cuando la orquesta tocaba la sección 2, se tendría que repetir. Esto es suficiente para mostrar cualquier ruta de acceso debe iniciar 1-D-3-E-5-Un y sólo hay dos caminos a partir de ahí.

Hay ciertamente más rutas de acceso al relajar sus condiciones como usted tiene, y si usted piensa acerca de por qué ciertas rutas están fallando, puede intentar mover los bordes de ayudar un poco; tal vez evitar los ciclos entre dos secciones de aumentar el número de pedidos para reproducir la música. Este es sin duda algo que tienes que jugar con más de algo que se puede resolver con rigor, sin embargo, pero si usted acaba de tratar de averiguar donde las cosas van mal para un montón de rutas de acceso, usted puede averiguar lo que usted necesita para cambiar a resolver esos problemas y, al menos, crear más rutas de acceso a través de la gráfica.

También podría comenzar con dos conjuntos de cinco puntos, y empezar a dibujar caminos de longitud $10$ a través de ellos, alternando entre los dos conjuntos (solista y orquesta) - que sería posible órdenes para reproducir la pieza - y continuamente se añaden nuevas rutas de acceso hasta que tuvo cada uno de los nodos de la gráfica con exactamente $2$ bordes salientes. Si haces esto bien, se debe generar un gráfico con más potencial de rutas a través de ella -, pero dado que ya has escrito la pieza, me imagino que cambiar totalmente la estructura de la pieza, no es una gran opción.