第一篇集合论
第一章集合及其运算
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∘h
2.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!/2
2.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 是对称的
qe3是什么[定理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-1
3.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 T
3.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.4
9.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))=2q
10.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)-1
10.6判定树
10.7比赛图
定义:：比赛图
[定理10.7.1]每个比赛图必有生成有向路(有哈密顿路)::
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议