二分圖：是這樣一個(gè)圖，它的頂點(diǎn)可以分類兩個(gè)集合X和Y，所有的邊關(guān)聯(lián)在兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合Ｘ，另一個(gè)屬于集合Ｙ。
最大匹配： 圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。
完美匹配： 如果所有點(diǎn)都在匹配邊上，稱這個(gè)最大匹配是完美匹配。
最小覆蓋： 最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。可以證明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)
最小路徑覆蓋：用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無環(huán)圖Ｇ的所有結(jié)點(diǎn)。解決此類問題可以建立一個(gè)二分圖模型。把所有頂點(diǎn)i拆成兩個(gè)：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m。
最大獨(dú)立集問題：在Ｎ個(gè)點(diǎn)的圖G中選出m個(gè)點(diǎn)，使這m個(gè)點(diǎn)兩兩之間沒有邊．求m最大值．如果圖Ｇ滿足二分圖條件，則可以用二分圖匹配來做．最大獨(dú)立集點(diǎn)數(shù) = N - 最大匹配數(shù)。