二分图 在圖論中二部圖英語Bipartite graph是一類特殊的圖又稱為二部图偶图雙分圖二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖使得所有邊都是連結一個 U 中的點和一個 V 中的點頂點集 UV 被稱為是圖的兩個部分等價的二分圖可以被定義成圖中所有的環都有偶數個頂點 可以将 U displaystyle U 和 V displaystyle V 当做一個着色 U displaystyle U 中所有頂點为蓝色 V displaystyle V 中所有頂點着绿色每条边的两个端点的颜色不同符合图着色问题的要求相反的非二分圖無法被二著色例如 K  displaystyle K  個頂點的完全圖將其中一个顶点着蓝色并且另外一个着绿色后第三个顶点与上述具有两个颜色的顶点相连无法再对它着蓝色或绿色 二分图的一种描述方式为 G   U  V  E  displaystyle GUVE 包含了独立集 U displaystyle U 和 V displaystyle V 以及边 E displaystyle E 的資訊假如 G displaystyle G 不是连通图可能有多種將所有頂點分成 U displaystyle U 和 V displaystyle V 的方式在特定的應用場合中將頂點的兩部分 U displaystyle U  V displaystyle V 寫出來是有必要的如果  U    V  displaystyle UV 則 G displaystyle G 称为平衡二分图如果二分图 U displaystyle U 以及 V displaystyle V 的顶点分別有相同的度數則 G displaystyle G 被稱為是雙正則的英语Biregular graph 给定一个二分图 G displaystyle G 在 G displaystyle G 的一个子图 M displaystyle M 中 M displaystyle M 的边集中的任意两条边都沒有共同的端点则称 M displaystyle M 是一个匹配