Grafo bipartito que empareja como problema.

Question

Deje $A=\{a_1,a_2, ..., a_n \}$ $B=\{b_1,...,b_m\}$ finita de conjuntos. También se $A_1,...,A_k\subset A$ están cubriendo de $A$ $B_1,...,B_t\subset B$ están cubriendo de $B$. Deje $V$ ser un conjunto de pares de $A_xB_y$, de modo que para cada una de las $a_i\in A$ $b_j \in B$ no es un porcentaje ($A_xB_y$ par en $V$$a_i \in A_x,b_j\in B_y$.

Esto es similar a la perfecta coincidencia en bipartita de gráficos, pero en lugar de un solo vértice tomamos algunas conjunto de verticies y coincidir con ellos de otro conjunto. La pregunta es ¿cuál es el tamaño mínimo de $V$, de modo que perfecto maridaje que existe. Podemos tomar todas las $A_i$ $B_j$ y ya se están cubriendo vamos a tener la condición satisfecho. Pero se utilizará $tk$ pares.

¿Alguien sabe algo de teoría acerca de este problema? Estoy pensando que esto puede ser reducido a bipartito de juego gráfico problema. Necesito algoritmo de encontrar el conjunto mínimo $V$.

Él es el ejemplo de:

Deje $A=B=\{0,1,2\}$

$A_1=B_1=\{0,1\}$

$A_2=B_2=\{0,2\}$

$A_3=B_3=\{1,2\}$

Si tomamos $V=\{A_1A_1,A_1A_2, A_2A_1,A_2A_2 \}$ la condición se tendrá por satisfecho. Todos los pares serán cubiertos.

$(0,0)\in A_1A_1$

$(0,1)\in A_1A_1$

$(0,2)\in A_1A_2$

$(1,0)\in A_1A_1$

$(1,1)\in A_1A_1$

$(1,2)\in A_1A_2$

$(2,0)\in A_2A_1$

$(2,1)\in A_2A_1$

$(2,2)\in A_2A_2$

Se puede ver que $V=\{A_1A_2, A_2A_3, A_3A_1\}$ es la respuesta.

---

A partir de los comentarios resultó que este problema es NP-duro, así que voy a añadir algunas condiciones para obtener la respuesta de mi problema original.

Deje $A=B$ y todos los $A_i$ tienen el mismo tamaño. Si añadimos esta condiciones, es posible dar cota superior para $V$. De hecho estoy tratando de conseguir el mínimo de la cubierta de la siguiente gráfica:

Considere el espacio vectorial $F_2^3$

$A=B=\{(000), (001), (010), (011), (100), (101), (110)\}$

$A_i$ es solución de la ecuación. Es coset y contiene $4$ vectores.

$A_1=\{x_1=0\}=\{(000), (001), (010), (011)\}$

$A_2=\{x_2=0\}$

$A_3=\{x_3=0\}$

$A_4=\{x_1+x_2=1\}$

$A_5=\{x_2+x_3=1\}$

$A_6=\{x_1+x_3=1\}$

$A_7=\{x_1+x_2+x_3=0\}$

He mostrado que la cobertura con el tamaño de la $6$ existe y necesita ayuda para demostrar que es mínima. Aquí está cubriendo:

$V=\{A_7A_3, A_3A_4, A_5A_1, A_2A_5, A_1A_7, A_7A_2 \}$

Answer 1

Vamos a escribir $A_i$ como conjuntos de números: $$ A_1 = \ {0,1,2, 3} \ A_2 = \ {0,1,4, 5} \ A_3 = \ {0,2,5, 6} \ A_4 = \ {2,3,4, 5} \ A_5 = \ {1,2,5, 6} \ A_6 = \ {1,3,4, 6} \ A_7 = \ {0,3,5, 6} \ $$ (espero he calculado todo bien:)). Es fácil ver que $A_i \cup A_j\ne A$, por lo que cada número debe ser de al menos $3$ "componente izquierdo" establece, por lo que tenemos si el número de pares es $k$ $$4k\ge21$% $# %k\ge6 de #%.