题目内容
(请给出正确答案)
[主观题]
假定Anxn是一个无向简单图G的邻接矩阵,其中n是图G的顶点数。对Anxn采用顺序的方法存储其下三角,然
后写出对G进行宽度优先搜索的算法。
查看答案
如果结果不匹配,请 联系老师 获取答案
A.计算邻接矩阵中第i行的元素之和
B.计算邻接矩阵中第i列的元素之和
C.计算邻接矩阵中第i行的非零元个数
D.计算邻接矩阵中第i列的非零元个数
A.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关。
B.邻接表只能用于有向图的存储,而邻接矩阵对于有向图和无向图的存储都适用。
C.存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的下(或上)三角部分就可以了
D.用邻接矩阵M表示图,判定任意两个结点Vi和Vj之间是否有长度为n的路径相连,则只要检查M的n次方后,第 i行第j列的元素是否为0即可。
设G是恰合2k(k2≥1)个奇度顶点的无向连通图,证明G中存在k条边不重的简单通路使得
证明定理15.8.
定理15.8:设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.