题目内容
(请给出正确答案)
[单选题]
图G=<V,E>是简单有向图,邻接矩阵刻画下列哪种关系( ).
A.点与点
B.点与边
C.边与点
D.边与边
查看答案
如果结果不匹配,请 联系老师 获取答案
A.点与点
B.点与边
C.边与点
D.边与边
设为简单有向图G的邻接矩阵,证明A3的对角线元素表示经过结点v1的“三角形”的个数,即以v为一个结点的G的子图k3的个数.
从邻接矩阵可以看出,该图共有()个顶点。如果是有向图,该图共有()条有向边;如果是无向图,则共有()条边。
A、9
B、3
C、6
D、1
E、5
F、4
G、2
H、0
证明定理15.8.
定理15.8:设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.
对图9.17给出的有向图G:
(1)写出它的邻接矩阵A,用邻接矩阵计算各个结点的出度与人度.
(2)计算说出从出到后的长度为1,2,3,4的拟路径各有多少条.
(3)计算,说出它们中第2,3分量及第4,4分量的意义.
(4)计算它的路径矩阵B及可达性矩阵P,并从P说出G的各强分图.
A、ABCDGIFE
B、ABCDGFHE
C、ABGHFECD
D、ABFHEGDC
E、ABEHFGDC
F、ABEHGFCD
A.环路复杂性计算连通区法,靠计算有向退化图中的连通区的个数计算环路复杂度
B.判定条件计算法:从退化图中的判定个数计算环路复杂度。V(G)=判定条件个数+1
C.V(G)=m-n+1说明:V(G)为有向图G中环路复杂度;m为图G中弧数;n为图G中节点数
D.V(G)=m-n+p说明:V(G)为有向图G中环路复杂度;m为图G中弧数;n为图G中节点数;根据图论有向图G强连通分量p,添加图G中强连通分量后,p值为2
设G=<V,E>为无向图,命题均有,则G中存在哈密顿通路”的真值为()。