> 数学 >
若0-1的m*n矩阵A中,每行有k个1,每列1的个数不超过k,则A可以写成P1+P2+...+Pk,其中Pi也是m*n阶0-1矩阵,且每行恰1个1,每列1的个数不超过1.
用图论证明
m
人气:302 ℃ 时间:2020-05-19 01:01:53
解答
第i行第j列的元素为1相当于有向图中i号节点到j号节点有一条有向线段.那么从某个节点开始按照选取一条链:a1->a2->...->ak->a(k+1),这里a(k+1)允许和a1相同,即构成环,如果提前成环的话就在余下的节点里继续构造这样的...
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版