离散数学图论习题课.pptxVIP

图论习题课;图论基本要求;无向图G有21条边，12个结点度数为3，其余结点度数为2，求G的顶点数。;设树T有17条边，12片树叶，4个4度内结点，1个3度内结点，求T的树根的度数。;试证明 (a)和(b)两个图是同构的。;证明：设图(a)为G=<V,E>，图(b)为G′=<V′,E′>。 令g：V?V′， 定义为：g(a)=1，g(b)=2，g(c)=3，g(d)=4。 显然，g：V?V′是双射函数。 根据双射函数g，E中的边和E′中的边有如下的对应关系： (a,b)?(1,2)，(a,c)?(1,3)，(a.d)?(1,4)，(b,c)?(2,3)，(c,d)?(3,4)。 所以 (a)与(b)同构。;画出5个??点的自补图;图G=?V,E?如图所示，求出从d出发的所有基本回路。;有向图G。⑴求a到d的最短路径和距离。⑵求d到a的最短路径和距离。⑶判断G是哪类连通图，是强连通，单向连通，还是弱连通？;设G=?V,E?是一个简单有向图，V=?v1, v2, v3, v4?，邻接矩阵如下：（1）求v1的出度deg＋(v1)。（2）求v4的入度deg－(v4)。（3）由v1到v4长度为2的路有几条？;解：⑴ deg＋(v1)=1 ⑵ deg－(v4)=2 ⑶ A2= 由于 =1，所以由v1到v4长为2的路有1条。 ;有向图G如图所示。⑴ 写出G的邻接矩阵。⑵ 根据邻接矩阵求各结点的出度和入度。⑶ 求G中长度为3的路的总数，其中有多少条回路。⑷ 求G的可达性矩阵。⑸ 利用P∧PT，求图中的所有强分图;解：⑴A=;14;对于如下赋权图，利用克鲁斯克尔(kruskal)算法求一棵最小生成树。;求出对应于图1所给出的树的二叉树。;求带权3,4,5,6,7,8,9的最优二叉树T，并计算出它的权值。;最优树的权为： W(T)=(3＋4)×4＋7×3＋(5＋6)×3＋(8＋9)×2=116。