①有一条欧拉回路和一条汉密尔顿回路。 ②有一条欧拉回路但没有汉密尔顿回路。 ③没有欧拉回路但有汉密尔顿回路。 ④既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中，边的总数等于2(n-1)，这里n是叶子数。
答：证明 设分枝点数为i。因为在完全m叉树中，有(m-1)i=n-1，所以，当m=2时有i=n-1。又因为在
完全二叉树中，每个分枝点射出两条边，所以边的总数是2i，即边的总数是2(n-1)。 五、计算
求带权2、3、5、7、11、13的最优二叉树。
答：解 2 3 5 7 11 13 所求最优二叉树为 5 5 7 11 13 10 7 11 13 17 11 13 17 24 41
六、证明
在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。 试证
m?k(n?2)
k?2答：在一个连通平面图中，若它有n个结点，m条边，且每个面由k条边围成。 试证
m?k(n?2)
k?2证明 设此平面图有r个面。
?deg(ri)?k??deg(ri)?kr
又
??deg(ri)?k2m。将其代入欧拉公式 k2mk(n?2)n?m?r?2 得 n?m??2 整理得 m?
kk?2?kr?2m，从而有r?
6
七、证明
设V是有限字母表，给定代数系统?V*,??，其中?是串的连接运算。对于任一串??V，建立V到
**N的映射f，f(?)?|?|。证明f是?V*,??到?N,??的一个满同态，且当|V|?1时，f是同构映射。
答：证明 对于V中任意两字符串?和?，因为|???|?|?|?|?|，所以
*f(???)?|?|?|?|?f(?)?f(?)
nn??????对于任一正整数n?N，取a?V，则|aa?a|?n，所以，f(aa?a)?n，f是?V*,??f(?)?0，
到?N,??的一个满同态。
n???当|V|?1时，设V?{a}，f(aa?a)?n，f(?)?0，f是双射，因此，f是一个同构映射。
八、应用
给定有限状态机Ms?(Q,S,R,f,h,A)，它的状态图如附图所示。 1、 求状态A的011010的后继以及可接受状态序列。
?E???C???A???E???C???D 答：因为A??所以状态A的011010的后继状态是D，可接受状态序列是AECAECD。 2、 求Ms对于激励010110的响应。 答：Ms对于激励010110的响应是ecdcae。
3、 构造一台与Ms相似的转换赋值机Mt，画出Mt的状态图。 答：与Ms相似的转换赋值机Mt?(Q,S,R,f,g,qI)，其中：
0110107
Q?{A,B,C,D,E},S?{0,1},R?{a,b,c,d,e},qI?Af:f(A,0)?E,f(A,1)?Bf(B,0)?D,f(B,1)?Bf(C,0)?D,f(C,1)?Af(D,0)?E,f(D,1)?Cf(E,0)?B,f(E,1)?Cg:g(A,0)?e,g(A,1)?bg(B,0)?d,g(B,1)?bg(C,0)?d,g(C,1)?ag(D,0)?e,g(D,1)?cg(E,0)?b,g(E,1)?c
九、证明
考察一个（8，4）码C，它的校验位a5，a6，a7，a8满足下列方程 a5=a1+ a2+ a4 a6=a1+ a3+ a4 a7=a1+ a2+ a3 a8=a2+ a3+ a4
其中a1，a2，a3，a4为信息位。 求出这个码的一致校验矩阵。证明
Mt的状态图为：
minW(X)?4。
x?Cx?0答：证明 一致校验矩阵为：
8
?1?1?H??1??0?1011011111011000010000100??0? 0??1??矩阵H中无零列向量，且任意两个、三个列向量之和不等于零向量。而第一、二、六、八列向量之和为零
向量，所以，
minW(X)?4
x?Cx?0
复习题三
一、设集合 S??a,b,c?
完成下列各小题。 1求S的幂集P(S)。
答：P(S)?{?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 2证明?P(S),??是偏序集。
答：?A?P(S),因为A?A,因此关系?是自反的。
对任意A,B?P(S)，若有A?B,B?A,则A?B，因此关系?是反对称的。因此关系?是传递的。 对任意A,B,C?P(S)，若有A?B,B?C,则A?C，综上，?P(S),??是偏序集。
3画出偏序集?P(S),??的哈斯图。 答：偏序集?P(S),??的哈斯图如图1。
9
4在P(S)上定义两个二元运算?和?：对任意A,B?P(S)，A?B?A?B，A?B?A?B。请填空（在横线上填是或不是并回答为什么）：
①代数系统?P(S),?? 是 格，因为 P(S)中任意两个元素都有最小上界和最大下界。 。 ②代数系统?P(S),?? 是 有界格，因为 ?P(S),??有全上界，为{a,b,c}；有全下界，为
?。 。
③代数系统?P(S),?? 是 有补格，因为 ?P(S),??是有界格且?P(S),??中每一元素都有补元素。 。
④代数系统?P(S),?? 是 分配格，因为 对于任意A,B,C?P(S)，有
A?(B?C)?(A?B)?(A?C)A?(B?C)?(A?B)?(A?C)
成立。
⑤代数系统?P(S),?,?,~? 是 布尔代数，因为 ?P(S),??是有补分配格，即?P(S),??是布尔格，?P(S),?,?,~?是由布尔格?P(S),??诱导的代数系统。 二、计算
??x)是布尔代数?{0,1},?,?,??上的一个布尔表达式。设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x23试写出E(x1,x2,x3)的析取范式和合取范式（用列函数表的方法）。
答：解
布尔表达式对应的函数表为：
10