子集及集合相等

集合的相等与子集关系集合是数学中一种重要的概念，它是由一些确定的对象按某种特性定相同加以归纳而成的整体。

在集合的运算中，相等和子集关系是两个基本的概念。

本文将探讨集合的相等及子集关系，并探讨它们在数学和日常生活中的应用。

一、集合的相等在集合的定义中，集合内的元素是无序的，所以两个集合要判断是否相等，只需要判断它们的元素是否完全相同即可。

若两个集合A和B的所有元素相同，则称集合A和集合B相等，记作A=B。

例如，设集合A={1, 2, 3}，集合B={2, 3, 1}，由于集合中的元素无序，集合A和集合B是相等的。

在实际应用中，集合的相等常用于数据库的查询和数据比对等场景，能够帮助我们快速准确地筛选出符合要求的数据。

二、集合的子集关系集合的子集关系是指一个集合的所有元素都包含在另一个集合中。

设集合A和集合B，若A中的所有元素都属于B，则称集合A是集合B的子集，记作A⊆B。

例如，设集合A={1, 2}，集合B={1, 2, 3}，由于集合A中的元素都包含在集合B中，所以集合A是集合B的子集。

在实际生活中，子集关系常常用于描述一组物体或概念的层级关系。

例如，在一个学校的学生集合中，可以将某个班级的学生集合看作是整个学校学生集合的子集。

三、集合相等与子集关系的性质1. 自反性：集合A和集合A相等，即A=A；集合A是集合A的子集，即A⊆A。

2. 对称性：若集合A=B，则集合B=A；若集合A是集合B的子集，则集合B是集合A的子集。

3. 传递性：若集合A=B，且集合B=C，则集合A=C；若集合A是集合B的子集，且集合B是集合C的子集，则集合A是集合C的子集。

这些性质在集合的运算中具有重要的作用，能够帮助我们推导和证明集合相等和子集关系的性质。

四、集合相等与子集关系的应用集合的相等和子集关系在数学和其他学科中有广泛的应用。

以下是一些常见的应用场景：1. 集合论：在数学的基础理论中，集合的相等和子集关系是研究集合运算和集合性质的基础。

集合间的基本关系知识点总结一、子集、真子集、集合相等二、空集1、定义：不含任何元素的集合叫做空集，记作φ.2、性质：空集是任何集合的子集.三、子集个数与元素个数的关系设有限集合A 有n （n 属于*N ）个元素，则其子集的个数是n 2，真子集的个数是12-n ，非空子集的个数是12-n ，非空真子集的个数是22-n .一、知识辨析1、} 3 ,2 ,1 {1⊆...........................................（ ）2、φ和{φ}表示的意义相同...............................（ ）3、} )1 ,0( {} 0 ,1 {} 1 ,0 {==..................................（ ）4、任何集合都有子集和真子集.............................（ ）5、若a ∈A ，则}{a ⫋A.....................................（ ）6、如果集合A B ⊆，那么若元素a 不属于A ，则必不属于B.....（ ） 二、选择1、已知集合} | {是菱形x x A =，} | {是正方形x x B =，} | {是平行四边形x x C =，那么A ，B ，C 之间的关系是 （ ）A.C B A ⊆⊆B.C A B ⊆⊆C.A ⫋B ⊆CD.C B A ⊆=2、给出下列四个关系式：①R ∈3；②Z ∈Q ；③0∈φ；④φ⊆} 0 {.其中正确的个数是 （ ）A.1B.2C.3D.43、能正确表示集合} 20| {≤≤∈=x R x M 和集合} 0x -| {2=∈=x R x N 关系的Venn 图是 （ ）A B C D4、已知集合} ,2| {Z k k x x A ∈==，} ,4| {Z k k x x B ∈==，则A 与B 之间的关系是（ ） A.A=B B.B ⊇A C.A ⫋B D.B ⫋A5、已知集合} 03| {*＜-∈=x N x A ，则满足条件A B ⊆的集合B 的个数为（ ） A.2 B.3 C.4 D.86、已知集合} 2 ,1 ,0 {⊆A ，且集合A 中至少含有一个偶数，则这样的集合A 的个数为 （ ） A.6 B.5 C.4 D.37、集合} , {y x 的子集个数是 （ ） A.1 B.2 C.3 D.48、在下列选项中，能正确表示集合} 2 ,0 ,2 {-=A 和集合} 02| {2=+=x x x B 关系的是 （ ） A.A=B B.B A ⊇ C.B A ⊆ D.B A =φ 9、集合} 1 ,2 {-=A ，} 1 ,m {2--=m B ，且A=B ，则实数m=（ ） A.2 B.-1 C.2或-1 D.410、已知集合} 0y ,0y |y)(x, {＞＜x x M +=，} 0y ,0|),( {＜＜x y x P =，那么 （ ） A.P ⫋M B.M ⫋P C.M=P D.M ≠P11、下列四个关系：①} , {} , {a b b a ⊆；②φ=} 0 {；③} 0 {∈φ；④} 0 {0∈.其中正确的个数为（ ）A.1B.2C.3D.412、已知φ⫋} 0x | {2=+-a x x ，则实数a 的取值范围是 （ ） A.41＜a B.41≤a C.41≥a D.41＞a 13、设集合} 1 1, {-=A ，集合} 02| {2=+-=b ax x x B ，若B ≠φ，A B ⊆，则有序实数对（a,b ）不能是（ ）A.（-1,1）B.（-1,0）C.（0，-1）D.（1,1） 三、填空14、已知集合} 3, 1, {m A -=，} 4 3, {=B ，若A B ⊆，则实数m= .15、已知集合} ,02| {2R a a ax ax x A ∈=++=，若集合A 有且仅有2个子集，则a 的取值构成的集合为 .16、设a ，b ∈R ，集合} ,0 {} 1 , {b a a +=，则a b -= . 四、解决问题17、已知集合} 4 1| {＞或＜x x x A -=，} 3a 2| {+≤≤=x a x B ，若A B ⊆，求实数a 的取值范围.18、已知} 01)1(3| {22=-+++=a x a x x A ，} 0 {=B ，若B A ⊆，求a 的取值范围.19、若集合} 06| {2=-+=x x x M ，} 0))(2(| {=--=a x x x N ，且M N ⊆，求实数a 的值. 提升题 一、选择题1、下面各选项中，两个集合相等的是 （ ）A.} ) 2 ,1 ( {=M ,} ) 1 ,2 ( {=NB.} 2 ,1 {=M ，} ) 2 ,1 ( {=NC.M=φ，} {φ=ND.} 012| {2=+-=x x x M ，} 1 {=N 2、下列关系中正确的是（ ）A .} 1 ,0 {1∈ B.} 1 ,0 {1∉ C.} 1 ,0 {1⊆ D.} 1 ,0 {} 1 {∉ 3、已知集合} 02| {2＜-+∈=x x Z x A ，则集合A 的一个真子集为 （ ） A.} 02| {＜＜x x - B.} 20| {＜＜x x C.} 0 { D.} {φ 4、集合} 1 ,0 1, {-=A ，A 的子集中含有元素0的子集共有（ ） A.2个 B.4个 C.6个 D.8个5、若P M ⊆，Q M ⊆，} 2 1, ,0 {=P ，} 4 2, ,0 {=Q ，则满足上述条件的集合M 的个数是（ ） A.1 B.2 C.4 D.86、集合} , 3| {N n x x M n ∈==，集合} , 3| {N n n x x N ∈==，则集合M 与集合N 的关系为（ ） A.N M ⊆ B.M N ⊆ C.N M = D.M ⊈N 且N ⊈M7、若A x ∈，A x ∈1，则称A 是伙伴关系集合.集合} 3 ,2 ,31,21 ,0 ,1 {-=M 的所有非空子集中具有伙伴关系的集合的个数是（ ） A.31 B.7 C.3 D.18、已知集合} , 0| {N y a y y A ∈≤=＜，} , 032| {2N x x x x B ∈≤--=，若A ⫋B ，则满足条件的正整数a 所构成集合的子集的个数为（ ） A.2 B.4 C .8 D.16 二、填空9、方程0822=--x x 的解集为A ，方程02=-ax 的解集为B ，若A B ⊆，则实数a 的取值集合为 .10、已知集合} 44 ,4 ,3| {-=m y A ，集合} ,3| {2m y B =，若A B ⊆，则实数m= . 三、解决问题11、已知} 52| {≤≤-=x x A ，} 121| {-≤≤+=m x m x B ，A B ⊆，求m 的取值范围.。

高中知识点之集合一、集合的有关概念⒈定义：一般地，我们把研究对象统称为元素，一些元素组成的总体叫集合，也简称集。

2.表示方法：集合通常用大括号{ }或大写的拉丁字母A,B,C…表示，而元素用小写的拉丁字母a,b,c…表示。

3.集合相等：构成两个集合的元素完全一样。

4.元素与集合的关系：(元素与集合的关系有“属于∈〞及“不属于∉两种)⑴假设a是集合A中的元素，那么称a属于集合A，记作a∈A；⑵假设a不是集合A的元素，那么称a不属于集合A，记作a∉A。

5.常用的数集及记法：非负整数集〔或自然数集〕，记作N；正整数集，记作N*或N+；N内排除0的集.整数集，记作Z；有理数集，记作Q；实数集，记作R；6.关于集合的元素的特征⑴确定性：给定一个集合，那么任何一个元素在不在这个集合中就确定了。

如：“地球上的四大洋〞〔太平洋,大西洋，印度洋，北冰洋〕。

“中国古代四大创造〞〔造纸，印刷，火药，指南针〕可以构成集合，其元素具有确定性；而“比拟大的数〞，“平面点P周围的点〞一般不构成集合，因为组成它的元素是不确定的.⑵互异性：一个集合中的元素是互不相同的，即集合中的元素是不重复出现的。

.如:方程(x-2)(x-1)2=0的解集表示为{1,-2},而不是{1,1,-2}⑶无序性：即集合中的元素无顺序,可以任意排列、调换。

7.元素与集合的关系：(元素与集合的关系有“属于∈〞及“不属于∉〞两种)⑴假设a是集合A中的元素，那么称a属于集合A，记作a∈A；⑵假设a不是集合A的元素，那么称a不属于集合A，记作a∉A。

二、集合的表示方法⒈列举法：把集合中的元素一一列举出来, 并用花括号“{}〞括起来表示集合的方法叫列举法。

如：{1，2，3，4，5}，{x2，3x+2，5y3-x，x2+y2}，…；说明：⑴书写时，元素与元素之间用逗号分开；⑵一般不必考虑元素之间的顺序；⑶在表示数列之类的特殊集合时,通常仍按惯用的次序；⑷集合中的元素可以为数，点，代数式等；⑸列举法可表示有限集，也可以表示无限集。

1.1集合及子集的有关概念一、 考纲解析与复习目标：理解集合、子集的概念，了解空集的意义，了解属于、包含、相等 关系的意义，掌握有关术语和符号，并会用它们正确表示集合 二、 知识梳理：1、集合的基本概念： （1） 一般地，我们把 _________ 统称为元素，-把 _________ 组成的 _______ 叫做集合•集合中的元素具 有 ___________ 性、___________ 性、 __________ 性等特性.（2） ____________________________________ _______________________ 叫空集，记作 . （3） 集合表示方法主要有 ________ 法、 ________ 法，也常用区间和文氏图表示集合.（4）常见数集符号： N g ,N ,Z,Q,R,C（5）元素与集合之间的关系：“属于”、“不属于”，符号表示为 2、集合与集合的关系： （1） 子集的概念（AUB ）: ______________________________ . （2） 子集的性质：① ________ ，② ___________ ，③ ______________ . （3） 真子集、集合相等的概念及符号表示： _____________________ .（4） _______________________________________________________________ 含n 个元素的集合 A 的所有子集的个数是 _______________________________________________________ 3、几点注意：（1）考虑集合问题应有“空集优先”意识； （2）集合用描述法表示时，要分析代表 元素是什么，尤其分清“数集”与“点集” ，还要分析清楚元素的限制条件； （3）集合中的确定参 数值的问题，要注意集合中元素性质的检验；（4）解题时注意分类讨论、 数形结合等数学思想方法三、典型例题：（2）下列命题中真命题的个数是 _______ 个2、用列举法表示下列集合 1、（ 1）下列选项不能形成集合的的是A 、大于2的全体实数 （）B 、不等式3x 5 2的所有解C 、直线y 3x 1上所有点D 、x 轴附近的点①0 ② { }③0 {0}④ {a}⑤{0}(3)设集合A {x, x 2x ｝，则x 须满足的条件是(1) Ax Z(2) B{y y (3) C{(x,y)6, xN,y N}，x 2 6,x N g , y N g }，(4) D {(x,y)x y 6,x N g , y N g }2x ax bx 1 0, x R} {1}求 a,b 的值;(5)设 A{a,b}, E {B BA ｝，则、设集合 A {x R X a bV2,a (1) X0 ；( 2) x1；（3） x1(5) x X 1X 2其中X 1A,X 2 A .（列举法表示）.Z,b Z ｝，判断下列元素x 与A 的关系:X iX 2其中X 1 代 X 2 A ；5、 A.6、 A {x y {(x,y) y设集合M xM N B. M,2x 1}1｝，试讨论(1)已知 A {a 2,(a (2)已知 M {2, a,b}, N {y y■ x 2 1} ， C {(x, y)A 与B 、C 与D 之间的关系. k 1x 4 2,k z ，则(N D. M N1)2,a 2 3a3｝且1 A ，求实数a 的值;{2a,2,b 2}且 M N ，求 a,b 的值;y ■ x 2 1}，(3)设{7、设 A {x x 2 2x 30,xR}, B｛x a x 2a 1｝, B A ，求a 的取值范围.8、已知｛1｝ A ｛1,2,3,4,5｝，求（1） 满足条件的所有集合 A 的个数；（2） A 中所有元素之和为奇数的集合A 的个数.9、设A R 且满足：若a A ，则丄1 a(1) (2)(3) 若2 A ，问A 中还有哪些元素？A 中能否只有一个元素，若可以求出 A ，若不可以说明理由•若A 是非空数集，则 A 中最少有几个元素？10、 设 A {x 2 x a,a 2}, B {y y 2x 3, x A}, C {y y x 2, x A}，求使E3 L 1l ( 4) X.3 . 26•设 A {x x 2 2x 30}, B {x ax 10},，若 A B ，则 a ______________ .7•元素为正整数的集合 S 满足命题：“若x S ,则8 x S ” . （1） 试写出只有一个元素的集合S ；（ 2）试写出元素个数为 2的集合S ；（3）满足上述命题的集 S 共有多少个？2x 18.（ 1） A x||x a 2 ,B1 ，若A B ，则a 的取值范围是 ____________1x 2（2） ___________________________________________________________________________ M {x1 x 3}, N {x x a}，若M N ，则a 的取值范围是 _______________________________________ ；C B 时a 的取值范围四、巩固练习：1•非零实数a,b,c 构成的数 abc——；，则m 组成的集合M 的真子集的个数是（）abcA 、8B 、7C 、4D 、22•设 M {a,a d,a 2d}, N2{a,aq,aq }其中 a 0.M N 则实数q 的值为 3.A {a,b},B {a,b,c,d,e,f}，则满足A M B 的集合M 有24.已知集合A {x ax 2x1 0}，且 A R ，（1）若A ，求a ；（ 2）若A 中只有一个元素，求 a ；（ 3 ）若A 的子集至多有两个，求 a . 5. ( 1) A {x x2a 1,a R}, B b 2 2b,b R},则集合 A 与B 的关系是{x2 0,xR}，则C 与A 的关系是 (2) A {y y4x5, xN g }， B {yx 21,x N g }则 A 与 B的关系是1,3]}, B{y y4x, x 1,3]} C {(x, y) y[1,3]},D {( x, y) y 4x,x1,3]},则A 与B 的关系是C 与D 的关系是(3) P {(x,y)||x 1,且 y 1},Q {(x,y) x 2 a,a 0}，若P Q ，则a 的取值范围2 9.设 A {x x 4x 0, x R}, B {x x22(a 1)x a 2 1 0,a R,x R}，若 B A ，求a 的值. 10、已知 f (x) px q,(p,q R), A {x x f(x)}, B x}(1)求证：A (2) A { 1,3}，求集合 B . 1.1参考答案 三、典型例题： 1、D ; 2、(1) {-4,-1,0,134,5,8} ; ( 2) {6,5,2}; (3) { (2,2) , (1,5) (3,3) , (4,2) , (5,1) }; (5) { ,{a},{b},{a,b}} ; 3、略；4、，； 5、B ; ,(0,6) }; ( 4) { (1,5) , (2,4), 6、(1) a=0; (2)1a=0,b=1;或 a= l ,b=2; (3) a=0,b=-1;或 a=1,b=-2; 7、1; 8、(1) 15 个；(2) 7 个；9、(1) A ,则 而 (2)若A 中只有一个元素 a ,贝U由于」| I 卩无实根，故A 不能只含一个元素; (3)，且，故A 中最少有3个元素.10、 四、巩固练习：1、 B ；2、3、 15 ；4、( 1) a>1;( 2) a=0 或 a ：M 1.5、( 1) ； ^ '；a=0 或 a=1; (3) 1不包含 D , D 不包含 C.6、0 或-1 或.7、( 1) {4}; (2) {1,7}, {2,6} , {3,5}; ( 3) ；(3) I ； 1； (3)忙尸； 15 个.8、(1)：；；儿—1; (2) 所以 = f(x) = x ,所以 tEBA 匚“；(2 )由题意得 p=-1 ,q=-3,所以 B{ _ 1，3’ -J 引a<-1 1-.9、：'J'或 a=1.10、( 1)设X 討，则L ；Q -。

高中数学数集符号高中数学中，数集符号是一种用于描述和表示数集的特殊符号。

这些符号可以帮助我们更清晰地定义数集，并进行相关运算和分析。

1. 包含关系符号：- （子集）：表示一个集合中的所有元素都是另一个集合的元素，但是两个集合可以不相等。

例如，若集合A是集合B的子集，则表示为AB。

- （子集或相等）：表示一个集合中的所有元素都是另一个集合的元素，且两个集合可以相等。

例如，若集合A是集合B的子集或相等，则表示为AB。

2. 关系符号：- ∈（属于）：表示一个元素属于某个集合。

例如，若元素x属于集合A，则表示为x∈A。

- （不属于）：表示一个元素不属于某个集合。

例如，若元素x不属于集合A，则表示为xA。

3. 运算符号：- ∪（并集）：表示两个或多个集合中所有的元素的集合。

例如，集合A和集合B的并集为A∪B。

- ∩（交集）：表示两个或多个集合中共有的元素的集合。

例如，集合A和集合B的交集为A∩B。

- （差集）：表示从一个集合中移除包含在另一个集合中的元素，得到的剩余元素的集合。

例如，集合A和集合B的差集为AB。

4. 其他符号：- （自然数集）：表示所有正整数的集合。

例如，2∈表示2是自然数集的元素。

- （整数集）：表示所有整数的集合。

例如，-3∈表示-3是整数集的元素。

- （有理数集）：表示所有可以表示为两个整数的比值的数的集合。

例如，1/2∈表示1/2是有理数集的元素。

- （实数集）：表示所有实数的集合。

例如，√2∈表示根号2是实数集的元素。

通过使用这些数集符号，我们可以更加准确地描述和操作数集，从而更好地理解和解决数学问题。

数集符号在高中数学的各个领域都有广泛的应用，例如集合论、数列、函数等等。

第一篇集合论第一章集合及其运算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]每个比赛图必有生成有向路(有哈密顿路)::。