2.6　獨立集與匹配

設X是V的一個子集，若X中任意兩個頂點在G中均不相鄰，則稱X為G的獨立集。若X是G的獨立集，但任意增加一個頂點后就破壞它的獨立性，則稱這個獨立集X為極大獨立集。G的一個獨立集X稱為G的最大獨立集，如果G不包含滿足|Y|>|X|的獨立集。G的最大獨立集的基數稱為G的獨立數，記為α（G）。圖2-17給出了彼得森圖的極大和最大獨立集。

圖2-17　彼得森圖的極大和最大獨立集

匹配問題是運籌學的重要問題之一，也是圖論的重要內容。它在所謂“人員分配”和“最優分配”等實際問題中有著重要的作用。

設M是E的一個子集，它的元素是G中的邊，并且這些邊中的任意兩個均不相鄰，則稱M為G的匹配。若頂點v與匹配M中的某條邊關聯，則稱v是M飽和的，否則稱v是M非飽和的。若G的每個頂點均為M飽和的，則稱M為G的完美匹配。若匹配M不可能是圖G的任何一個匹配的真子圖，則稱M為G的極大匹配。若G沒有另外的匹配M'，使得>，則M稱為G的最大匹配。顯然每個完美匹配都是最大匹配。圖2-18給出五棱柱的一個極大匹配和一個完美匹配。

圖2-18　五棱柱的極大匹配和完美匹配

定義2-7　設M是G的一個匹配，G的M交錯路是指其邊在M和E（G）\M中交替出現的路。如果G的一條M交錯路的起點和終點都是M非飽和的，則稱其為一條M可擴路或M增廣路。

定理2-4　（Berge，1957）圖G的匹配M是最大匹配的充分必要條件是G中不存在M可擴路。

定理2-5　（Tutte，1947）圖G有完美匹配的充分必要條件是對?S?V（G），O（G\S）≤。

關于二部圖的匹配，有下面定理。

定理2-6　（Hall，1935）設G是具有二劃分（X，Y）的二部圖，則G有飽和X的匹配當且僅當對?S?X，≥，其中N（S）表示S中所有點的鄰點組成的集合。