![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/langzh-hk-640px-Simple-bipartite-graph.svg.png&w=640&q=50)
二分圖
維基百科,自由的 encyclopedia
在圖論中,二分圖(英語:Bipartite graph)是一類特殊的圖,又稱為二部圖、偶圖、雙分圖。二分圖的頂點可以分成兩個互斥的獨立集 U 和 V 的圖,使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的,二分圖可以被定義成圖中所有的環都有偶數個頂點[1][2]。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/320px-Simple-bipartite-graph.svg.png)
可以將 和
當做一個着色:
中所有頂點為藍色,
中所有頂點着綠色,每條邊的兩個端點的顏色不同,符合圖着色問題的要求[3][4]。相反的,非二分圖無法被二着色,例如
(3 個頂點的完全圖),將其中一個頂點着藍色並且另外一個着綠色後,第三個頂點與上述具有兩個顏色的頂點相連,無法再對它着藍色或綠色。
二分圖的一種描述方式為:,包含了獨立集
和
,以及邊
的資訊。假如
不是連通圖,可能有多種將所有頂點分成
和
的方式[5];在特定的應用場合中,將頂點的兩部分
、
寫出來是有必要的。如果
,則
稱為平衡二分圖[3]。如果二分圖
以及
的頂點分別有相同的度數,則
被稱為是雙正則的(英語:Biregular graph)。
給定一個二分圖 ,在
的一個子圖
中,
的邊集中的任意兩條邊都沒有共同的端點,則稱
是一個匹配。