二分圖是圖論當中很重要的一個板塊，由二分圖的匹配與帶權匹配可以推廣出一般圖的匹配與帶權匹配。本篇主要會講到二分圖的定義、性質、判定。
一、定義
二分圖，又稱二部圖，英文名叫 Bipartite graph，是圖論中的一種特殊模型。
二分圖是什么？節(jié)點由兩個集合組成，且兩個集合內部沒有邊的圖。換言之，存在一種方案，將節(jié)點劃分成滿足以上性質的兩個集合。
二、性質
那么二分圖有什么性質呢？
當且僅當無向圖G的每一個環(huán)(即回路、圈，英文為circle)的結數(shù)均是偶數(shù)時，G才是一個二分圖。如果無環(huán)，相當于每個環(huán)的結點數(shù)為0，故也視為二分圖，即為二分圖不存在長度為奇數(shù)的環(huán)，因為每一條邊都是從一個集合走到另一個集合，只有走偶數(shù)次才可能回到同一個集合。
如果兩個集合中的點分別染成黑色和白色，可以發(fā)現(xiàn)二分圖中的每一條邊都一定是連接一個黑色點和一個白色點。
三、判定
如何判定一個圖是不是二分圖呢？
換言之，我們需要知道是否可以將圖中的頂點分成兩個滿足條件的集合。
顯然，直接枚舉答案集合的話實在是太慢了，我們需要更高效的方法。
考慮上文提到的性質，我們可以使用 DFS（圖論） 或者 BFS 來遍歷這張圖。如果發(fā)現(xiàn)了奇環(huán)，那么就不是二分圖，否則是。
四、應用
二分圖最大匹配
二分圖最大權匹配
一般圖最大匹配
一般圖最大權匹配
C語言網提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習題和答疑，點擊了解：
一點編程也不會寫的：零基礎C語言學練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個編程真題的編程百練課程
信息學奧賽或C++選手的 必學C++課程
藍橋杯ACM、信息學奧賽的必學課程：算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導課程