大师作文网matlab中已知一矩阵,求其连通性
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/10/03 19:16:19
matlab中已知一矩阵,求其连通性
已知一个N*N的矩阵,用M表示；
M(i,j)只能取1或0；
当M(i,j)=1时,表示i,j可以连通；当M(i,j)=0时,表示i,j不能连通；
定义M(i,i)=1.
M给定；
求所有的点是否连通.
当N取较大数值时,相对复杂起来了,
============================
感谢matlab2007的回答
============================
你的说法是正确的
我后来查阅了些资料
对于M，有S矩阵
S=M+M^2+M^3+...+M^(N-1)；其中N是M的行数或列数
若S中有元素为零，则不连通；S中无零，则连通。
原理正如你所说的；
当N取大数时，对于M剩多少次才算结束，你没有明确回答，但是原理很正确，最后还是感谢你的回答。
=======
详细介绍可查阅：
《基于邻接矩阵图的连通性判定准则》；
贾进章，刘 宋寿森。
第22 卷第2 期 辽宁工程技术大学学报 2003年4月
=======
这是我查阅的资料，希望对大家有用！
已知一个N*N的矩阵,用M表示；
M(i,j)只能取1或0；
当M(i,j)=1时,表示i,j可以连通；当M(i,j)=0时,表示i,j不能连通；
定义M(i,i)=1.
M给定；
求所有的点是否连通.
当N取较大数值时,相对复杂起来了,
============================
感谢matlab2007的回答
============================
你的说法是正确的
我后来查阅了些资料
对于M，有S矩阵
S=M+M^2+M^3+...+M^(N-1)；其中N是M的行数或列数
若S中有元素为零，则不连通；S中无零，则连通。
原理正如你所说的；
当N取大数时，对于M剩多少次才算结束，你没有明确回答，但是原理很正确，最后还是感谢你的回答。
=======
详细介绍可查阅：
《基于邻接矩阵图的连通性判定准则》；
贾进章，刘 宋寿森。
第22 卷第2 期 辽宁工程技术大学学报 2003年4月
=======
这是我查阅的资料，希望对大家有用！
M*M一直乘下去,直到不发生改变,连通性一目了然.
M矩阵是一次联通矩阵,也就是如果他上三角都是正的那么所有的点直接联通.因为你这里联通是双向的,所以也可以是全部点都是正的.
M*M是二次联通矩阵,如果上三角都是正的,就是说M的中的点可以通过另一个点间接的全部联通.
同理M*M*M是三次联通.
比如M =
1 1 1 0
1 1 0 0
1 0 1 1
0 0 1 1
那么1,2直接联通,1,3直接联通,3,4直接联通.但是其他点不能直接联通,所以矩阵中有0.我们其实可以看到,2和3都联通1,所以可以间接一个1实现联通,2和4不能直接连,但是2可以通过1连到3,3又联到4,所以他需要两个间接就可以联通,下面的方法证明了这一点.
M*M =
3 2 2 1
2 2 1 0
2 1 3 2
1 0 2 2
可以看到2,3是变成正的了,也就是2,3间接1次联通,2,4还是0表示间接1次不联通.
M*M*M =
7 5 6 3
5 4 3 1
6 3 7 5
3 1 5 4
全部都正了,表示所有的点三次联通,也就是,任意一个点最多之用间接两个点就可以走到任何一个点.
M矩阵是一次联通矩阵,也就是如果他上三角都是正的那么所有的点直接联通.因为你这里联通是双向的,所以也可以是全部点都是正的.
M*M是二次联通矩阵,如果上三角都是正的,就是说M的中的点可以通过另一个点间接的全部联通.
同理M*M*M是三次联通.
比如M =
1 1 1 0
1 1 0 0
1 0 1 1
0 0 1 1
那么1,2直接联通,1,3直接联通,3,4直接联通.但是其他点不能直接联通,所以矩阵中有0.我们其实可以看到,2和3都联通1,所以可以间接一个1实现联通,2和4不能直接连,但是2可以通过1连到3,3又联到4,所以他需要两个间接就可以联通,下面的方法证明了这一点.
M*M =
3 2 2 1
2 2 1 0
2 1 3 2
1 0 2 2
可以看到2,3是变成正的了,也就是2,3间接1次联通,2,4还是0表示间接1次不联通.
M*M*M =
7 5 6 3
5 4 3 1
6 3 7 5
3 1 5 4
全部都正了,表示所有的点三次联通,也就是,任意一个点最多之用间接两个点就可以走到任何一个点.