（书后作业）集合论与图论

5．判断下列命题之真伪：

(1)若f:X?Y且f是满射，则只要X是可数的，那么Y是至多可数的； (2)若f:X?Y且f是单射，那么只要Y是可数的，则X也是可数的； (3)可数集在任一映射下的像也是可数的； 答案：

6．设Ａ是有限集，Ｂ是可数集，证明：BA?{f|f:A?B}是可数的。

7. 设?为一个有限字母表，?上所有字（包括空字）之集记为??。证明??是 可数集

21

P142习题

1.找一个初等可数f(x)，使得它是(0,1)到实数R的一一对应。

3.试给出一个具体的函数，使得它是从(0,1)到[0,1]的一一对应。

4. 利用康托的对角线法证明2A是不可数集，其中A为可数集。

5．利用康托的对角线法证明所有的0，1的无穷序列是不可数集。

22

第六章 图的基本概念

P206习题

1．画出具有4个顶点的所有无向图(同构的只算一个)。

2．画出具有3个顶点的所有有向图(同构的只算一个)。

3．画出具有4个、6个、8个顶点的三次图。

4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。

P209习题

1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有圈？

23

2．证明：一个连通的(p，q)图中q≥p-1。

3．设G是一个（p，q）图，且q?(p?1)(p?2)/2，则G是连通的。

4. 设G是一个(p，q)图，δ(G)≥[p/2]，试证G是连通的。

6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。

8．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。

24