匹配数：端点两两不同的边子集最大值
定义二：任意一条边都与其对应点子集有重合
性质1：最大匹配=无可增广轨道，必要性易证
G中关于M的可增广轨道定义：
v0e1v1e2v2...e(2k+1)v(2k+1),v0&v(2k+1)\notinM(未被M许配),e1e(2k+1)\notinM,e2e(2k)\inM
假设还有更大匹配M‘，M异或M'中deg(v)\in{1,2},只有4中情形，
又要符合匹配数之差=1，必有可增广轨道，paradox~
如何取得可交错轨道？
- M亦或M'
- 二分图连通域
性质2：二分图存在完备匹配\iff|N(S)|>|S|
设u未被最大匹配匹配，Z=与u有交错轨道的点集，
S=X∩Z,T=Y∩Z,(为取连通分支), 设u与y1相邻，则y1与x1匹配，
(1)N({u,x1})>1,还有y2与u或x1相邻，递推，必得可增广轨道
(2)因为连通二分图无增广轨道，必有|S|=|T|+1,矛盾
覆盖数：删除后点集无边的顶点集最大值
定义二：每条边都有一个端点属于集合C的min|C|
性质1：M为覆盖，C为匹配，|M|\leq|C|
性质2：若|M|=|C|,C为最小覆盖，M为最大匹配
性质3：二分图的|M|=|C|
证明：若将所有顶点相配，√
条件：最大匹配，无增广轨道
目标：|覆盖集|=匹配数，若反证，假设|最小覆盖集|>匹配数；2. 找到一个|覆盖集|=匹配数
有顶点(在两端)剩余，在X中未将U匹配，由于为二分图，令Z为与U有交错轨道的顶点集，
S=X∩Z，T=Y∩Z，其中S-U\subseteqM,T-U\subseteq M,
(X-S)UT为覆盖集，否则N(S)>T,矛盾
U是未匹配集，因为M是最大匹配集/(无可增广轨道uie1ti)在Y中每一邻点都是匹配边，否则可获得更大的匹配集，与U相连的都是匹配边端点T'，T‘在M∩Y中的点和T’构成T，所以T中的顶点全被相配
|M|=|T|+|X-S|,Y中顶点在T中的匹配为|T|,不在T中的被X-S相配，为|X-S|,
如果X-S中与T相配，X-S与U相连
性质4：普通G有完备匹配\iffo(G-S)\leq|S|\rightarrowpeterson定理：无桥三次正则图有完备匹配
反证法可证\existsG'，G'无完备匹配；\foralle，G'+e有完备匹配，
设U={v|v\inG',deg(v)=|G'|-1},G-U的奇片为G1,G2,...,Gi为完全图，
否则Gi非完全图，反证法易证存在x,y,z\inGi,xy,yz\inGi,xz\notinGi,
又\becausedeg(y)<n-1,\therefore\existsyw\notinGi.设G'=Gx+xz,Gy=G'+yw的两个最大匹配分别为M1,M2，
考虑Gx异或Gy,想得到更大的匹配必然要处理不同的边，相同的边保留较为简单
每个点分别连接Gx，Gy中一边，每个连通分支Hi均为偶圈，
- xz,yw分别在圈C1,C2，M2在C1中匹配+M1在C2中匹配=G'中完备匹配，矛盾
- xz,yw在同一个圈内，