2004图论复习题答案

图论复习题答案一、判断题，对打，错打1．无向完全图是正则图。()2．零图是平凡图。()只有结点没有边的图称为零图3．连通图的补图是连通图.()4．非连通图的补图是非连通图。()5．若连通无向简单图G中无圈，则每条边都是割边。()6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。()连通7．任何树都至少有2片树叶。()平凡树8．任何无向图G都至少有一个生成树。()连通9．非平凡树是二分图。()无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。10．所有树叶的级均相同的二元树是完全二元树。()11．任何一个位置二元树的树叶都对应唯一一个前缀码。()12．3,3K是欧拉图也是哈密顿图。()欧拉图每个顶点度数是偶数13．二分图的对偶图是欧拉图。()14．平面图的对偶图是连通图。()15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。()二、填空题1．无向完全图K6有15条边。2．有三个顶点的所有互不同构的简单无向图有4个。3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有10片树叶。1.树m=n-12.握手定理4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集有n-1个，基本圈有m-n+1个。5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2个面。顶点数n-边数m+面数=2三、解答题1．有向图D如图1所示，利用D的邻接矩阵及其幂运算abcde图1求解下列问题：（1）D中长度等于3的通路和回路各有多少条。（2）求D的可达性矩阵。（3）求D的强分图。解：（1）M=0001010000000010100000010M2=0100000010000101000001000M3=1000001000010000001010000M4=0001001000100000100000010由M3可知，D中长度等于3的通路有5条，长度等于3的回路有3条。（2）I+M+M2+M3+M4=1000001000001000001000001+0001010000000010100000010+0100000010000101000001000+1000001000010000001010000+0001001000100000100000010=2102013010111110202011021D的可达性矩阵为R=B（I+M+M2+M3+M4）=1101011010111111101011011abcde图1（3）RT=1111111111001001111100101R×RT=1101011010001001101000001由矩阵R×RT可知，该有向图的强分图有：{a}，{b，d，e}，{c}2．画出有1个4次顶点，2个2次顶点，4个1次顶点的所有非同构的树。3．用Kruskal算法求图2所示带权图的最小生成树，并计算它的权。C（T）=254．试画出带权为1,2,3,4,5,7,的最优二元树,并计算它的权。m（T）=（1+2）4+33+（7+4+5）2=535．出席某次国际学术报告会的六个成员654321,,,,,PPPPPP被分在一组。他们的情况是：1P会讲汉语、法语和日语；2P会讲德语、日语和俄语；3P会讲英语和法语；4P会讲汉语和西班牙语；5P会讲英语和德语；6P会讲俄语和西班牙语。怎样把他们安排在一张圆桌旁坐下，使得每个人都能和他两旁的人交谈？解构造无向图EVG,，其中12943685710111233622754139},,,,,{654321PPPPPPV，}|),{(会讲同一种语言与jijiPPPPE，则得无向图如图所示。由该图得一条哈密顿回路：1352641PPPPPPP，即为满足要求的安排。四、证明题1．设T是完全二元树，T中有m条弧和t片树叶，证明：m=2(t1)。证明：设完全二元树T有n个顶点。因为它有t片树叶，所以除树叶以外的顶点有tn个。由于完全二元树中，根和分支点的引出次数为2，每片树叶的引出次数为0，故所有顶点的引出次数之和为)(2tn，它等于边数m。又因为1nm，故有1)(2ntn，解得12tn。因此)1(2221ttnm。3P1P2P4P6P5P