下载文档原格式
图论引导笔记第⼋章匹配与分解8.1 匹配定义：1、（边的集合）独⽴的：G.E的⼀个⼦集，且该集合中的任意两条边不相邻接。
称边独⽴集。
2、匹配（matching）：图G的⼀个独⽴集。
3、匹配（match）：⼆部图的两个部集的点集之间的⼀种映射关系，该映射关系满⾜于所连接的边是⼀个匹配（matching）*以下考虑的是⼆部图G，他的两个集部是U和W，且|U|≤|W|，X是U的⾮空⼦集4、（⾮空点集的）邻域：集合中所有顶点邻域的并。
设集合为X，记作N（X）5、（集部是）友好的：对于集部U，他的任意⾮空⼦集X，都有|N(X)|≥|X|。
（翻译⼀下就是说，在这个部⾥任意取⼀部分点都能形成匹配）6、互异代表元系：有⼀串⾮空有限集合{S1,S2,…,Sn}，存在n个不同的元素{x1,x2,…,xn}使得xi∈Si,则这串{xi}称为互异代表元系。
（⽽不是指；仅仅这个集合有别的集合没有。
显然，|∪{Si}|≥n）7、（⼆分图）交错路：⼀条属于匹配的边和⼀条不属于匹配的边交错构成的路。
8、（任意分图）最⼤匹配：具有最⼤基数的匹配, 对于n阶⼆分图，最⼤匹配数不会超过floor(n/2)9、完美匹配：（此处讨论⼆分图）G的阶数为偶数，匹配基数等于n/2，G中任意顶点均能通过M匹配到G中另⼀个顶点。
完美匹配也必定是最⼤匹配。
使⽤：完美匹配要求图的⼀个集部是友好的和边有关的加<'>,和点有关的不加。
11、边独⽴数：G 中边独⽴集的最⼤基数。
记作β'(G)。
阶为n的图存在完美匹配当且仅当n为偶数且β'(G)=n/2.12、覆盖：顶点与其关联边，互为彼此的覆盖。
13、边覆盖：覆盖G所有点的边的集合，称为是G的⼀个边覆盖。
14、边覆盖数：G中所有边覆盖最⼩的基数，记作α'(G)，当且仅当G不包含孤⽴点的时候有定义。
15、最⼩边覆盖：具有最⼩边覆盖基数的边覆盖。
边覆盖/独⽴有关的⼀些性质：对于整数n≥3，1≤r≤s，边覆盖数有：α'(Cn)=α'(Kn)=ceiling(n/2); α'(K_r,s)=s边独⽴数有：β'(Cn)=β'(Kn)=floor(n/2); β'(K_r,s)=r所以：α'(Cn)+β'(Cn)= α'(Kn)+β'(Kn)=n; α'(K_r,s)+ β'(K_r,s)=r =s+r以上性质很显然可以看出来。
