下载文档原格式
(P147) 2，32. 一房子的平面图如图。
问能否从前门进去，最后从后门出去，走过所有的门且每扇门只经过一次？解：建立无向图图模型如下：顶点表示房间和前后门区域，边表示房间(区域)之间的门。
原问题等价于如下的问题：在表示前门区域和后门区域的顶点之间，是否存在欧拉通路？答案是：存在，因为这个图是连通图，且这两顶点的度为奇数，而其余顶点的度均为偶数（图需重画）3. 对于有16个扇区和4个探测器的磁鼓，给出一种合理的0-1赋值。
解：00001001101011115. 说明下图不是哈密顿图。
解：从图中删除所标记的6个顶点， 所得到的图由7个孤立点组成，有7个连通分量。
所以，该图不满足哈密顿图的必要条件，因而不是哈密顿图（图需改，怎么改请看解答）*补充：为了测试计算机网络上的所有连接和设备，可以在网络上发一个诊断消息。
为了测试所有的连接，应当使用什么种类的通路？为了测试所有的设备呢？解：测试连接：欧拉通路；测试设备：哈密顿通路*13. 证明任意竞赛图都有有向哈密顿通路。
证明：考虑竞争图的某条长度最大的有向基本通路l，证明l含有所有的顶点，从而l是有向哈密顿通路。
采用反证法，假定存在不在l上的顶点。
不妨设顶点v不在l上，l=v1v2…v k-1v k。
v和v k之间的有向边必从v指向v k，否则l将不是最长的基本通路。
类似地，v和v1之间的有向边必从v1指向v。
从v2开始，顺着l找到第1个顶点v i，v和v i之间的有向边从v指向v i，（这样的顶点一定存在，因为v k就是这样的顶点）。
显然，v1v2…v i-1vv i…v k-1v k是基本通路，长度大于l。
这与l是长度最大的基本通路矛盾。
于是，l含有所有的顶点。
（需加图，请看证明）14. 设简单连通图G有n个顶点、e条边。
若G是平面图，则e≤3n-6。
证明：简单图任何回路的长度均不小于3，故简单平面图每个面的次数均大于等于3，所以e≤3(n-2)/(3-2)=3n-6（欧拉公式的推论）17. 若简单连通图G有n个顶点、e条边，则G的厚度至少为⎡e/(3n-6)⎤。
第八章 代数系统习题8.11．解 ⑴是，⑵不是，⑶是，⑷不是。
2．解 若﹡对 是可分配的，则有任意a,b,c ∈*I,均有a ﹡(b c)=(a ﹡b) (a ﹡c)= a b ac =( a b ⋅ a c )= a b+c而a ﹡(b c)=a ﹡(b ⋅c)= a b ⋅c ≠a b+c 故﹡对 是不可分配的。
3．解 ⑴对于任意A ∈P(S), 因为A ⊆S ，所以，A ⋃S =S ，因此，S 是关于⋃运算的零元； ⑵对于任意A ∈P(S), 因为A ⊆S ，所以，A ⋂S = A ，因此，S 是关于⋃运算的零元单。
4．解 ⑴①因为x*y=xy-2x-2y+6，则y*x=yx-2y-2x+6= x*y ，满足交换律； ②任意x,y,z ∈R 有x*(y*z)=x*(yz-2y-2 z +6)=x(yz-2y-2 z +6)-2x-2(yz-2y-2z+6)+6 =xyz-2xy-2xz+6x-2x -2yz+4y+4z-12+6= xyz-2xy-2xz-2yz+4x+4y+4z-6. (x*y)*z=(xy-2x-2y+6) *z =(xy-2x-2y+6)z-2(xy-2x-2y+6)-2z+6 =xyz-2xz-2yz+6z-2xy+4x+4y-2z-6=x*(y*z). 故满足结合律。
(2) ①设任意a ∈R,存在e ∈R,要e*a= ea-2e-2a+6=a ，由于a 的任意性则e=3。
因此e=3是其单位元;②设任意b ∈R, z ∈R ，要有z*b= zb-2 z-2b+6= z ，由于b 的任意性则z=2，因此 z=2是其零元。
（3）因为*是满足交换律，对于x ∈R ，要存在1-x ∈R ，须有x*1-x= x 1-x-2x-21-x+6= e=3, 当x ≠2时，2321--=-x x x。
即对于任意的x ，当x ≠2时x 都是可逆的，且2321--=-x x x。
5．解 f 1,f 2,f 3都满足交换律，f 4满足等幂率，f 2有单位元a ，f 1有零元a ，f 3有零元b 。
离散数学第8章函数离散数学第8章函数***** Eight离散数学Discrete Mathematics6/2/20XX年9:02 PMDiscrete Math. , Chen Chen离散数学第8章函数***** Eight第八章函数§8.1 函数的定义与性质§8.2 函数的复合与反函数§8.3 双射函数与集合的基数§8.4一个电话系统的描述实例6/2/20XX年9:02 PMDiscrete Math. , Chen Chen离散数学第8章函数§8.1 函数的定义与性质***** Eight定义8.1 设F 为二元关系，若x domF 都存在唯一的y ranF 使xFy 成立, 则称F为函数。
对于函数F, 如果xFy,则记y =F(x),并称y为 F 在x 的值。
例8.1 设F1={x1,y1, x2,y1, x3,y2},F2={x1,y1, x1,y2}. 则F1是函数，而F2不是函数。
定义8.2 设F、G是函数，则F=G F G∧ G F.注：如果F=G,那么它们满足：(1) dom F=dom G; (2) x dom F = dom G都有F(x)= G(x). 定义8.3 设A, B为集合, 如果f 是函数, 且domf=A,ran f B,则f 称为从A到B的函数，记作f : A→B.6/2/20XX年9:02 PM Discrete Math. , Chen Chen 3离散数学第8章函数§8.1 函数的定义定义8.4 所有从A 到B 的函数的集合记作BA,即BA={f | f: A→B}. A m 注：1. 若|A|=m, |B|=n, 则| B | = n ; 2. ΦΦ ={Φ }, BΦ={Φ}, ΦA=Φ. 例8.2 见教材P137. 定义8.5 设函数f : A→B,A1 A,B1 B.***** Eight(1) 令f (A1)={ f (x)| x A1}. 称f (A1)为A1在f 下的像。
