作业帮 > 数学 > 作业

判断有向图的回路长度和条数

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/10 06:50:18
判断有向图的回路长度和条数
对如下有向图D,求D中长度为4的路有多少条?其中回路有多少条?
额没关系不用写过程,就是解释下为什么?原理是?这部分我们没学。
判断有向图的回路长度和条数
将图表示成邻接矩阵的形式
求长为4的路等价于求邻接矩阵的4次幂中4的个数
回路的条数等于对角线上4的个数
这个过程不好写,建议楼主查一下图论中关于邻接矩阵的部分
邻接矩阵A的n次方的a(i,j)项等于等于有向图中从i到j长为n的路的条数
这个在离散数学书里一般占一节,一句话讲不太清楚
建议楼主还是找本书翻翻