主題
Search

二分圖


BipartiteGraph

二分圖,也稱為雙圖,是一組圖頂點的集合,這些頂點被分解成兩個不相交的集合,使得同一集合內的任意兩個圖頂點都不相鄰。二分圖是 k-部圖 的一個特例,其中 k=2。上面的圖示展示了一些二分圖,每個圖中的頂點都根據它們所屬的兩個不相交的集合進行了著色。

二分圖等價於可二著色圖。所有無環圖都是二分圖。一個有環圖是二分圖當且僅當其所有環的長度均為偶數 (Skiena 1990, p. 213)。

二分圖族包括

1. 無環圖(即,森林),

2. 書圖 S_(n+1) square P_2,

3. 交叉稜柱圖

4. 冠圖 K_2 square K_n^_,

5. 環圖 C_(2k),

6. 齒輪圖

7. 網格圖

8. Haar 圖

9. Hadamard 圖

10. 超立方體圖 Q_n,

11. 騎士圖

12. 梯形圖

13. 梯級圖 nP_2(它們是森林)。

14. 路徑圖 P_n(它們是樹),

15. 蒙古包圖

16. 謝爾賓斯基地毯圖

17. 堆疊書圖

18. 星圖 S_n(它們是樹)。

柯尼希線著色定理指出,每個二分圖都是 1 類圖柯尼希-艾格瓦里定理指出,對於二分圖,匹配數(即最大獨立邊集的大小)等於頂點覆蓋數(即最小最小頂點覆蓋的大小)。

可以使用 Wolfram 語言測試一個圖是否為二分圖,方法是使用BipartiteGraphQ[g],並且可以使用以下方法找到二分圖的其中一個分量的索引FindIndependentVertexSet[g][[1]]。

BipartiteGraphs

節點數為 n=1, 2, ... 的二分圖的數量是 1, 2, 3, 7, 13, 35, 88, 303, ... (OEIS A033995)。

BipartiteConnectedGraphs

節點數為 n=1, 2 ... 的連通二分圖的數量是 1, 1, 1, 3, 5, 17, 44, 182, ... (OEIS A005142)。


另請參閱

雙色圖, 雙三次圖, 二分重圖, 二分克內澤圖, 完全二分圖, 圖二著色, k-部圖, 柯尼希-艾格瓦里定理, 柯尼希線著色定理, 塔特猜想

使用 探索

參考文獻

Chartrand, G. 圖論導引。紐約: Dover, p. 116, 1985。Read, R. C. 和 Wilson, R. J. 圖譜。英國牛津: Oxford University Press, 1998。Saaty, T. L. 和 Kainen, P. C. 四色問題:進攻與征服。紐約: Dover, p. 12, 1986。Skiena, S. "二分圖著色。" §5.5.2 in 用 Mathematica 實現離散數學:組合數學和圖論。Reading, MA: Addison-Wesley, p. 213, 1990。Sloane, N. J. A. 序列 A033995 in "線上整數序列百科全書"。Steinbach, P. 簡單圖的野外指南。Albuquerque, NM: Design Lab, 1990。

在 上被引用

二分圖

引用為

埃裡克·韋斯坦因 "二分圖。" 來自 Web 資源。 https://mathworld.tw/BipartiteGraph.html

主題分類