（2）r(R)?R?R0?R?IA?{?a,a?,?a,b?,?b,a?,?c,d?,?b,c?}?IA
s(R)?R?R?1?{?a,a?,?a,b?,?b,a?,?c,d?,?b,c?,?d,c?,?c,b?}
t(R)?R?R2???{?a,a?,?a,b?,?a,c?,?a,d?,?b,b?,?b,d??b,a?,?c,d?,?b,c?} 该题要求画出三个闭包的关系图. 每个关系图2分,共6分. 边少画或多画一律判错. 3 (1)如图2
（2）A的极大元有：7，8，9，10，11，12 A的极小元有：1
（3）B的上界是{6,12},最小上界是6 B的下界是1，最小下界是1
哈斯图中若出现水平的边,扣1分. 4．（８分）
（１）判断下图是否为欧拉图，若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4分）
答：因为该图是连通图且图中没有奇度顶点，所以该图是欧拉图(只要判断正确给2分)。欧拉回路标序如下图：
6
１ ９ ８ ２ 14 11 1312 ７
10 ３
６
找的欧拉回路正确再2分
４
５
（2）判断下图是否为哈密顿图，若是，请给出一哈密顿回路（用阿拉伯数字在顶点上标明顺序即可）；若不是，请说明原因（4分）
答：该图不是哈密顿图(2分)。取Ｖ＝｛４，６，８｝，从图中删除Ｖ，得五个连通分支，如下图所示，所以该图不是哈密顿图。(2分)
另一证明:反证若有哈密顿圈,由于点5,7,9都是二度点,因此该哈密顿圈必包含边(4,5)(5,6)(6,7)(7,8)(8,9)(9,4),这6条边构成一个圈,矛盾.
１ １ ６ ５ 10 ４ ９ ７ ５ 10 ８ ９ ７ ２
２
３ ３
５．（8分）设G是无向简单图且δ(G)≥k≥2，试证明G中存在长度大于等于k+1的初级回路（圈）。 证明：不妨设Ｇ是连通图，若G不连通，因为Ｇ的各连通分支的最小度也都大等于k，因而可对它的某个连通分支进行讨论。设u,v为G中任意两个顶点，由G是连通图，因而u,v之间存在路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径”为Γt=v0v1?vt,则t≥k，事实上若存在“极大路径” Γs=v0v1?vs
7
且s 在Γt上构造圈，由于δ(v0)≥δ(G)≥k≥2，因而v0除与Γt上的v1相邻外，还存在Γt上的k-1个顶点vi1,vi2,?,vik?1(1?i1?i2???ik?1?t)与v0相邻，则v0v1...vi1...vi2?vik?1v0为一个圈且长度大等于k+1。 注意:也可直接设Γ是G的最长路径. ６．（8分）在一棵有3个2度顶点，2个4度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2分） 请画出所有这样的非同构的无向树。（6分） 答：设树叶有x片，则边数m=3+2+x-1=4+x，由握手定理知，2m=2*(4+x)=∑d(vi)=3*2+2*4+x 解得x=6，所以应该有６片树叶。共有十个非同构的无向树，如下： (1) 两个４度点相邻的情况： (2) 两个４度点中间有一个２度点的情况： 8 (3) 两个４度点中间有两个２度点的情况： (4) 两个４度点中间有三个２度点的情况： (请酌情扣分) 9