设为简单有向图G的邻接矩阵,证明A3的对角线元素表示经过结点v1的“三角形”的个数,即以v为一个结点的G的子图k3的个数.
设G为n个结点的无向简单图,若x(G)≥k,则称G是k-连通图,k为非负整数.证明以下结论:
(1)当时,正明G连通.
(2)当时,证明G是k-连通图.
从大到小的次序链接的,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
a)图7-21中的边能剖分为两条路(边不相重),试给出这样的剖分。
b)设G是一个具有k个奇数度结点(k>0)的连通图,证明在G中的边能剖分为k/2条路(边不相重)。
c)设G是一个具有k个奇数度结点的图,问最少加几条边到G中,而使所得的图有一条欧拉回路,说明对于图7-21如何能做到这一点。
d)在c)中如果只允许加平行于G中已存在的边,问最少加几条边到G中,使所得的图中有一条欧拉回路,这事总能做到吗?叙述能做到这事的充分必要条件。
对图9.17给出的有向图G:
(1)写出它的邻接矩阵A,用邻接矩阵计算各个结点的出度与人度.
(2)计算说出从出到后的长度为1,2,3,4的拟路径各有多少条.
(3)计算,说出它们中第2,3分量及第4,4分量的意义.
(4)计算它的路径矩阵B及可达性矩阵P,并从P说出G的各强分图.