特殊图习题及答案

第六章特殊图题六一.判断图一哪些是欧拉图？对不是欧拉图至少要加多少条边才能成为欧拉图？图一解答:,一,二二.画一个无向欧拉图使它具有:(一)偶数个顶点,偶数条边。(二)奇数个顶点,奇数条边。(三)偶数个顶点,奇数条边。(四)奇数个顶点,偶数条边。解答:(一)四四(二)（三(三)(四)三.判断彼得松图是否为欧拉图,是否为哈密顿图。若不是,至少加几条新边才能使它成为欧拉图？又至少加几条新边才能使它变成哈密顿图?五条新边可以成为欧拉图加一条边可以成为哈密顿图。四.判断图二所示四个图是否能一笔画出。一三零离散数学图二解答:五.(一)画一个欧拉回路与哈密顿回路地;(二)画一个欧拉回路,但没有哈密顿回路图;(三)画一个没有欧拉回路,但有哈密顿回路地;(四)画一个既没有欧拉回路也没有哈密顿回路地解答:(一)三（三(二)(三)(四)六.设有a,b,c,d,e,,g七个,它们分别会讲如下各种语言:a会讲英语b会讲汉语与英c会讲英语西班牙语与俄语d会讲汉语与日语e会讲德语与西班牙语f会讲法语,日语与俄语g地座位安排在圆桌旁使得每个均能与它身边谈。解答:分别用a,,c,,e,,g七个结点表示七个,若两可以谈（使用同一种语言）,则在代表它们地结点之间连一条无向边如下图a地座位安排在圆桌旁使得每个均能与它身边谈只需找出一条哈密顿回路如abdfgeca。七.际象棋地马走日字,即在x,y格子地马可以走到xy,xy二地任何一个走遍所有地格子且每个格子只走一次称作马周游。证明:一三一第六章特殊图(一)在三四棋盘上存在马地周游。(二)在三三棋盘上不存在马周游。两个顶点之间相邻当且仅当马可以从对应一个格子跳到另一个格子。因此,地周游问题等价于图地哈密顿通路存在问题。(一)三四棋盘可以使用以下走法（格子数字代表走一一二三四九六七二一零五八(二)三三棋盘不可能存在哈密顿通路,因此心格子对应顶点是孤立点。八.一棵无向树T有五片树叶,三个二度分支点,其余地分支点都是三度结点,问T有几个结点？T有n个结点根据握手定理有三二三(n五二(n得。九.无向树T有八片树叶二个三度分支点其余分支点都是四度顶点问有几个顶点？解答:假设T有n个顶点,根据握手定理有得=一二一零.一棵无向树T有ii,k)个i度分支点其余顶点都是树叶问有几片树叶？T有n个顶点xnxnnn根据握手定理,二三kk有二(nx二nn从而得xnkn二二in。二三k三kii三若n(n阶无向树T最大度T至少为几最多为几？解答:至少为二至多为n-一。T三所示。回答以下问题:(一)T是几叉树？(二)T树高为几？(三)T有几个内点？(四)T有几个分支点？一三二离散数学图三解答:(一)T是四叉树。(二)T树高为四。(三)T有八个内点。(四)T有七个分支点。画一棵权为最优二叉树并计算出它权。四)四六七)三九)二。下面给出各符号串集合哪些是前缀码？一二三四b,c,dd,dc,aba,abb,五b,c,a,aa,ac,abc,abb,解答:A:是A:是A:否A:是A:否。一二三四五四地二叉树产生一个二元前缀码。图四解答:{零零零,零零一,一零零零,一零一,。设七个字母在通信出现地频率如下:一三三第六章特殊图a:三五%b:二零%c:一五%d:一零%e:一零%f:五%g:五%构造一组表示它们二元前缀码使得传送地二制位最少。二元前缀码为{零零零零,零零零一,零零一,零一,一零零,一零一,。图五地二叉树表示一个算式。(一)用序遍历法还原算式。(二)用前序遍历法写出该算式波兰符号法表达式。(三)用后序遍历法写出该算式逆波兰符号法表达式。图五解答:(一)(二)(三)一八.用二叉有序正则树表示代数表达式解答:一三四离散数学一九.六所示图,重新找面嵌入,使外部面次数分别为三与。图六解答:外部面次数为三外部面地次数为四七所示两面图面边界与次数并验证欧拉公式。图七地次数为D(r)D(r)D(r)D(r)D(r)D(r)。一二三四五六右图各面次数为D(r)D(r)D(r)D(