(書后作業(yè)最后稿)集合論與圖論

1、第一章 集合及其運(yùn)算習(xí)題1. 寫出方程的根所構(gòu)成的集合。2.下列命題中哪些是真的，哪些為假a)對每個集A，； b)對每個集A，；c)對每個集A，； d)對每個集A，；e)對每個集A，； f)對每個集A，；g)對每個集A，； h)對每個集A，；i)對每個集A，； j)對每個集A，；k)對每個集A，； l)對每個集A，；m)對每個集A，； n) ；o)中沒有任何元素； p)若，則q)對任何集A，； r)對任何集A，；s)對任何集A，； t)對任何集A，。答案：3.設(shè)有n個集合且，試證：。4.設(shè)，試求？5.設(shè)S恰有n個元素，證明有個元素。習(xí)題 6.設(shè)A、B是集合，證明:。7.設(shè)A、B是集合，試證。9

2、.設(shè)A，B，C為集合，證明：。10.設(shè)A，B，C為集合，證明：。11.設(shè)A，B，C為集合，證明：。12.設(shè)A，B，C都是集合，若且，試證B=C。15.下列命題是否成立？說明理由（舉例）。(1)；(2)；(3)。 16下列命題哪個為真？ 答案：_a)對任何集合A,B,C，若，則A=C。b)設(shè)A,B,C為任何集合，若，則B=C。c)對任何集合A,B，。 d)對任何集合A,B，。e)對任何集合A,B，。 f)對任何集合A,B，。17填空：設(shè)A,B是兩個集合。a)_； b)_c)_； d)_。18設(shè)A，B，C為三個集合，下列集合表達(dá)式哪一個等于？答案：_（a）；（b）；（c）；（d）；（e）。習(xí)題20

3、設(shè)A,B,C為集合，并且，則下列斷言哪個成立？(1)；(2)；(3)；(4)。答案：21設(shè)A,B,C為任意集合，化簡習(xí)題24設(shè)。求。25設(shè)A,B為集合，試證：A×BB×A的充要條件是下列三個條件至少一個成立：（1）；（2）；（3）。26設(shè)A,B,C,D為任四個集合，證明：29設(shè)是三個任意集合，證明：。30設(shè)A,B為集合，下列命題哪些為真？（1）且； （2）或；（3）； （4）若，則；（5）若，則。答案：_31設(shè)A有m個元素，B有n個元素，則A×B是多少個序?qū)M成的？A×B有多少個不同的子集？答案：_32設(shè)是兩個集合，試證：若，則。習(xí)題33設(shè)A,B是兩個有

4、限集，試求34.某班學(xué)生中有45正在學(xué)德文，65正在學(xué)法文。問此班中至少有百分之幾的學(xué)生正同時學(xué)德文和法文？第二章 映射習(xí)題習(xí)題1. 設(shè)A，B是有窮集，。則（1）計(jì)算； （2）從A到A有多少個雙射？習(xí)題3. 證明：從一個邊長為1的等邊三角形中任意選5個點(diǎn)，那么這5個點(diǎn)中必有2個點(diǎn)，它們之間的距離至多為1/2，而任意10個點(diǎn)中必有2個點(diǎn)其距離至多是1/3。5. 證明在52個整數(shù)中，必有兩個整數(shù)，使這兩個整數(shù)之和或差能被100整除。6.設(shè)為的任一排列，若n是奇數(shù)且，則乘積為偶數(shù)。習(xí)題7.設(shè)，證明8. 設(shè)，證明。10.設(shè)。以下四個小題中，每個小題均有四個命題，這四個命題有且僅有一個正確，請找出正確的

5、那個。（1）（a）若，則未必在A中；（b）若，則；（c）若，則； （d）若，則。（2）（a）； （b）；（c）； （d）。（3）（a）； （b）；（c）； （d）上面三個均不對。（4）（a）； （b）；（c）若； （d）若。習(xí)題15. 設(shè)，試求。習(xí)題17設(shè)，試構(gòu)造兩個映射和g：，使得（1），但；（2），但。18.設(shè)則（1）若存在唯一的一個映射，使得，則是可逆的嗎？（2）若存在唯一的一個映射，使得，則是可逆的嗎？20. 是否有一個從到的一一對應(yīng)，使得，但？ 習(xí)題21.設(shè)，求。22.將置換分解成對換的乘積。第三章 關(guān)系習(xí)題習(xí)題1.給出一個既不是自反的又不是反自反的二元關(guān)系？2.是否存在一個同時不滿

6、足自反性，對稱性，反對稱性，傳遞性和反自反性的二元關(guān)系？3.設(shè)R，S是X上的二元關(guān)系，下列命題哪些成立：a)若R與S是自反的，則分別也是自反的；b) 若R與S是對稱的，則分別對稱的；c) 若R與S是傳遞的，則也是傳遞的；d) 若R與S不是自反的，則也不是自反的；e) 若R與S是反自反的，則也是反自反的；f) 若R是自反的，則也是反自反的；g) 若R與S是傳遞的，則RS是傳遞的。答案：_4.實(shí)數(shù)集合上的“小于”關(guān)系是否是反自反的？集合X的冪集上的“真包含”關(guān)系是否是反自反的？為什么？5.設(shè)R、S是X上的二元關(guān)系。證明：（1）； （2）；（3）； （4）若，則；6設(shè)R是X上的二元關(guān)系，證明：是對稱

7、的二元關(guān)系。7設(shè)R為上的是反自反的和傳遞的二元關(guān)系,證明：R是反對稱的。習(xí)題9.“父子“關(guān)系的平方是什么關(guān)系？ 答案：_11.設(shè)R與S為X上的任兩個二元關(guān)系，下列命題哪些為真？ 答案：_a）若R,S都是自反的，則也是自反的； b）若R,S都是對稱的，則也是對稱的； c）若R,S都是反自反的，則也是反自反的； d）若R,S都是反對稱的，則也是反對稱的； e）若R,S都是傳遞的，則也是傳遞的。 12設(shè)R1是A到B，R2和R3是B到C的二元關(guān)系，則一般情況下：。但有人聲稱等號成立，他的證明如下：設(shè)，則，使得且。于是且。從而且，所以，即。同理可證相反的包含關(guān)系成立，故等式成立，這個證明錯在什么地方？1

8、3.設(shè)R，S是X上的滿足的對稱關(guān)系，證明。習(xí)題25.設(shè)。是S上的二元關(guān)系：。證明：（1）是S上的等價關(guān)系；（2）求等價類的集合。26. 設(shè)。是S上的二元關(guān)系：。證明：（1）是S上的等價關(guān)系；（2）求等價類數(shù)。27. 設(shè)。是S上的二元關(guān)系：。證明：（1）是S上的等價關(guān)系；（2）求等價類。28.由置換確定了上的一個關(guān)系當(dāng)且僅當(dāng)i與j在的循環(huán)分解式中的同一循環(huán)置換中，證明：是X上的等價關(guān)系，求。29給出X1,2,3,4上兩個等價關(guān)系R與S，使得不是等價關(guān)系。30設(shè)是X上的一個自反關(guān)系，證明：是等價關(guān)系若且，則。35設(shè)X是一個集合，試求：（1）X上自反二元關(guān)系的個數(shù)；（2）X上反自反二元關(guān)系的個數(shù)；（

9、3）X上對稱二元關(guān)系的個數(shù)；（4）X上自反或?qū)ΨQ關(guān)系的個數(shù)。習(xí)題38.存在一個偏序關(guān)系，使得中有唯一的極大元素，但沒有最大元素？若有請給出一個具體例子；若沒有，請證明之。39令S1，2，12，畫出偏序集（S,|）的Hass圖，其中“|”是整除關(guān)系，它有幾個極大（小）元素？列出這些極大（小）元素。第四章 無窮集合及其基數(shù)習(xí)題1. 設(shè)為由序列的所有項(xiàng)組成的集合，則是否是可數(shù)的？為什么？2.證明：直線上互不相交的開區(qū)間的全體所構(gòu)成的集合至多可數(shù)。3.證明：單調(diào)函數(shù)的不連續(xù)點(diǎn)的集合至多可數(shù)。4.任一可數(shù)集的所有有限子集構(gòu)成的集族是可數(shù)集合。5判斷下列命題之真?zhèn)危?1)若且是滿射，則只要是可數(shù)的，那么是

10、至多可數(shù)的；(2)若且是單射，那么只要是可數(shù)的，則也是可數(shù)的；(3)可數(shù)集在任一映射下的像也是可數(shù)的；7. 設(shè)為一個有限字母表，上所有字（包括空字）之集記為。證明是可數(shù)集習(xí)題1.找一個初等可數(shù)，使得它是到實(shí)數(shù)的一一對應(yīng)。4. 利用康托的對角線法證明是不可數(shù)集，其中為可數(shù)集。5利用康托的對角線法證明所有的0，1的無窮序列是不可數(shù)集。第六章 圖的基本概念習(xí)題1畫出具有4個頂點(diǎn)的所有無向圖(同構(gòu)的只算一個)。2畫出具有3個頂點(diǎn)的所有有向圖(同構(gòu)的只算一個)。3畫出具有4個、6個、8個頂點(diǎn)的三次圖。4某次宴會上，許多人互相握手。證明：握過奇數(shù)次手的人數(shù)為偶數(shù)(注意，0是偶數(shù))。習(xí)題1設(shè)u與v是圖G的兩

11、個不同頂點(diǎn)。若u與v間有兩條不同的通道(跡)，則G中是否有圈？2證明：一個連通的(p，q)圖中qp-1。3設(shè)G是一個（p，q）圖，且，則G是連通的。6在一個有n個人的宴會上，每個人至少有m個朋友(2mn)。試證：有不少于m+1個人，使得他們按某種方法坐在一張圓桌旁，每人的左、右均是他的朋友。8設(shè)G是圖。證明：若(G)2，則G包含長至少是(G)+1的圈。習(xí)題1證明：若圖G不是連通圖，則Gc 是連通圖。2證明：每一個自補(bǔ)圖有4n或4n+1個頂點(diǎn)。習(xí)題1.給出一個10個頂點(diǎn)的非哈密頓圖的例子，使得每一對不鄰接的頂點(diǎn)u和v，均有：degu+degv9。2試求Kp中不同的哈密頓圈的個數(shù)。4完全偶圖Km，

12、n為哈密頓圖的充分必要條件是什么？10證明具有奇數(shù)頂點(diǎn)的偶圖不是哈密頓圖。第七章 樹和割集習(xí)題1分別畫出具有4、5、6個頂點(diǎn)的所有樹(同構(gòu)的只算一個)。2證明：每個非平凡樹是偶圖。3設(shè)G是一棵樹且(G)k，證明：G中至少有k個度為1的頂點(diǎn)。4令G是一個有p個頂點(diǎn)，k個支的森林，證明：G有p-k條邊。6設(shè)樹中有個度為1的頂點(diǎn)，有個度為2的頂點(diǎn)，有個度為3的頂點(diǎn)，則這棵樹有多少個頂點(diǎn)和多少條邊？7一棵樹T有n2個度為2的頂點(diǎn)，n3個度為3的頂點(diǎn)，nk個度為k的頂點(diǎn)，則T有多少個度為1的頂點(diǎn)？習(xí)題1. P個頂點(diǎn)的圖中，最多有多少個割點(diǎn)？3證明：有一座橋的三次圖中至少有10個頂點(diǎn)。4.設(shè)v是圖G的一個

13、割點(diǎn)，證明v不是G的補(bǔ)圖Gc的割點(diǎn)。7.有割點(diǎn)的連通圖是否一定不是歐拉圖？是否一定不是哈密頓圖？有橋的連通圖是否一定不是歐拉圖和哈密頓圖。第九章 平面圖和圖的著色習(xí)題1.設(shè)是一個具有個面，個分支的平面圖，則。2. 若G是頂點(diǎn)數(shù)p11的平面圖，試證Gc不是平面圖。4證明：不存在7條棱的凸多面體。習(xí)題1.設(shè)G是一個沒有三角形的平面圖。應(yīng)用歐拉公式證明G中有一個頂點(diǎn)v，使得degv 3。2.設(shè)G是一個沒有三角形的平面圖。應(yīng)用數(shù)學(xué)歸納法證明G是4可著色的。第十章 有向圖習(xí)題2.畫出具有三個頂點(diǎn)的所有互不同構(gòu)的有向圖的圖解。3.具有p個頂點(diǎn)的完全有向圖中有多少條弧？習(xí)題1.設(shè)D是一個有p個頂點(diǎn)q條弧的有向圖。若D是連通的，證明：p-1qp(p-1)。2.設(shè)D是一個有p個頂點(diǎn)q條弧的強(qiáng)連通的有向圖，則q至少是多大？習(xí)題2.有向圖D的圖解如圖10.4.3所示(1)寫出