什麼叫二部圖

二部圖又叫二分圖，是圖論中的一種特殊模型，是指頂點集可分割為兩個互不相交的子集，並且圖中每條邊依附的兩個頂點都分屬於這兩個互不相交的子集，兩個子集內的頂點不相鄰。

判斷二部圖的常見方法是染色法：對任意一未染色的頂點染色，判斷其相鄰的頂點中，若未染色則將其染上和相鄰頂點不同的顏色， 若已經染色且顏色和相鄰頂點的顏色相同，則説明不是二部圖，若顏色不同則繼續判斷，直到全部染上色。