Puede este algoritmo en la eliminación de 1 de un (0,1)-matriz de fallar?

Question

Seamos dado un $n\times n$ matriz que contiene sólo ceros y unos.Ahora, el objetivo es eliminar algunos 'queridos' de la matriz (es decir, reemplazarlos con ceros), de modo que en cada fila y en cada columna hay un 'uno'. Por supuesto, es preferible que lo deje como mucho '' como es posible (máxima es obviamente $n$).

Ahora, vamos a definir el siguiente algoritmo: si hay un 'uno', que está solo en una columna o en una fila, de salir de allí, y reemplazar todos los 'queridos' en su columna y fila de ceros. Repetimos el proceso como hay un solo "unos" en las filas o columnas. Si no hay ninguna sola '' a la izquierda, tomamos la primera fila o columna (la primera es contada desde arriba (por filas) y de izquierda (por columnas)) que contiene dos '' (si no hay pares, vamos a por el primer triplete y así sucesivamente). En ese par (o triplete, o ...) salimos de la primera 'uno' intacta (la primera es contado desde la izquierda para los elementos de la fila, desde la parte superior de los elementos de una columna) y el cambio de todos los demás '" en la fila y columna de la primera 'uno' en ceros. Ahora, comprobamos que hay ahora ningún single 'queridos', como se define arriba - si sí, repetimos que parte del algoritmo, si no, buscamos el primer par, los trillizos, etc. El algoritmo termina cuando todos 'queridos' son individuales, tanto en su columna y fila.

Hace este algoritmo siempre de dar la máxima cobertura, es decir, no es terminar siempre con la máxima cantidad de "unos" en la final de la matriz? En otras palabras, puede haber una matriz con una posible exclusión de algunos, que termina con $n$ usando algún otro régimen de exclusión, mientras se termina en menos de $n$ '' mediante el algoritmo descrito anteriormente?

Answer 1

No estoy seguro de si esto funciona, pero me gustaría ser dudoso.

Otra forma de expresar este problema es encontrar el máximo parcial elecciones en un bipartito gráfico. (Sólo interpretar la matriz de una matriz de adyacencia para el gráfico). Por un máximo parcial coincidencia me refiero a un máximo de tamaño conjunto de aristas hay dos con un vértice en común.

La razón de mi escepticismo es que si el algoritmo trabajado, a continuación, se daría un algoritmo para la búsqueda de la solución en la situación de la Sala de matrimonio del teorema. Su algoritmo es "monotonía" en el sentido de que añade los bordes, pero nunca se elimina, sino que todos los algoritmos que tengo visto por la Sala del teorema, que uno necesita para eliminar bordes en ciertos las circunstancias en el proceso.

El problema es, por un lado, el algoritmo procede de ninguno de los que resuelve el problema de flujo máximo en una red. Conecte una fuente para cada vértice en un lado del desdoblamiento y un lavabo para cada vértice en el otro lado. Dar a todos los bordes de la capacidad de la unidad y encontrar un flujo máximo.

Answer 2

Sí. Considere la posibilidad de una gran matriz cuadrada con dos grandes bloques cuadrados llenos queridos y un vacío fila y una columna vacía. Eliminar uno a uno a partir de cada uno de los bloques fuera de la diagonal, y el lugar un correspondiente en el vacío de la fila y la columna. Ahora tiene una fila con dos elementos, el resto se había muchos elementos, y una columna de tener sólo dos elementos, el resto se había muchos. Su procedimiento será de acuerdo con la sparesely poblada de fila y columna de la primera. Permutar las filas y columnas, de manera que el procedimiento de enlaces de las dos opciones con diferentes bloques. Ahora el resto de cada bloque tiene más de una fila que tiene columnas o viceversa, como un perfecto maridaje no puede existir. Es fácil ver, sin embargo, que un perfecto maridaje existía antes de su algoritmo igualado el escaso número de fila y de columna.

Answer 3

Diagrama para dar un ejemplo para deinst la respuesta. He intentado poner esto en un comentario, pero se llena el formato. El Xs marcas que dan a un partido completo

X01100001
1X1100000
11X100000
111X00000
00001011X
0000X1110
000011X10
0000111X0
01000X000

Ahora, supongamos que tomamos las dos plazas marcada por las Y

*0**0000Y
111100000
111100000
111100000
00001011*
00001*110
00001*110
00001*110
0*000Y000

Tenemos dos 3 por 4 cuadrados a la izquierda, por lo que podemos tomar de 6 a más elementos. Esto da un total de 8 en lugar de 9. Podemos aplicar estos dos bloques a ser tomadas por el uso de una permutación.