付费大佬可以联系我把你们加入思维导图协作，看更加具体清楚地思维导图/敬礼

（思维导图在最后，可以直接看图不看文字）

5.1 匹配

• 匹配（边独立集）M是G的不相邻边组成的边子集（无环）
  • 饱和点 v是匹配M中某边的端点，则称v为M饱和点
  • 完美匹配 G中每个顶点均为M饱和点，则M为G的完美匹配
    • 最优匹配 在赋权完全偶图 寻找一个具有最大权值的完美匹配
  • 最大匹配 若M是G包含边数最多的匹配，则M为G的最大匹配
• M交错路 M中的边和非M的边交替组成的路
  • M可扩路 起点与终点为M非饱和点的路
    • M是G的最大匹配 当且仅当 G不含M可扩路
    • 中间的点一定都是M饱和点，起始非M边 然后交错 最后非M边
• 5.3 Tutte定理与完美匹配
  • 偶数阶图G 有完美匹配 当且仅当 o(G-S)≤|S| 对所有S属于V成立（任意删去s个顶点，所得图奇分支个数<=删去点数）
    • 奇分支o(G) 拥有奇数个顶点
  • 没有割边的三正则图 一定有完美匹配（每条边都在圈之中，彼得森图）有割边的三正则图 不一定没有完美匹配
  • 什么样的树有完美匹配？o(T‒v)=1
    • 因为T有完美匹配，由Tutte定理知o(T‒v)≤1显然，T是偶数阶的图，于是o(T‒v)≥1。因此，o(T‒v)=1。
• 5.4 因子分解
  • 因子：至少含G一条边的生成子图（非空生成子图）K因子-K正则的因子
    • 一因子的边集构成一个完美匹配（因为因子是边导出生成子图，要包含所有顶点，所以存在1因子必然有完美匹配）二因子的连通分支为一个圈（多个独立圈，H圈一定是二因子，但二因子不一定是H圈，连通的二因子是H圈）
  • 因子分解：将G分解成若干边不重的因子之并
    • K因子分解：每个因子均为K因子的分解
      • 一定是正则图每个顶点度数为k倍数
        • d正则图，k因子分解分解成d/k个因子
      • 1因子分解（阶数为偶且正则）一定偶数阶正则图（必要条件，反之不一定成立）一个一因子是图一个完美匹配的边导出子图能一因子分解，代表图能表示成多个 边不重 完美匹配边导出子图的并
        • 完全图K2n 是2n-1正则图！！所以有2n-1个完美匹配
          • 转圈法匹配其他标点转圈2n不动平行标点相连
        • n正则偶图Kn,n  n个一因子(n个完美匹配)
          • 固定X部分顶点，另一部分循环找匹配
        • 有割边的3正则图 不可1因子分解，可能有1因子（可能有完美匹配）无割边的3正则图 不一定可1因子分解，但一定有1因子（一定有完美匹配）
          • 具有H圈的3正则图 可1因子化（H圈一定可以分解成两个一因子）因为是3正则图，所以阶数一定偶数（握手定理得两个不能同时为奇）
          • 三正则图去掉一个一因子后（去掉不含割边的那种）得到2因子，顶点度数都为2，那么每条边都在圈中，与含割边不符
        • 偶阶正则图 k≥n/2（向下取整）时可以一因子分解
      • 二因子分解（度数为偶）每个2因子都是边不重的圈的并连通的2因子是H圈可2因子分解的图所有度数都为偶（不一定正则）连通图可二因子分解 当且仅当 偶数度正则图（加上了连通所以一定要正则）
        • 完全图K2n+1是n个H圈的并—可以分解成n个连通的2因子偶阶完全图可一因子化不可二因子化奇阶完全图可二因子化不可一因子化（偶阶可以分出一个一因子再二因子分解）
        • 连通图的2因子一定连通吗？不一定
  • 森林分解：将G分解成无圈图（森林因子）的并
    • 荫度σ(G)：无环图分解为边不重生成森林的最少数目（生成森林：含所有点，不一定连通，可能有孤立点）
      • 无圈图荫度=1 生成树
      • 有圈图荫度>=2 需要把圈拆掉σ(G)>=（m/n-1）向上取整因为分成很多树
      • G荫度由子图荫度决定ms是G的最大的s阶子图所包含的边数
        • 完全图Kn s=n时子图最大完全二部图Kr,p s=n=r+p时子图最大
  • 考试1.计算个数 2.证明题
    • 证明：若n为偶数且δ(G)≥n/2+1，则n阶图G有3-因子。
      • 3因子-一个1因子一个2因子因δ(G)≥n/2 Dirac定理得：n阶图G有H圈C又因n为偶数，所以C为偶圈于是由C可得到G的两个1因子，设其中一个为F1考虑G1=G-F1，则δ(G1)≥n/2。于是G1中有H圈C1作H=C1∪F1。显然H是G的一个3-因子
        • 证：若G为n阶简单图(n为偶数)且δ(G)≥n/2+3，则G中存在5-因子先分离出1因子，再2因子+2因子，最后合并
        • 证：当n≥1时，完全图K4n+1可以4-因子分解
• 5.5 匈牙利算法与最优匹配
  • 匈牙利算法：1.任取匹配M                    2.找M可扩路，若不存在，则M为最大匹配                     若存在，则将可扩路M与非M的边互换，得到比M多一条边的匹配M'（从G的每个非饱和点出发找M可扩路，直到不存在M可扩路）
    • （找M可扩路方法）用扎根于M 非饱和点u的M交错树的生长来求M可扩路
      • 以不饱和点开始，后面其他顶点都是两两配对的M饱和点，直到找到另一个不饱和点，若没找到就是最大匹配，若找到了就将路上的边交换得到更大的匹配
  • 最优匹配(完全偶图找权最大完美匹配)
    • 可行顶点标号L：任何边两端点的标号和都大于等于边权
      • 例 将二部图Y部分点标号全部设为0X只需要连的所有边权max值为标号就可
    • 相等子图Gl：以端点标号和=边权的边为边集的生成子图
      • 从上面的例子得到，取出边权=端点标号和的边即可
    • 相等子图的完美匹配=G的最优匹配
      • 证：设M*是Gl的完美匹配则M*中的边权和=所有顶点标号和对G任意完美匹配M，一定有M边权和<=M标号和=M*边权和所以M*是G最优匹配
        • KM算法（找最优匹配）1.任意可行定点标号L，决定Gl2.在Gl中任取一匹配M，用匈牙利算法找到一个完美匹配则该匹配就是最优匹配若在Gl中找不到完美匹配，就修改定点标号，(S\T是二部图X\Y在树上的点)
• 5.2 偶图的匹配与覆盖
  • 偶图匹配
    • 邻集
      • G为(X,Y)偶图 G含有饱和X每个顶点的匹配 当且仅当 |N(S)| ≥ |S| 对所有s属于X成立（N(S)此处就是Y）
    • 特殊图
      • 非平凡树 至多存在 一个完美匹配
      • K正则偶图 有完美匹配
      • 求Kn,n不同完美匹配的个数 n*n-1*...=n!
      • n方体 有完美匹配（n方体是有2^n个顶点的n正则二部图）
      • 求K2n中不同完美匹配的个数 2n-1*2n-3*...=(2n-1)!!
  • 点覆盖
    • 选中V(G)的一个点子集K，使G每条边至少一个端点在K中（通过选一些点，来将G所有边都选中）
    • 最小覆盖 包含点数最少的
    • 匹配<=覆盖取‘=’当且仅当 最大匹配和最小覆盖
      • 偶图中，最大匹配 边数=最小覆盖 点数（用于互相转化，很多题不用这个做不出来）

KM算法（找最优匹配）1.任意可行定点标号L，决定Gl2.在Gl中任取一匹配M，用匈牙利算法找到一个完美匹配则该匹配就是最优匹配若在Gl中找不到完美匹配，就修改定点标号，(S\T是二部图X\Y在树上的点)

以不饱和点开始，后面其他顶点都是两两配对的M饱和点，直到找到另一个不饱和点，若没找到就是最大匹配，若找到了就将路上的边交换得到更大的匹配

例 将二部图Y部分点标号全部设为0X只需要连的所有边权max值为标号就可

相等子图Gl：以端点标号和=边权的边为边集的生成子图

从上面的例子得到，取出边权=端点标号和的边即可

G荫度由子图荫度决定ms是G的最大的s阶子图所包含的边数

可行顶点标号L：任何边两端点的标号和都大于等于边权

完全图Kn s=n时子图最大完全二部图Kr,p s=n=r+p时子图最大