Lo que estoy haciendo para la Navidad? Secret Santa y la teoría de grafos

Question

Yo vivo con cuatro personas, que por suerte no paso mucho tiempo en la asignatura de matemáticas.se. Hemos decidido que este año nos gustaría hacer un Santa Secreto. Podemos representar la disposición de quién está comprando para quien el uso de un grafo dirigido $G = (V,E)$. $V = \{\alpha,\beta,\gamma,\delta,\varepsilon\}$ es nuestro conjunto de vértices, y $(u,v) \in E$ fib $u$ es comprar un regalo para $v$. Hemos decidido producir este gráfico por escrito nuestros nombres en pedazos de papel, arrastrando los pies alrededor de ellos, y cada uno de escoger uno. Si el nombre que dibujar no es válida, entonces dibujamos otro pedazo de papel. Nuestras reglas de validación fueron como sigue:

• Ningún participante podrá comprar por sí mismos - por lo $(v,v) \notin E$
• $\delta$ $\varepsilon$ son una pareja, que se va a comprar uno para el otro por separado de la santa secreto. En lugar de perder los bordes, se ha decidido a mostrar cada uno de otros no válido, por lo $(\delta,\varepsilon) \notin E$ $(\varepsilon, \delta) \notin E$
• Cada persona compra de exactamente una de la otra persona - por lo $deg_{in}(v) = deg_{out}(v) = 1$

Sé que he comprado. Puedo deducir toda la estructura de la gráfica a partir de esta información?

Puedo reducir el gráfico de cuatro posibles estructuras, publicado como una respuesta parcial, que ya me da un bastante gran cantidad de información. Yo no creo que pueda conseguir más información sobre el estado de la gráfica simplemente de saber que me voy a comprar, pero tengo algo de información sobre el orden en el que los nombres fueron sorteados, y saber que nunca tuvimos que volver a barajar.

Basado en la información proporcionada por el sorteo, ¿cómo puedo encontrar la probabilidad de cada una de las posibles Secreto de Santa arreglos?

Respuesta parcial - de los posibles gráficos de dar:

En estos gráficos, los nodos etiquetados $\delta/\varepsilon$ o $\varepsilon/\delta$ va a tomar diferentes valores, que conduce a cuatro posibles gráficos. En ambas situaciones, $\alpha$ tiene más natural de la información. Puede ser obtenido a partir del conocimiento del sorteo?

Answer 1

Desde $\epsilon$$\delta$, para todos los intensivos de fines, simétrica, no hay manera de saber cuál de los dos está dando un regalo a menos que usted pida a uno de ellos y decide revelar a usted, ya que la persona que está dando no es que (no sé cómo estricta o confidencial de su Santa Secreto es). Pero, en la probabilidad:

Tiene una sencilla forma de grafo dirigido con 5 aristas y 5 vértices que no están necesariamente conectados. Por lo tanto, hay sin condiciones previas, ${20\choose 5}$ posible gráficas. Sin embargo, sabemos que uno de los bordes (específicamente $\alpha\to\beta$) y que los dos bordes son imposibles. Por otra parte, sabemos que el $\beta$ debe tener grado $2$. La posibilidad de $\beta\to\alpha$ es impedido por el hecho de que esta fuerza de $\epsilon\to\delta$ o vice-versa, mientras que $\beta\to\gamma$ no puede suceder porque entonces tendríamos $\delta\leftrightarrow\epsilon$. Así que tenemos una $\frac{1}{2}$ de probabilidad de $\beta\to\delta$ $\epsilon$ cada uno. Deje $\beta\to X$ donde $X\in\{\delta,\epsilon\}$. Luego, con sus restricciones, $X\to\alpha$ $\gamma$ son las únicas posibilidades, de nuevo con un $50/50$ de probabilidad de cada uno. Si $X$ mapas a $\alpha$ o $\gamma$ únicamente determina la gráfica, como sus representaciones ilustran. Todo esto para decir que, cada una de las cuatro gráficas que usted presente es igualmente probable suponiendo que el empate fue al azar.