Selección de pelotas de las bolsas, con restricciones de color

Question

Supongamos que tengo N bolsas, cada una de las cuales contiene bolas de un único color. ¿Cuál es el número máximo de parejas que puedo formar sin reponer las bolas en las bolsas y con las siguientes restricciones? 1)Una pareja no puede contener bolas del mismo color (es decir, de la misma bolsa) 2)No puede haber más de una combinación de 2 colores, es decir, si ya hay un par de bolas rojas y negras no puede haber otro par de los colores mencionados.

Mi pregunta es si hay un método/fórmula simple para resolver el problema anterior. También me he dado cuenta de que se parece extrañamente al problema de la teoría de grafos de demostrar que una secuencia de grados es gráfica o no( que se puede resolver con el algoritmo de Havel-Hakimi)...

Answer 1

Suponiendo que cada bolsa tenga suficientes bolas, se puede formar $N$ -Elige 2 pares diferentes. Eso es $N(N-1)/2$ .

Answer 2

Si quieres expresarlo en términos de teoría de grafos, deja que las bolsas/colores sean vértices, y coloca una arista entre los vértices cuando sacas un par de esas bolsas. Tus restricciones equivalen a decir que tienes un gráfico simple: sin bucles y sin aristas múltiples. El máximo número posible de aristas se encuentra en el grafo completo $K_N$ y es $\binom{N}2=\frac12N(N-1)$ .

Por supuesto, esto supone que usted tiene al menos $N-1$ bolas en cada bolsa. Si no lo has hecho, el problema se vuelve sustancialmente más difícil: en efecto, estás imponiendo límites superiores inferiores a $N-1$ en los grados de al menos algunos de los vértices. En ese caso se podría utilizar el Teorema de Erdős-Gallai para determinar si tiene una secuencia de grados realizable. Si la tienes, el número máximo de pares es, por supuesto, la mitad de la suma de los grados. Si no es así, habría que encontrar la menor reducción del grado total que produzca una secuencia de grados realizable. Sospecho que se podría encontrar un algoritmo razonablemente eficiente para hacer esto, pero no he pensado mucho en ello.