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