发布时间 : 2024/5/19 0:29:15 星期日 文章2006离散数学a（答案）更新完毕开始阅读e977a21414791711cc791762

2006年下半年《离散数学》（闭卷）70学时

③ ┐Q(c) ① EI规则

④ R(c)∨ Q(c) ② UI规则

⑤ ?x(P(x)→ ┐R(x)) 前提引入 ⑥ P(c)→ ┐R(c) ⑤UI规则 ⑦ R(c) ③④析取三段论 ⑧ ┐P(c) ⑥⑦拒取式 ⑨ ?x ┐P(x) ⑧EG规则

2、今有n个人，已知他们中的任何二人和起来认识其余的n-2个人。证明：当n≥3时，这n个人能排成一列，使得中间的任何人都认识两旁的人，而两旁的人认识左边（或右边）的人。而当n≥4时，这n个人能排成一个圆圈，使得每个人都认识两旁的人。

解：设n个人分别为V1,V2,V3,?,Vn,?V={V1,V2,V3,?,Vn}为顶点集。若Vi

与Vj认识，就在代表它们的顶点间连一条无向边，得边集E，于是的无向简单图G=。对于任意Vi,Vj∈V，假设Vi与Vj不相邻，则对任意Vk∈V，（k<>i,k<>j）必与Vi或Vj相邻。否则与已知条件矛盾。不妨假设，VK与Vi相邻，与Vj不相邻。那么Vk与Vi所代表的两个人都不认识Vj所代表的人，这与已知矛盾。所以VK与Vi相邻，也与Vj相邻。因此， Vi与Vj都与其余的n-2个顶点相邻，从而deg(Vi)+deg(Vj)=n-2+n-2=2n-4,由于n?3,则2n-4?n-1。由定理15.7可知，G中存在哈密顿通路。当n?4由于2n-4?n由定理15.7的推论可知，G是哈密顿图。

图1-2

任课班级：114051-4、 111051-2 任课教师：孙明

5