集合与图论映射

数学奥赛辅导 第六讲 集合与映射知识、方法、技能这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识Ⅰ.有限集元素的数目 1．有限集的阶有限集A 的元素数目叫做这个集合的阶，记作|A|[或n(A)]. 2．集族的阶若M 为由一些给定的集合构成的集合，则称集合M 为集族.设A 为有限集，由A 的若干个子集构成的集合称为集合A 的一个子集族，求满足一定条件的集族的阶是一类常见的问题.显然，若|A|=n ，则由A 的所有子集构成的子集族的阶为2n . Ⅱ.映射，映射法定义1 设X 和Y 是两个集合（二者可以相同）.如果对于每个X x ∈，都有惟一确定的Y y ∈与之对应，则称这个对应关系为X 到Y 的映射.记为.Y y X x Y X ∈→∈→或这时,Y x f y ∈=)(称为X x ∈的象,而x 称为y 的原象,特别当X 和Y 都是数集时，映射f 称为函数.定义2 设f 为从X 到Y 的一个映射.(1)如果对于任何x 1、.),()(,,21212为单射则称都有f x f x f x x X x ≠≠∈ （2）如果对于任何Y y ∈，都有X x ∈，使得f (x )=y ，则称f 为满射; （3）如果映射f 既为单射又为满射，则称f 为双射；（4）如果f 为满射且对任何Y y ∈，恰有X 中的m 个元素x 1、x 2、…x m ，使得.)(,,,2,1,)(倍数映射的倍数为为则称m f m i y x f i ==定理1 设X 和Y 都是有限集，f 为从X 到Y 的一个映射, （1）如果f 为单射，则|X|≤|Y| （2）如果f 为满射，则|X|≥|Y| （3）如果f 为双射，则|X|=|Y|（4）如果f 为倍数为m 的倍数映射，则|X|=m|Y|. 这个定理的结果是显然的.定理2 设有限集f a a a A n },,,,{21 =是A 到A 上的映射，),()(1x f x f =),,)](([)(1*+∈∈=N r A x x f f x f r r 则f 是一一映射（即双射）的充要条件是：对任意).11,()(,)(1,,-≤≤∈≠=≤≤∈∈**i i i s i i m i i i m s N s a a f a a f n m N m A a i 而使得存在证明：必要性.若f 是双射，则i i a a f ==)(1（此时m i =1）,或者.)(11i i i a a a f ≠=在后一种情形下，不可能有.)()(1112i i i a a f a f ==否则，a i 1在A 中有两个原象a i 和a i 1，与f 是双射不合，而只可能有2222)(,,)(),2()(12i i i i i i i i i a a f a a a a f m a a f =≠===如果或者此时，则依同样的道理，不可能有或者此时而只可能有),3()(,,)()(33212====i i i i i i i m a a f a a a f a f213,,)(3i i i i i a a a a a f ≠=.如此等等.因为A 是有限集，所以经过有限次（设经过m 次）后，有i s i i m a ai f a a f i ≠=)(,)(而).11,(-≤≤∈*i m s N s这表明当f 是双射时，对任一A a i ∈都存在着映射圈:i im i i i a a a a a i →→→→-121在这个映射圈中，诸元素互异，且),1(1i i i a m n m 只有一个元素=≤≤充分性.如果对任意i i s i i m i i i i a a f a a f n m N m A a ≠=≤≤∈∈*)(,)(,1,,而使存在)1,(1-*≤≤∈i m s N s ，这说明从A 中任一元素a i 出发，都可以得到一个包含m i 个互异元素的映射圈，显然f 是双射.定理3 在命题1的条件下，若对i i m i i i a a f N m A a =∈∈*)(,,使存在，则对任意.)(,i i tm a a f N t i =∈*有这是明显的事实，证明从略.赛题精讲例1：设集合,30001|{},,14,20001|{≤≤=∈+=≤≤=y y B Z k k x x x A 集合||},,13B A Z k k y ⋂∈-=求.【解】形如4k +1的数的数可分三类：)(912,512,112Z l l l l ∈+++，其中只有形如12l +5的数是形如3k -1的数..167||},1997,,17,5{,1660),(20005121=⋂=⋂≤≤∈≤+≤B A B A l Z l l 所以所以得令例2：有1987个集合，每个集合有45个元素，任意两个集合的并集有89个元素，问此1987个集合的并集有多少个元素.【解】显然，可以由题设找到这样的1987个集合，它们都含有一个公共元素a ，而且每两个集合不含a 以外的公共元素.但是，是否仅这一种可能性呢？由任意两个集合的并集有89个元素可知，1987个集合中的任意两个集合有且仅有一个公共元素，则容易证明这1987个集合中必有一个集合中的元素a 出现在A 以外的45个集合中，设为A 1，A 2，…，A 45，其余的设为A 46，A 47，…，A 1996.设B 为A 46，…，A 1996中的任一个集合，且B a ∉，由题设B 和A ，A 1，A 2，…，A 45都有一个公共元素，且此46个元素各不相同，故B 中有46个元素，与题设矛盾，所以这1987个集合中均含有a .故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素. 例3：集合n B B B A ,,,},9,2,1,0{21 =为A 的非空子集族，并且当,2||≤⋂≠j i B B j i 时 求n 的最大值.【解】首先考虑至多含三个元素的A 的非空子集族，它们共有175310210110=++C C C 个，这说明.175max ≥n下证，.175max ≤n 事实上，设D 为满足题设的子集族，若,,4||,B b B D B ∈≥∈设且 则B 与B-{b}不能同时含于D ，以B-{b}代B ，则D 中元素数目不变.仿此对D 中所有元素数目多于4的集合B 作相应替代后，集族D 中的每个集合都是元素数目不多于3的非空集合，故.175max ≤n .所以，.175max =n在许多问题中，计数对象的特征不明显或混乱复杂难以直接计数，这时可以通过适当的映射将问题划归为容易计数的对象，然后再解决，从而取得化难为易的效果.例4：设},,,2,1{n S =A 为至少含有两项的公差为正的等差数列，其项都在S 中且当将S 的其他元素置于A 中之后，均不能构成与A 有相同公差的等差数列.求这种A 的个数（只有两项的数列也视为等差数列） 【解】当k n 2=为偶数时，满足题中要求的每个数列A 中必有连续两项，使其前一项在集{1,2,…,k}和{k +1,k +2,…,2k }中各任取一数，并以二数之差作为公差可以作出一个满足要求的数列A.容易看出，这个对应是双射.故知A 的个数为.422n k = 当n =2k +1为奇数时，情况完全类似.惟一的不同在于这时第二个集合},2,1{n k k ++ 有k +1个元素.故A 的个数为.4/)1()1(2-=+n k k例5：设a n 为下述自然数N 的个数：N 的各位数字之和为n 且每位数字都只能取1、3或4.求证对每个自然数n ，a 2n 都是完全平方数.【证明】记各位数字之和为n 且每位数字都是1或2的所有自然数的集合为S n ，并记,3,2,1,||2121--+=≥===n n n n n f f f n f f f S 时有且当则这意味着{f n }恰为菲波那契数列.作对应'1M M S n →∍如下：先将M 的数字中自左至右的第一个2与它后邻的数字相加，其和作为一位数字；然后再把余下数字中第一个2与它后邻的数字相加，所得的和作为下一位数字；依此类推，直到无数再相加为止.所得的新自然数M′除最后一位数可能为2之外，其余各位数字均为1、3或4.若记所有M ′的集合为T n ，则容易看出，上述对应是由S n 到T n 的双射，从而有n n n f S T ==||||，且显然有,4,3,2=+=-n a a f n n n ①对于任一数字和为2n ，各位数字均为1或2的自然数M ，必存在正整数k ，使得下列两条之一成立：（1）M 的前k 位数字之和为n ;（2）M 的前k 位数字之和为n -1，第k +1位数字为2.则立即可得 ,3,2,2122=+=-n f f f n n n ② 由①和②得到,2122222--+==+n n n n n f f f a a),(122222----=-n n n n f a f a ③因为.0,2,4,2,12242432=-====f a f a a a 所以于是由③递推即得,,3,2,1,22 ==n f a n n即n a 2为完全平方数.应用映射还可以证明某些与计数相关的不等式和等式.这时可以通过分别计数来证明等或不等，也可以不计数而直接通过适当的映射来解决问题.例6：将正整数n 写成若干个1和若干个2之和，和项顺序不同认为是不同的写法，所有写法种数记为a (n ).将n 写成若干个大于1的正整数之和，和项顺序不同认为是不同的写法，所有写法的种数记为)(n β.求证对每个n ，都有).2()(+=n n βα【证法1】将每项都是1或2，各项之和为n 的所有数列的集合记为A n ，每项都是大于1的正整数，各项之和为n 的所有数列的集合记为B n ，则问题就是证明|,|||2+=n n B A 显然，只需在两集之间建立一个双射就行了.i k ik i i n m a m i i i a a a A a a a a 其余的其中设,1,2,),,,(212121≤<<≤≤====∈= 均为1且令.21n a a a m =+++1211i a a a b +++= ，,22112122121121+++++++++++=+++=+++=--m i i k ik i i k i i i a a a b a a a b a a a b k k k k),,,,,(121+=k k b b b b b①则定义.2+∈n B b2+∈→∍n n B b a A②则f 为双射.事实上，若a a A a a n '≠∈'且,,，则或者数列a 和a ′中的2的个数不同，或者2的个数相同但位置不全相同.无论哪种情形,由①和②知f a f b a f b 即不同与,)()('='=为单射，另一方面，对任何2+∈n B b 利用①式又可确定,n A a ∈使得,,)(为满射即f b a f =从而f 为由A n 到B n +2的双射.【证法2】使用证一中的记号.n n B A 和对于任意的令,),,,,(2121+-∈=n m m A a a a a a,,2;,1,).,,,(11121A a a A a a a a a a m n m m ∈'=∈'=='+-时当时当显然 容易看出，映射 n n n A A a af A ⋃∈'→∍++12是双射，故有).()1()2(n n n ααα++=+注意到2)2(,1)1(==αα，便知,)(n f n =α这里|f n |为菲波那契数列.对于任意的令2121),,,,(+-∈=n k k B b b b b b⎩⎨⎧>-=='--2)1,,,,(2),,,(121121k k k k k b b b b b b b b b b 当当则当,,,2;,2,21容易验证时当时时+∈'>∈'='=n k n k B b b B b b b 映射n n n B B b b B ⋃∈'→∍++12为双射，故有),()1()2(n n n βββ++=+==+n f n )2(β所以a (n )【证法3】显然有),4(2)2(),3(1)1(βαβα===即命题于n =1,2时成立.设命题于,.2,)1(1k n k n k k n =+=≥+≤既然命题于时命题成立须证当时成立令与之间的双射与与故存在时都成立.,,11312+++++f k k k k n f f B A B A k⎩⎨⎧>∈=+2),()()(1k k k k b a f A a a f a f 当当则f 为由.321的双射到+++⋃⋃n n k k B B A A对于任意的令和任意,),,,(),,,,(32212121+++-⋃∈'=∈=k k l k m m B B b b b b A a a a a a⎩⎨⎧==∈='+-,1,,2,),,,(1121m k m k m a A a A a a a a 当当 ⎩⎨⎧∈'∈+∈'∈=++++.,)1,,,)2,,,(34212421k k l k k l B b B b b b B b B b b b b 当当 43212:.:+++++∈→'∍⋃⋃∈'→∍k k k k k k B b b B B h A A a a A g 则映射都是双射，从而复合映射42:++∈→∍k k B b a A g f h为双射，故有)4()2(+=+k k βα，于是由数学归纳法知命题对所有自然数n 都成立.映射法还可以与其他方法结合起来使用，而且大多数竞赛题是这种类型.例如映射法可与抽屉原理、构造法、反证法等各种方法结合起来.例7：设oxyz 是空间直角坐标系，S 是空间中的一个有限点集，S x ，S y ，S z 分别是S 中所有点的坐标平面oyz ，ozx ，oxy 上的正投影所成的集合.求证.||||||||2z y x S S S S ⋅⋅≤（1992年IMO 试题5）【证明】对每点令,),(x S j i ∈∑∈=∈=ixS j i ijij TS S j i x j i x T ),(}},,(|),,{(显然有由柯西不等式有2),(2),(),(2||||||1||ij S j i x ijS j i S j i T S TS xxx∑∑∑∈∈∈⋅=⋅⋅≤①考虑集合},,|),{(),(2121),(ij ij ij ij ij S j i T t t t t T T T T V x∈=⨯⨯=∑∈其中显然，|V|=2),(||ij S j i T x∑∈定义映射f 如下z y S S i x j x j i x j i x V ⨯∈'→'∍)),(),,((),,(),,,(，不难看出f 为单射，因此有||||||z y S S V ⋅≤由①、②即得||||||||2z y x S S S S ⋅⋅≤.例8：设集合},10,,2,1{ =A A 到A 的映射f 满足下列两个条件： ①对任意;)(,30x x f A x =∈②对每个.)(,,291,a a f A a k Z k k ≠∈≤≤∈+使得至少存在一个求这样的映射的总数. (1992年日本奥林匹克预选赛题) 【解】注意到10=5+3+2，30=5×3×2.这提示我们将A 划分成三个不相交的子集},{},,{},,,,{2132154321c c b b b a a a a a A ⋃⋃=.因为f 满足条件①和②，所以f 是A 到A 上的双射，并且由定理2的证明过程得知A 中存在映射圈，因此，定义映射,)(,)(;)(,)(,)(,)(,)(:32211554433221b b f b b f a a f a a f a a f a a f a a f f ======= .)(,)(;)(122113c c f c c f b b f ===因为30是5、3、2的最小公倍数，故由定理2和定理3知f 是满足题目条件①和②惟一的一类映射.因此，f 的总数目相当于从10个元素中选取5个，再从剩下的5个中选取3个，最后剩下的两个也选上，它们分别作圆排列的数目，它等于.120960)!1)(!2)(!4(2235510=⋅⋅⋅C C C例9：设集合A={1，2，3，4，5，6}，映射A A f →:,其三次复合映射f ·f ·f 是恒等映射，这样的f 有多少个？ （1996年日本数学奥林匹克预选赛题）【解】因为集合A 上的三次复合映射是恒等映射，所以定理2和定理3推知符合条件的映射f 有三类：（1）f 是恒等映射；（2）A 中存在一个三元映射圈),,(互异c b a a c b a →→→，而其他三个元素是不动点； （3）A 中存在两个三元映射圈).,,,,,(互异和c b a c b a a c b a a c b a ''''→'→'→'→→→类型（1）的f 只有1个.对于类型（2），先从6个元素中选出3个元素20,,36=C c b a 的方法有种，又a 、b 、c 作圆排列有（3—1）！=2种，故这样的f 有20×2=40个.对于类型（3），首先6个元素平分成两组有10236=÷C 种分法，每组分别作圆排列又有（3—1）！（3—1）！=4种方式，所以这样的f 有10×4=40个. 综上所述，所求的f 有 1+40+40=81个.例10：把正三角形ABC 的各边n 等分，过各分点在△ABC 内作各边的平行线，得到的图形叫做正三角形ABC 的n 格点阵. （1）求其中所有边长为||1BC n的菱形个数； （2）求其中所有平行四边形的个数. （1988年国家集训队选拔考试题） 【解】延长AB 至.||1||||,,BC nC C B B C AC B ='='''使得至作出正三角形C B A ''的n+1格点阵（图I —3—1—1）.边2+''n C B 上有个点，依次编码为0，1，2，…，n+1. 在△ABC 中边长为n1|BC|的菱形可以按边不平 行于BC 、AC 与AB 分为三类.容易看出，这三类 中菱形个数相同.边不平行BC 且边长为n1|BC|的 所有菱形集合记作S.由正整数1，2，…，n 组成 的所有有序的数对（i ,j ）,i <j 所构成的集合记作T.很明显，,||2n C T =设菱形EFGH ∈S ，延长它的两条邻边HG 与GF ，分别交.),(,1,T j i n j i j i C B ∈≤<≤''则与于点令（i ,j ）是菱形EFGH 在S 到T 的映射ϕ下的像，这样便建立了S 到T 的映射ϕ.容易验证，映射ϕ是双射.因此，,||||2n C T S ==所以所求的边长为n1|BC|的菱长个数为32n C . 其次，将平行四边形按边不平行于BC 、AC 与AB 分为三类，这三类的平行四边形个数应相同，边不平行BC 的所有平行四边形集合记作V.非负整数0,1,2,…,n+1构成的所有有序四元数组（i ,j ,k ,l ）,10+≤<<<≤n l k j i 构成的集合记作W.很明显，42||+=n C W .设α是V 中平行的四边形，延长它的四条边分别交l k j i C B ,,,于点''，其中10+≤<<<≤n l k j i ，则ϕαββ的映射到在是令W V W l k j i .),,,(∈=下的像.这样便定义了V 到W 的一个映射ϕ.容易验证，ϕ是双射.因此，.||||42+==n C W V 从而所求平行四边形的个数为423+n C .。

第一篇集合论第一章集合及其运算1.1 集合的概念1.2 子集、集合的相等1.3 集合的基本运算1.4 余集、De Morgan公式1.5 笛卡尔乘积1.6 有穷集合的基数第二章映射2.1 函数的一般概念——映射定义::映射(法则),映射(笛卡尔乘积),限制和扩张,部分映射,映射相等,单射,满射,双射,恒等映射2.2 抽屉原理2.3 映射的一般性质定义::象f(A),原象f-1(A)[定理2.3.1](1)f-1(C∪D)=f-1(C)∪f-1(D);(2)f-1(C∩D)=f-1(C)∪f-1(D);(3)f-1(CΔD)=f-1(C)Δf-1(D);(4)f-1(C C)=(f-1(C))C⊆⊇⊇[定理2.3.2]∪∪(5)f(A B)=f(A)f(B);(6)f(A∩B)f(A)∩f(B);(7) f(AΔB)f(A)Δf(B);(8) f(A\B)f(A)\f(B)2.4 映射的合成定义::映射的合成[定理2.4.1]合成符合结合律,但不符合交换律[定理2.4.2]设f:X→Y,则f∘I X=I Y∘f =f[定理2.4.3]设f:X→Y,g:Y→Z, 则(1)若f与g都是单射,则g∘f也是单射:f是单射,∀x1x2且x1≠x2 y1=f(x1),y2=f(x2)且y1≠y2有g(f(x1))≠g(f(x2))(2)若f与g都是满射,则g∘f也是满射:f满射,∀y必有x∈X使f(x)=y.∀z∈Z必有y∈Y使g(y)=z.则∀z∈Z必有x∈X使g(f(x))=z.(3)若f与g都是双射,则g∘f也是双射[定理2.4.4]设f:X→Y,g:Y→Z, 则(1)若g∘f是单射,则f是单射;∀x1,x2∈X且x1≠x2有g(f(x1)) ≠g(f(x2))(2)若g∘f是满射,则g是满射;反证:∃z∈Z使∀y∈Y,g(y)≠z则有∀x∈X有g(f(x)) ≠z推出矛盾(3)若g∘f是双射,则f是单射且g是满射[定理2.4.5]设f与g都是X到X的映射,则I m (f)⊆I m(g)的充分必要条件是存在一个映射h:X→X使得f=g∘h2.5 逆映射定义::逆映射,左逆映射,右逆映射[定理2.5.1]逆映射存在的充要条件是f是双射::⇒ Ix,Iy+定理2.4.4⇐构造g(y)=x当且仅当f(x)=y[定理2.5.2]逆映射唯一::假设不唯一,推出g=I x°g=(h°f)°g=h°(f°g)=h°I x=h[定理2.5.3] (gf)-1=f-1g-1,(f-1)-1=f:(gf)(f-1g-1)=g(ff-1) g-1= gg-1=I z, (f-1g-1) (gf)=f(gg-1)f-1= ff-1=I x[定理2.5.4](1)f是左可逆的充分必要条件是f为单射:⇒定义+定理⇐f:X→I m(f)的双射,建立g:I m(f)→X双射,在扩充到Y上,y∉I m(x)随便映射一个(2)f是右可逆的充分必要条件是f为满射:⇒定义+定理⇐构造2.6 置换定义::n次置换,k-循环置换,对换,奇置换,偶置换[定理2.6.1][定理2.6.2][定理2.6.3]置换α,β没有共同数字时可以交换[定理2.6.4]置换可进行唯一循环分解[定理2.6.5]置换分解成若干对换的乘积,分解个数的奇偶性不变[定理2.6.6]奇偶置换个数相等,都等于n!/22.7 二元和n元运算定义::有限序列,无限序列,子序列,二元运算,一元运算,n元运算,交换律,结合律,代数系的同构2.8 集合的特征函数定义::集合的特征函数第三章关系3.1 关系的概念定义::关系(映射),关系(笛卡尔乘积),定义域,值域,多部映射,关系(多部映射),多值二元关系3.2 关系的性质定义::自反,反自反,对称(R对称⟺R=R-1),反对称,传递,相容,逆3.3 关系的合成运算定义::关系的合成,[定理3.3.1]关系的合成不符合交换律,但符合结合律[定理3.3.2](1)R1°(R2∪ R3 )=(R1°R2)∪(R1°R3);(2)R1° (R2∩ R3 )⊆(R1°R2)∩(R1°R3);(3)(R2∪R3 )°R4 = (R2°R4) ∪(R3°R4);(4)(R2∩R3 ) °R4⊆(R2°R4) ∩(R3°R4) [定理3.3.3](1)(R∘S)-1 = S-1∘R-1:(2)R∘R-1 是对称的[定理3.3.4]R是传递关系⟺R°R⊆R[定理3.3.5]R0=I x;R1=R;R n+1=R n°R;R m°R n=R m+n;(R m)n=R mn[定理3.3.6]设X是一个有限集合且|X|=n,R为X上的任一二元关系,则存在非负整数s,t,使得0≤s<t≤2n^2且R s= R t[定理3.3.7]设R是X上的二元关系,若存在非负整数s,t,s<t,使得且R s= R t ,则(1)R s+k= R t+k ,k为非负整数(2)R s+kp+i= R s+i ,其中p=t-s,而k,i为非负整数(3)令S={R0,R,R2 ,…,R t-1},则对任意的非负的整数q,有R q ∈S[定理3.3.8]R对称且传递⟺R=R°R-13.4 关系的闭包定义::传递闭包(所有包含R的传递关系的交,可以类似定义自反传递闭包等),自反传递闭包,自反闭包,对称闭包[定理3.4.1]关系R的传递闭包是传递关系(如果R是传递关系,R+=R):[定理3.4.2]R+=∪R i=R∪R2∪R3∪…:: R+⊆∪R i只要证明∪R i是包含R的传递关系, ∪R⊆R+只要证明(a,b)∈R m,(b,c)∈R n.(a,c)∈R m+n,(a,c) ∈R+[定理3.4.3]R+=∪R n=R∪R2∪R3∪…R n::证明R k⊆∪R i,如果k>n,x仅有n个元素,由抽屉原理得存在b i=b j重复以上过程证明.[定理3.4.5]R*=R0∪R+3.5 关系矩阵和关系图定义:: (1)R是自反的,当且仅当B的对角线上的全部元素都为1;(2) R是反自反的当且仅当B的对角线上的全部元素都为0;(3) R是对称的当且仅当B是对称矩阵;(4) R是反对称的当且仅当b i j与b j i不同时为1,i≠j;(5) R是传递的当且仅当若b i j=1且b j k=1,则b i k=1; (6) R-1的矩阵是B T3.6 等价关系和集合划分定义::等价关系(1.自反2.对称3.传递),等价类,商集[定理3.6.3]3.7 映射按等价关系划分3.8 偏序关系和偏序集定义::偏序关系(自反,反对称,传递),偏序集,全序集,Hasse图,上下界,最大最小元素,链与反链第四章无穷集合及其基数4.1可数集定义::可数集(从自然数集N到集合A有一一映射),无限集(能与自身的真子集对等的集合),代数数,超越数[定理4.1.1]集合A为可数集⟺A的全部元素可以排成无重复项的序列[定理4.1.2]无限集中包含可数子集[定理4.1.3]两个可数集的并是可数集[定理4.1.4]有限个可数集的并是可数集[定理4.1.7]可数个可数集的并是可数集:写成无穷阶方阵,按对角线游历[定理4.1.8]有理数集Q是可数集[定理4.1.10]一列有限个集合的笛卡尔乘积为可数集4.2连续统集定义::连续统(与[0,1]实数集对等)[定理4.2.1]区间[0,1]内的全体实数构成不可数无穷集::康托对角线第二篇图论第六章图的基本概念6.1图论的产生与发展概述6.2基本定义定义::无向图,G(p,q),平凡图,零图,有向图,定向图,子图,生成子图,导出子图,图的同构,度(degv),δ(G),Δ(G),正则图(推论三次图的顶点个数为偶数)[定理6.2.1]欧拉定理:Σ(degv)=2q推论度为奇数的点的个数必为偶数6.3路、圈、连通图定义::通道,闭通道,迹,闭迹,路,圈(回路),连通图,支[定理6.3.1]uv有路⟺u≅v[定理6.3.2]degu+degv≥p–1⟹G连通::拆成两个支用结论反证,degu≤n1-1,degv≤p-n1-1推出与结论的矛盾[定理6.3.3]∀v∈V,degv为偶数⟹G中有圈::设最长路证明[定理6.3.4]∃u,v中有两条不同路⟹G有圈::6.4补图、偶图定义::补图,自补图,三角形,偶图,完全偶图(Km,n), 图上两点间的距离d(u,v)[定理6.4.1]R(3,3)≤6::抽屉原理+[定理6.4.2]偶图判断的充要条件:图上所有的圈的长度都为偶::⇒将圈上的奇偶序的点放入两个顶点划分中⇐取定一点按距离奇偶构造[定理6.4.3](Turan定理)p个顶点没有三角形的图至多有[p^2/4]::6.5欧拉图定义::欧拉闭迹,欧拉图,欧拉迹[定理6.5.1]欧拉图存在定理:G的每个顶点的度都为偶::⇒显然⇐结合定理6.3.3造N个圈Zi然后数归证明这些圈相接.推论::欧拉图的等价命题: 1)G是欧拉图2)∀v∈V,degv为偶数3)G的边能划分成若干不相交的圈.[定理6.5.2]欧拉迹存在定理:: ⇒从定理6.5.1获得⇐uv奇数度,加edge(u,v)得欧拉迹C,在C上去掉edge(u,v).6.6哈密顿图定义::哈密顿圈、哈密顿图[定理6.6.1]G是Hamilton⟹∀S∈V有ω(G-S)<|S|[定理6.6.2](Dirac定理)p个顶点的图G,δ(p)≥p/2,⟹G是一个哈密顿图.[定理6.6.3](Ore定理)p个顶点的图,∀u,v(u,v不邻接),均有degu+degv≥p⟹G是哈密顿图.[定理6.6.4]p个顶点的图,∀u,v(u,v不邻接),均有degu+degv≥p-1⟹G是哈密顿图.6.7图的邻接矩阵[定理6.7.1]图同构的邻接矩阵判定[定理6.7.2]ij顶点间长l的通道条数=A l(i,j)::数归l,[定理6.7.3]G(p,q),连通⟺(A+I)^(p-1)>0::⇒定理6.7.2⇐定理6.7.2第七章树和割集7.1树及其性质定义::树,极小连通图(推论树是极小连通图), 偏心率,树的半径,树的中心[定理7.1.1]树的六个等价命题:1)树;2)G中任两点有且只有一条路;3)G连通且p=q+1; 4)G无圈且p=q+1;5)G无圈且其中任意不相邻两点加边得唯一的圈;6)连通(p≥3且G非Kp)且其中任意不相邻两点加边得唯一的圈.推论非平凡树至少有两个度为1的顶点且非平凡树是偶图::偶图判断的构造证明法[定理7.1.2]树的中心的位置7.2生成树定义::生成树, 生成森林, 生成树的距离,生成树的基本变换[定理7.2.1]生成树存在⟺G连通::⟹显然⟸破圈法.推论G连通⟹q≥p-1[定理7.2.2](Cayley定理)Kp的生成树的个数=p(p-2)[定理7.2.3]生成树中去掉边集E1后必能找到另一不在原生成树中的边集E2使T-E1+E2为生成树[定理7.2.4]距离为k的两个生成树可以经过k次基本变换互相得到::数归,由定理7.2.3知,d(T0,T)=k去掉e1后必然有e2∉T0使(T0-e1)+e2=T1,而d(T1,T)=k-1得到归纳.7.3割点、桥和割集定义::割点,桥,割集(有极小性)[定理7.3.1]割点的等价命题:1)v是割点;2)∃u,w≠v使uw间所有路经过v;3)∃划分{U,W} UW间所有路经过v;[定理7.3.2]桥的等价命题:1)x是桥;2)x不在G的任何圈上3)∃u,v使x在连接uw所有路上;4)∃划分{U,W},使x在连接UW所有路上; [定理7.3.4]割集将图分成两个支(推论有k个支的图G去掉割集后有k+1个支)[定理7.3.5]割集必然包含生成树的某条边::反证[定理7.3.6]割集与G中的圈必有偶数条公共边::G1G2取定一点周游,e(u,v)(u∈G1,v∈G2)是圈与割集相交的边第八章连通度和匹配8.1顶点连通度和边连通度定义::κ(G), λ(G), n-连通,n-边连通[定理8.1.1]κ(G)≤λ(G)≤δ(G)[定理8.1.2]κ(G)=a,λ(G)=b,δ(G)=c的构造方法:构造两个Kc+1,用b条边连接这两个支[定理8.1.3]G(V,E)有p个顶点且δ(G)≥ [p/2]⟹λ(G)=δ(G)::[定理8.1.4][定理8.1.5]∀u,v∈V且u,v∈C⟺G是2-连通[定理8.1.6]8.2门格尔定理8.3匹配、霍尔定理定义::匹配,最大匹配,偶图G的完备匹配,相异代表系, 完美匹配[定理8.3.1](Hall定理)::[推论8.3.1]第九章平面图和图的着色9.1平面图及其欧拉公式定义::平面图,面,内部面,外部面[定理9.1.1]欧拉定理:平面图有p-q+f=2::通过f数归[推论9.1.1]每个面都由长为n的圈围成⟹q=n(p-2)/(n-2)::每条边都与两个面邻接⟹2q=nf拓展最大可平面图[推论9.1.2]G(p,q)的最大可平面图每个面都是三角形且q=3p-6[推论9.1.3]每个面都由长为4的圈围成⟹q=2p-4::拓展没有三角形的边极大图[推论9.1.4]G(p,q),q≤3p-6,G没有三角形q≤2p-4[推论9.1.5]K5和K3,3都是不可平面图::K5,f=7,由于每个面至少三条边, K3,3中每个圈至少为4[推论9.1.6]G可平面⟹ (G)≤5::反证+推论9.1.49.2非哈密顿平面图[定理9.2.1]Grinberg定理:G(V,E)是(p,q)平面哈密顿图,C是哈密顿圈.令fi为C的内部由i条边围成的面的个数,gi为C的外部由i条边围成的面的个数则(1)Σ(i-2)fi=p-2;(2) Σ(i-2)gi=p-2;(3) Σ(i-2)(fi-gi)=0;9.3库拉托斯基定理、对偶图定义::细分,同胚,初等收缩,对偶图[定理9.3.1](Kuratowski定理)G可平面⟺G没有同胚于K5或K3,3的子图[定理9.3.2](Wagner定理) G可平面⟺G没有收缩到K5或K3,3的子图9.4顶点的着色定义::n-可着色,色数(有极小性),χ(G)[定理9.4.2]Δ=Δ(G),G是(Δ+1)- 可着色的.[定理9.4.3-定理9.4.5]平面图可以4着色9.5边的着色定义::n-边着色,边色数(有极小性), χ’(G)第十章有向图10.1有向图的概念定义::有向图,弧,对称弧,定向图,带环图,多重有向图,有向图的反图,入度(id(v)),出度(od(v)),完全有向图,有向图的补图,有向图的同构[定理10.1.1]Σid(v)= Σod(v)=q且Σ(id(v)+od(v))=2q10.2有向路和有向圈定义::有向通道,有向闭通道,生成通道,有向迹,有向闭迹,生成(闭)轨迹,有向路,有向圈,有向回路,可达,半(弱)通道,强连通,强支,单连通,弱连通,有向图的连通[定理10.2.1]有向图D是强连通的⟺D有一条闭生成通道[定理10.2.2]uRv当且仅当uv可互达⟹R是V上的等价关系[定理10.2.3]有向图D的每个顶点都在D的一个强支中[定理10.2.4]一个没有有向圈的有向图至少有一个出度为0的顶点[定理10.2.5]有向图D没有圈⟺D中每条有向通道都是有向路[定理10.2.6]有向图D有有向圈⟺D的子图D1(V1,E1),∀v∈V1,id(v)>0,od(v)>0[定理10.2.7]连通有向图D,∀v∈V,od(v)=1,D中恰有一个有向圈10.3强连通图的应用10.4有向图的邻接矩阵定义::有向图的邻接矩阵,可达矩阵,关联矩阵10.5有向树与有序树定义::有向树,有根树,入树,父,子,祖先,真祖先,深度,高度,子树,有序树,m元有序树,正则m元有序树,正则二元树,二元树,满二元树,完全二元树(高为h的二元树,去掉深度为h一层,得到满树,而且h层从左向右排布)[定理10.5.1]有向图D是有根树⟺D没有弱圈且D中存在一个可以到达其他顶点的顶点(root)::⇒化为无向图证明没有弱圈,用除根以外的点入度为1证可达.⇐[定理10.5.3]高为h的二元树至多有2 (h+1)-1个顶点[定理10.5.4]高为h的完全二元树的顶点数满足2h≤p≤2(h+1)-110.6判定树10.7比赛图定义::比赛图[定理10.7.1]每个比赛图必有生成有向路(有哈密顿路)::。

《集合论与图论》课程教学大纲一、课程基本信息课程编号：CS31111课程名称：集合论与图论英文名称：SET THEORY AND GRAPH THEORY课程学时：64；讲课学时： 48；实验学时：上机学时：习题学时：16;课程学分：4.0开课单位：计算机科学与技术学院授课对象：计算机大类专业（包括计算机科学与技术、物联网工程、生物信息学、信息安全）、软件工程大类专业开课学期： 1春先修课程：工科数学分析、线性代数二、课程目标《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课程。

本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。

该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。

要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。

集合论与图论为此提供了强有力的描述工具与推理理论。

本课程的目标是通过理论学习，为计算机科学与技术专业的后继课及将来的科学研究提供必要的相关数学知识，提供建立离散系统的数学模型的数学描述工具；使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系；引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。

课程具体目标如下：课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想；课程目标3：掌握资料查阅方法，学会对课堂所学理论知识进行扩展，培养自学能力。