图论复习题答案一、 判断题，对打Ö，错打Ï1． 无向完全图是正则图 Ö )2． 零图是平凡图 Ï )3． 连通图的补图是连通图. ( Ï )4． 非连通图的补图是非连通图 Ï )5． 若连通无向简单图G中无圈，则每条边都是割边 Ö )6． 若无向简单图G是（n，m）图，并且m=n-1，则G是树 Ï )7． 任何树都至少有2片树叶 Ï )8． 任何无向图G都至少有一个生成树 Ï )9． 非平凡树是二分图 Ö )10． 所有树叶的级均相同的二元树是完全二元树 Ï )11．任何一个位置二元树的树叶都对应唯一一个前缀码 Ö )12．是欧拉图也是哈密顿图 Ï )13． 二分图的对偶图是欧拉图Ï)14．平面图的对偶图是连通图 Ö )15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数 Ï )二、填空题1．无向完全图K6有 15 条边2．有三个顶点的所有互不同构的简单无向图有 4 个3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有 10 片树叶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 个面abcde图1三、解答题1．有向图D如图1所示，利用D的邻接矩阵及其幂运算求解下列问题：（1） D中长度等于3的通路和回路各有多少条2） 求D的可达性矩阵3） 求D的强分图解： （1）abcde图1M= M2= M3= M4=由M3可知，D中长度等于3的通路有5条，长度等于3的回路有3条2）I+M+M2+M3+M4=+++ + = D的可达性矩阵为R=B（I+M+M2+M3+M4）=（3）RT = R×RT =由矩阵R×RT可知，该有向图的强分图有：{a}，{ b，d，e}，{ c}2． 画出有1个4次顶点，2个2次顶点，4个1次顶点的所有非同构的树3． 用Kruskal算法求图2所示带权图的最小生成树，并计算它的权1294368571011C（T）=2512336227541394． 试画出带权为1,2,3, 4,5,7,的最优二元树,并计算它的权m（T）=（1+2）´4+3´3+（7+4+5）´2=535． 出席某次国际学术报告会的六个成员被分在一组。
他们的情况是：会讲汉语、法语和日语；会讲德语、日语和俄语；会讲英语和法语；会讲汉语和西班牙语；会讲英语和德语；会讲俄语和西班牙语怎样把他们安排在一张圆桌旁坐下，使得每个人都能和他两旁的人交谈？解 构造无向图，其中，，则得无向图如图所示由该图得一条哈密顿回路：，即为满足要求的安排四、证明题1． 设T是完全二元树，T中有m条弧和t片树叶，证明：m = 2(t-1)证明： 设完全二元树T有n个顶点因为它有t片树叶，所以除树叶以外的顶点有个由于完全二元树中，根和分支点的引出次数为2，每片树叶的引出次数为0，故所有顶点的引出次数之和为，它等于边数m又因为， 故有，解得。