匹配：

匹配M：M是E的一個，不包含環的子集，它的任意兩條邊在G中均不相鄰。

M飽和的點v：匹配M的某條邊，與頂點v關聯。

M非飽和的點v：M中無邊與頂點v關聯。

完美匹配M：若G中的每個頂點，都是M飽和的點。

最大匹配M：在G中，找不到其它匹配的邊數，大于M了。

ps：每個完美匹配，都是最大匹配。

?

M交錯路：指圖G的邊，在E\M和M中交替出現，的路。

M可擴路：起點和終點，都是，非飽和的，M交錯路。

ps：這個證明可等價于，M不是最大匹配，當且僅當G含有M可擴路。

充分性證明，M’為M可擴路中，除去M中的邊，所組成的邊集。在可擴路中，選取的M’內的邊集互不相交，因此可算是個匹配。M’有m+1條邊，M有m條邊。

反之是，必要性證明，M和M’的對稱差，意味著去除，M和M’之間公共邊。因為M和M’都是匹配，里面的任意兩條邊均不鄰接，因此H中的一個點，不可能同時關聯M或M’中的兩條邊。M’的邊多于M的邊，H必定存在一個分支，M’的邊多于M的邊，在這個分支中，也必定存在，以M’中的邊開始和結束的路P。

?

偶圖的匹配與覆蓋：

鄰集N(S)：與S的頂點，相鄰的所有頂點的集合。

ps：必要性證明，S是X的子集，因此M也飽和S中的每一個頂點，則S中的每個頂點，也匹配于Y中的一個頂點，所以N(S)在原圖G中，至少有S。

反之是，充分性證明，為包含所有，含有u點的交錯路的頂點集。u肯定是Z中唯一的非飽和點，不然就有可擴路了，不然，在一條交錯路上，出現了兩個非飽和點，以這兩點為端點，截取出來的路，就為可擴路了。

因為T是由Y和連接于u的交錯路上的點的交集，所以T中的點所有都是的飽和點。

如果沒有交錯路的限制，S會和Y中多個點相鄰，因此有，。因為Z選取的是，所有連接于u的交錯路上的點，所以T必定包含了所有N(S)上的點（如S的某個點到u的某條交錯路中，加多一條到N(S)的邊，又形成一條交錯路）。

因N(S)中每個頂點v，均有一個交錯路連接于u，所以v∈Z，但是Z包含了所有T中的點，從而v∈T，這表明，所以有。

?

ps：頂點數X或Y，乘上X或Y上每個點的度數k，則等于邊數E(G)。N(S)的點所關聯的邊數至少為S。

?

覆蓋：在頂點集中取個子集K，使得圖G的每條邊，至少有一個端點在K中。

最小覆蓋K：圖G不能找到一個覆蓋K’，使得。

?

任何匹配M和任何覆蓋K，均由。若G是偶圖，則有

ps：K至少包含每條邊的一個端點。

?

ps：U中的每一個點v，出現在的每一個交錯路上，均只有v它一個非飽和點。一個端點在S中，另一個端點也必定在N(S)中，也就是T中，因此和另一個端點在Y\T中，矛盾。由于X\S的點不會和T中的點相連，所以最大匹配里的邊，由T與S中的一些飽和點連成的邊和包含X\S中的點的匹配邊，組成，因此有最大匹配數等于最小覆蓋數。

?

Tutte定理與完美匹配：

分支根據，它有奇數個或偶數個頂點，而分成為，奇分支或偶分支。

o(G)：G的奇分支的個數。

?

以下推論是充分條件。例如，有割邊的3正則圖，不一定就沒有，完美匹配。

ps：Gi是奇分支，所以是奇數，因此，奇數乘以奇數，還是奇數，是奇數。又因為奇數減去偶數是奇數，是奇數，它表示原有Gi每個點所關聯的邊數的2倍，減去Gi先有的邊數的兩倍，結果為，Gi被S切斷的度數，也即邊數。有k個mi，且每個mi至少為3，所以有，3k≤。因為S不僅要與Gi這些點連邊，而且S內部的點也要連邊，因此有：≤。

?

因子分解：

圖G的一個因子：G的一個生成子圖，但至少有一條邊。

G的一個因子分解：因子的邊的并，且這些因子的邊并無交集，即交集為空集。

n-因子：一個n度正則的因子。

n-因子分解：G是幾個n-因子的和，且它們的并，就為n-因子分解。

而上述的那個G本身，稱為n-可因子化。

?

若G有一個1-因子，即是完美匹配（1-因子是生成子圖，且每個點的度都為1），且G為偶階圖（G的度數之和為n=2m）。

所以不能有1-因子，有1-因子。

ps：一個1-因子即為一個完美匹配，即為多個這樣的完美匹配構成。因為是完美匹配，中的每個點都要被匹配到，且一個點要有2n-1條邊，所以要找出的完美匹配的個數，即1-因子的個數，為2n-1個。可按下述例1的方法來劃分。

?

?

例子：

ps：去掉一個完美匹配，則所有頂點的度會減1。在完美匹配中，若割邊所關聯的頂點選擇了其它邊，這就不能選擇割邊了，所以當然會有不含割邊的1-因子，因此3-正則圖，一定有一個不含割邊的1-因子。

?

2-因子分解：

若一個圖是2-可因子化，則每個因子，一定是，不相交圈(圈的邊無交集)的一個并。（因為這個圖的每個2-因子，頂點的度都為2）。

不是2-可因子化的。

若一個2-因子是連通的，則它是一個H圈。（因為這個生成圖是連通的，就只有一個圈，也就是H圈。若不是連通的，可能有多個圈）

ps：構造出的n條路，其端點最后連接，形成H圈。

?

2度正則圖是一個2-因子。

偶圈能表示為，兩個1-因子的和。

例子：

ps：其中的2-因子是一些偶圈，偶圈1-可因子化的，所以這個圖也是1-可因子化的。

Peterson圖就是個例子，由5邊形和5角星形一起構成了，一個2-因子(非連通的生成子圖)，和一個聯接5邊形和5角星的完美匹配。

ps：2-可因子化，意味著，這個連通圖是由多個不相交的圈組成。

?

最優匹配與匈牙利算法：

為解決人員分派問題的一個算法。

扎根于u的M交錯樹：u是非飽和點，樹H種的任一點v，有唯一的(u,v)路，是一條M交錯路。

匈牙利算法：

ps：表明找不到一個匹配能飽和所有X的頂點，也就是不存在完美匹配。，用路P上的非匹配邊，置換掉，路P上的匹配M中的邊。

例子：

?

最優匹配：

定義：在賦權圖中，尋找一個具有最大權的完美匹配。

對來說，有個不同完美匹配。

可行頂點標號：存在一個實值函數l，使得偶圖中，

不管邊的權是什么，總存在一個可行頂點標號：

相等子圖：具有邊集的，G的生成子圖。

ps：因為某一對頂點標號之和，總是≥該邊的權值，因此所有頂點標號的總和是，圖的權值總和的一個上界。是上的完美匹配，因此上的任一兩個頂點標號之和都=邊上的權值。但在M上取得邊，可能會小于，關聯的兩頂點標號之和。

?

最優匹配算法：

步驟：

例子：

修改頂點標號方法：

ps：重新計算的α值，涉及到在S集合中，不在T集合中的元素。例如鎖定，1、3、4行和1、4、5列。

總結

以上是生活随笔為你收集整理的《图论及其应用》学习笔记（匹配和因子分解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。