Complejidad de la selección de entradas en la matriz para encontrar clases

Question

Supongamos que tengo una matriz con entradas $x$ o $y$, donde el número de filas = número de columnas = $n$.Si quiero seleccionar/circular $n$ entradas tales que para cada fila, solo se encierre exactamente una, para cada columna, también se encierre exactamente una, y de modo que todas las entradas envueltas en un círculo sean solo $x$ (si existe tal círculo de entradas), ¿a qué clase de complejidad pertenece?¡Gracias!

Answer 1

Dejar $u$ ser el conjunto de filas de la matriz dada y $v$ el conjunto de columnas.Para cada $x$ en fila $yo$ y columna $j$, agrega un borde entre la fila $yo$ y columna $j$.tendrás un gráfico bipartito (no ponderado) $G=(U,V,E)$.El problema es encontrar un combinación perfecta, que es básicamente lo mismo que encontrar la coincidencia máxima de $g$.

Hay varios algoritmos que calculan la máxima coincidencia de cardinalidad.Por ejemplo, El algoritmo Hopcroft-Karp corre en $O(\max(|E|\sqrt {|V|}, |V|^2)$.

Entonces, podemos decir que la clase de complejidad del problema en la pregunta está en $O(n^{2.5})$ desde $|E|\le n^2$ y $|V|= 2n$.