集合與圖論復習題

課程內(nèi)容考試時間：14周周日第一大節(jié)考試地點：1111101-2M1021111103-4M104重概念輕理論重計算輕證明1課程內(nèi)容

第一章:集合及其應用第二章:映射第三章:關(guān)系

*第四章:無窮集合及其基數(shù)

*第五章:模糊集合論第六章:圖的基本概念第七章:樹和割集

第八章:連圖度和匹配第九章:平面圖和圖的著色

*第十章:有向圖2第一章：集合及其應用1.1集合的概念1.2子集、集合的相等1.3集合的基本運算1.4余集、DeMorgan公式1.5笛卡爾乘積1.6有窮集合的基數(shù)3第一章：集合及其應用1、設(shè)A、B是集合，證明；A=B=AB證明:AB=(A\B)∪(B\A)必要性顯然,充分性:如果A≠,設(shè)xA,分兩種情況：①xA且xB,則xAB；由B=AB,矛盾②xA,xB,則xAB,xB,矛盾因此A=。*4第二章：映射

2.1函數(shù)的一般概念—映射

2.2抽屜原理

2.3映射的一般性質(zhì)

2.4映射的合成

2.5逆映射*2.6置換*2.7二元和n元運算

2.8集合的特征函數(shù)5

1(p46).設(shè)f:XY,CY,DY,證明:f-1(C\D)=f-1(C)\f-1(D)證：設(shè)xf-1(C\D),則f(x)C\D,也就是f(x)C,f(x)D,也就是xf-1

(C),xf-1

(D),因此:xf-1(C)\f-1(D);反過來設(shè)xf-1(C)\f-1(D),則xf-1(C)且x\f-1(D),也就是f(x)C,f(x)D,f(x)C\D,xf-1(C\D)所以f-1(C\D)=f-1(C)\f-1(D)。第二章：映射6

4(P47)、設(shè)f:XY,AX,BY,以下四個小題中,每個小題均有四個命題，這四個命題中有且僅有一個正確,請找出正確的那個。(1)(a)若f(x)f(A),則x不一定在A中;

(b)若f(x)f(A),則xA;

(c)若f(x)f(A),則xA;

(d)若f(x)f(A),則xAc;(a)正確第二章：映射7(2)(a)f(f-1(B))=B,(b)f(f-1(B))B(c)f(f-1(B))B,(d)f(f-1(B))=Bc(b)正確(3)(a)f-1(f(A))=A,(b)f-1(f(A))A(c)f-1(f(A))A,(d)三個均不對(c)正確(4)(a)f(A)≠,(b)f-1(B)≠(c)若yY,則f-1(y)X,(d)若yY,則f-1(y)X,(d)正確。第二章：映射*8第三章：關(guān)系

3.1關(guān)系的概念

3.2關(guān)系的性質(zhì)

3.3關(guān)系的合成運算

3.4關(guān)系的閉包

3.5關(guān)系矩陣和關(guān)系圖

3.6等價關(guān)系和集合的劃分

3.7映射按等價關(guān)系分解*3.8偏序關(guān)系與偏序集*3.9良序集與數(shù)學歸納法95(P86)、設(shè)R與S是X上的二元關(guān)系,證明:a)(R-1)-1=R;b)(R∪S)-1=R-1∪S-1;d)如果RS,則R-1S-1;c)(R∩S)-1=R-1∩S-1;第三章：關(guān)系10

13(P114)、設(shè)X是一個集合,X=n,試求:

a.X上自反二元關(guān)系的個數(shù);

b.X上反自反二元關(guān)系的個數(shù);

c.X上對稱二元關(guān)系的個數(shù);

d.X上自反或?qū)ΨQ關(guān)系的個數(shù);第三章：關(guān)系11X=n,XX=n2,從(XX)\Ix=n2-n=n(n-1)(XX)\Ix關(guān)系的個數(shù)為2n(n-1)X上自反二元關(guān)系的個數(shù)為2n(n-1);b.X上反自反二元關(guān)系的個數(shù);X上反自反二元關(guān)系的個數(shù)也是2n(n-1);第三章：關(guān)系12設(shè)R是X上對稱的二元關(guān)系;c.X上對稱二元關(guān)系的個數(shù);如果(x,y)R,則(y,x)R,如果xy,則(x,y)與(y,x)只計算一個就行了,X=n,XX=n2,x與y相等的有序?qū)τ衝個x與y不相等的有序?qū)κ莕2-n個x與y不相等的有序?qū)Φ囊话胧?n2-n)/2個X上對稱二元關(guān)系的個數(shù)是2n(n+1)/2;參與計算的有序?qū)κ荹(n2-n)/2]+n=(n2+n)/2第三章：關(guān)系13d.X上自反或?qū)ΨQ的二元關(guān)系的個數(shù);只要求出自反并且對稱的二元關(guān)系的個數(shù)就行了;(XX)\Ix=n2-n=n(n-1)x與y不相等的有序?qū)Φ囊话胧?n2-n)/2個自反并且對稱的元素的個數(shù)是2n(n-1)/2;自反或?qū)ΨQ的元素的個數(shù)是

2n(n-1)+2n(n+1)/2-2n(n-1)/2。X上自反的二元關(guān)系的個數(shù)是2n(n-1);X上對稱二元關(guān)系的個數(shù)是2n(n+1)/2;第三章：關(guān)系*14第六章：圖論的基本概念6.1圖論的產(chǎn)生與發(fā)展概述6.2基本定義6.3路、圈、連通圖6.4補圖、偶圖6.5歐拉圖6.6哈密頓圖6.7圖的鄰接矩陣6.8帶權(quán)圖與最短路問題15

4(P258).(1)有割點的連通圖是否一定不是歐拉圖?(2)是否一定不是哈密頓圖?(3)有橋的連通圖是否一定不是歐拉圖和哈密頓圖?(1)有割點的連通圖有可能是歐拉圖;解(2)一定不是哈密頓圖;(3)有橋的連通圖一定不是哈密頓圖也不是歐拉圖習題16第七章：樹和割集7.1樹及其性質(zhì)7.2生成樹7.3割點、橋和割集17第七章：樹和割集

4(P244).設(shè)G是一棵樹且(G)≥k,證明G中至少有k個度為1的頂點。