oРoРv1РoРv5Рv2Рv3Рv4Р2.图G=<V, E>,其中V={ a, b, c, d, e},E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) },对应边的权值依次为2、1、2、3、6、1、4及5,试Р(1)画出G的图形; (2)写出G的邻接矩阵;Р(3)求出G权最小的生成树及其权值.Р(1)G的图形如下:Р(2)写出G的邻接矩阵Р(3)G权最小的生成树及其权值Р3.已知带权图G如右图所示. Р(1) 求图G的最小生成树; (2)计算该生成树的权值.Р解:(1) 最小生成树为Р1Р2Р3Р5Р7Р(2) 该生成树的权值为(1+2+3+5+7)=18Р4.设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权.Р3Р5Р2Р5Р10Р7Р17Р31Р17Р34Р65Р权为 2*5+3*5+5*4+7*3+17*2+31=131Р四、证明题Р1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图中的奇数度顶点个数相等.Р证明:设,.则是由n阶无向完全图的边删去E所得到的.所以对于任意结点,u在G和中的度数之和等于u在中的度数.由于n是大于等于3的奇数,从而的每个结点都是偶数度的(度),于是若在G中是奇数度结点,则它在中也是奇数度结点.故图G与它的补图中的奇数度结点个数相等.Р2.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.Р证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.Р又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图.Р故最少要加条边到图G才能使其成为欧拉图.
全文预览
