若0-1的m*n矩阵A中,每行有k个1,每列1的个数不超过k,则A可以写成P1+P2+...+Pk,其中Pi也是m*n阶0-1矩阵,且每行恰1个1,每列1的个数不超过1.用图论证明m
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 14:31:13
![若0-1的m*n矩阵A中,每行有k个1,每列1的个数不超过k,则A可以写成P1+P2+...+Pk,其中Pi也是m*n阶0-1矩阵,且每行恰1个1,每列1的个数不超过1.用图论证明m](/uploads/image/z/11595937-49-7.jpg?t=%E8%8B%A50-1%E7%9A%84m%2An%E7%9F%A9%E9%98%B5A%E4%B8%AD%2C%E6%AF%8F%E8%A1%8C%E6%9C%89k%E4%B8%AA1%2C%E6%AF%8F%E5%88%971%E7%9A%84%E4%B8%AA%E6%95%B0%E4%B8%8D%E8%B6%85%E8%BF%87k%2C%E5%88%99A%E5%8F%AF%E4%BB%A5%E5%86%99%E6%88%90P1%2BP2%2B...%2BPk%2C%E5%85%B6%E4%B8%ADPi%E4%B9%9F%E6%98%AFm%2An%E9%98%B60-1%E7%9F%A9%E9%98%B5%2C%E4%B8%94%E6%AF%8F%E8%A1%8C%E6%81%B01%E4%B8%AA1%2C%E6%AF%8F%E5%88%971%E7%9A%84%E4%B8%AA%E6%95%B0%E4%B8%8D%E8%B6%85%E8%BF%871.%E7%94%A8%E5%9B%BE%E8%AE%BA%E8%AF%81%E6%98%8Em)
若0-1的m*n矩阵A中,每行有k个1,每列1的个数不超过k,则A可以写成P1+P2+...+Pk,其中Pi也是m*n阶0-1矩阵,且每行恰1个1,每列1的个数不超过1.用图论证明m
若0-1的m*n矩阵A中,每行有k个1,每列1的个数不超过k,则A可以写成P1+P2+...+Pk,其中Pi也是m*n阶0-1矩阵,且每行恰1个1,每列1的个数不超过1.
用图论证明
m
若0-1的m*n矩阵A中,每行有k个1,每列1的个数不超过k,则A可以写成P1+P2+...+Pk,其中Pi也是m*n阶0-1矩阵,且每行恰1个1,每列1的个数不超过1.用图论证明m
第i行第j列的元素为1相当于有向图中i号节点到j号节点有一条有向线段.
那么从某个节点开始按照选取一条链:a1->a2->...->ak->a(k+1),这里a(k+1)允许和a1相同,即构成环,如果提前成环的话就在余下的节点里继续构造这样的链或者环.因为每个节点的出度不小于入度,所以k>1时上述链/环肯定是存在的.从原图中去掉这条链/环之后就把k变成k-1,然后用归纳法就行了.