3.图论
染色
区间图的染色
独立集
独立数\(\alpha (G)\)的一些下界
图的香农容量
图的强积
匹配与分解
图G的一个匹配M是一组两两无公共顶点的边。
在图G中给定一个匹配M，与M中一条边相关联的每个顶点称为“被浸润的”其它顶点称为“未被浸润的”。
一个浸润了所有顶点的匹配称为图的完美匹配。(图的顶点必须是偶数2t且匹配的边数为t)
- Kn,n中有多少个完美匹配?n!.
- 在偶圈Cn中有两个完美匹配。
- 在K2n中，完美匹配的数目为\(\frac{(2n)!}{2^n n!}\)
- Petersen图中的完美匹配数目? 6.
最大匹配和极大匹配
- 极大匹配:不能再通过添加边来使其变得更大。
- 最大匹配:图的所有匹配中边数最大的（之一）。
- 匹配数m(G):最大匹配的边数。
交错路径与增广路径
-
被称为交错路径（M-alternating path），如果M内和M外之间的边在此路径上交错出现。
-
被称为增广路径（M-augmenting path），如果它本身是交错路径且起点终点都未被浸润。亦即，此路径的边数为奇数且起始的两边在M外。
若有M-增广路径P，则\(M△P\)是一个更大的匹配。如果M是最大匹配，则不可能存在M-增广路径。
图G中的匹配M是最大匹配当且仅当G不包含M-增广路径。
二部图中浸润X的最大匹配存在当且仅当对任意\(S∈X\)有\(|N(S)|>|S|\)。
每个k-正则二部图有完美匹配。
霍尔匹配定理
二部图中浸润X的最大匹配存在当且仅当对任意\(\mathcal{S}\subseteq\text{}X\)有\(\left\vert\textit{N(S)}\right\vert\geq\left\vert\textit{S}\right\vert\)
每个k-正则二部图有完美匹配
相异代表元
给定一个设计(X,3)，其中有b个区组B1,B2,.. . , Bb，一族相异代表元指的是一族不同的顶点x1,x2,...,xb，使得x; ∈ B.
图的因子
图的1-因子分解:将图的边集分拆为一族完美匹配的不交并。
顶点覆盖
顶点覆盖与匹配
线性规划
连通性
Harary图
凯莱图
Whitney定理
网络流
代数图论
邻接矩阵
强正则图
