数学建模社区-数学中国

标题: [求助]一个0-1矩阵的转换问题, 急求高手赐教, 谢谢! [打印本页]
作者: bobwuhk    时间: 2005-10-24 22:34
标题: [求助]一个0-1矩阵的转换问题, 急求高手赐教, 谢谢!

一个NXN的0-1矩阵的元素由0和1组成. 每行每列包含任意个数的0, 其他元素为1. 该矩阵由一条水平线和一条竖直线划分为四个区域(分块子矩阵) A, B, C及D, 如下所示. 假设N是偶数, A, B, C, D分别为(N/2)X(N/2)的子阵.

3 v& x8 I# i5 w9 Y

A | B

1 U1 \- f% K$ I9 b6 a D

------ | ---------

" \. {! k# p+ S4 ` x0 O& I) V# w$ K

D | C

% F: R2 E$ L+ q# S# `) C8 s, T

证明:

; ^/ G2 W5 D$ Q& m6 u

对该矩阵的行或列进行有限次数的互换, 可以得到同时满足下列条件的一个新矩阵: 1) 如果新矩阵的某一行包含在A和B区域中, 则该行在A区域中的1的个数不少于在B区域中的1的个数, 或者在A区域中的1的个数比B区域中的1的个数少1; 如果新矩阵的某一行包含在C和D区域中, 则该行在C区域中的1的个数不少于在D区域中的1的个数, 或者在C区域中的1的个数比D区域中的1的个数少1; 2) 如果新矩阵的某一列包含在A和D区域中, 则该列在A区域中的1的个数不少于在D区域中的1的个数, 或者在A区域中的1的个数比D区域中的1的个数少1; 如果新矩阵的某一列包含在B和C区域中, 则该列在C区域中的1的个数不少于在B区域中的1的个数, 或者在C区域中的1的个数比B区域中的1的个数少1.

5 U, ~2 a6 Y- l3 I: l

同时, 请给出该变换的运算复杂度.

作者: madio    时间: 2005-10-30 16:06
一般性的证明不知道，高手指点吧！



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5