Seleccionar un elemento de cada uno de muchos conjuntos de modo que no haya dos elementos iguales.

Question

Seleccionar un elemento de cada uno de muchos conjuntos de modo que no haya dos elementos iguales.

Matemáticas
np-completo
combinatoria
teoría elemental de conjuntos

jake mconley

Supongamos que tenemos un conjunto finito $A$ cuyos elementos son subconjuntos de otro conjunto finito $B$ $\left (\epsilon \in A \implies \epsilon \subseteq B \right )$ . A continuación, supongamos que queremos seleccionar hasta un elemento de cada conjunto $\epsilon \in A$ tal que no hay dos elementos seleccionados de cualquiera de estos conjuntos $\epsilon$ son iguales. ¿Cómo haríamos para encontrar el número máximo de elementos que podemos seleccionar de estos conjuntos de manera que se satisfagan estas condiciones?

Obviamente, este número máximo de elementos está acotado por el mínimo del tamaño de $A$ y el tamaño de $B$ , pero supongamos que conocemos el contenido de cada uno de los conjuntos $\epsilon$ . ¿Hay algún método que se pueda usar para obtener más información sobre este máximo de manera oportuna, o este problema toma tiempo para resolverlo?

Esteban Donovan

Esto suena a Sudoku, puede ser útil ver si puedes reducir Sudoku a esto, en cuyo caso creo que debe ser NP-difícil. Dicho esto, ha pasado un tiempo desde que tuve que pensar en NP para poder equivocarme.

Respuestas (1)

Seleccionar un elemento de cada uno de muchos conjuntos de modo que no haya dos elementos iguales.

Esto suena a Sudoku, puede ser útil ver si puedes reducir Sudoku a esto, en cuyo caso creo que debe ser NP-difícil. Dicho esto, ha pasado un tiempo desde que tuve que pensar en NP para poder equivocarme.

Guardar marca · Answer 1

Puede resolver esto usando el flujo máximo en tiempo polinomial.

Considere un gráfico dirigido con nodos $\{S, F\} \cup A \cup B$ . Los bordes, todos los cuales tienen peso 1, son $\{S \to a | a \in A\} \cup \{a \to b | b \in a, a \in A\} \cup \{b \to F | b \in B\}$ .

Entonces el flujo máximo de $S$ a $F$ es la respuesta a tu problema.

Tenga en cuenta que para el flujo máximo, si todos los pesos de los bordes del gráfico son números enteros, el flujo máximo tendrá un flujo de números enteros en cada borde. Es por eso que esta reducción funciona.

Editar:

De hecho, esto se puede considerar como un caso especial de coincidencia bipartita máxima.

Seleccionar un elemento de cada uno de muchos conjuntos de modo que no haya dos elementos iguales.

jake mconley

Esteban Donovan

Respuestas (1)

Guardar marca

¿Cuántas permutaciones casi perfectas hay?

Una pregunta sobre un caso especial del principio de inclusión-exclusión

prueba combinatoria de identidad que involucra multiconjuntos

t¿De cuántas maneras podemos dividir un conjunto S en dos subconjuntos bajo las siguientes restricciones?

Cuestión de combinatoria y teoría de conjuntos

Sea A={1,2,3,4,5,6,7,8,9,0,20,30,40,50}A={1,2,3,4,5,6,7,8 ,9,0,20,30,40,50}A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}. 1. ¿Cuántos subconjuntos de tamaño 2 hay? 2. ¿Cuántos subconjuntos hay en total?

Reducción P/NP (ciclo hamiltoniano a TSP)

Si A={x1,x2,x3,…,xn}A={x1,x2,x3,…,xn}A= \{ x_1 , x_2 , x_3 , \ldots , x_n \}. ¿Cuántos subconjuntos hay?

Encontrar el elemento N en una lista de todos los números posibles

número de formas de elegir conjuntos de números enteros