图的矩阵表示做题总结

图的矩阵表示做题总结

关联矩阵(有向图)

离散书上清晰的讲解了无向图的关联矩阵(p161),无书的同学可看下图,我就不做讲解。

图片[1]-图的矩阵表示做题总结-开心之家

我们主要谈谈有向图的关联矩阵,在有向图D=<V,E>中,ej离开vi(箭头指出),则mij=1;ej进入vi(箭头指入),则mij=-1;ej和vi不相关联,则mij=0.

例1:在图D中,e1为<v1,v2>,关联矩阵表示如下图。(画图太烂了,大家将就看一下,难搞哦)

图片[2]-图的矩阵表示做题总结-开心之家

例2:学习通上的题,这个好看多了。

图片[3]-图的矩阵表示做题总结-开心之家
matlab实现邻接矩阵求可达矩阵(有向图)或连通矩阵(无向图)

A=[0,1,0,1;1,0,1,1;0,1,1,0;1,1,0,0]; %输入邻接矩阵
I=eye(4); %4阶单位矩阵(可变,随矩阵A的阶数改变)
S=A+I; %A0+A1
p=S;
for i=2:4 %4为邻接矩阵A的阶数(随矩阵A的阶数改变)
p=p+A^i; %A2+A3+A4(一直加到An,n为矩阵A的阶数)
end
p(p~=0) =1; % 将不为0 的元素变为1
p

邻接矩阵求通路与回路数

设A为p阶图G=<V,E>的邻接矩阵,其中V={v1,v2,···,vp}。

vi到vj长度为n的通路数:矩阵A的n次幂An(n=1,2,3,···)中的元素aij(n)表示vi到vj长度为n的基本通路的总数。

长度为n的通路总数:矩阵中元素aij(n)之和。

vivi长度为n的回路数:元素aii(n)表示通过vi的长度为n的基本回路的总数。

长度为n的回路总数:矩阵主对角线之和。

可达矩阵求单向连通分图和强联通分图

设A为p阶图G=<V,E>的邻接矩阵。

1.找出图G的邻接矩阵A。

2.计算A的幂和CA。(CA=A0+A1+···+Ap

3.得出可达矩阵。(矩阵CA中对应元素不为0标1,为0标0)

4.写出可达矩阵的转置矩阵。

5.分别求可达矩阵与它的转置矩阵的析取(求单向连通分图)和合取(求强联通分图)。

© 版权声明
THE END
喜欢就支持一下吧
点赞11 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容