二分图

二分圖的範例

在圖論中，二部圖（英語：Bipartite graph）是一類特殊的圖，又稱為二部图、偶图、雙分圖。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖，使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的，二分圖可以被定義成圖中所有的環都有偶數個頂點^[1][2]。

可以将 ${\displaystyle U}$ 和 ${\displaystyle V}$ 当做一個着色：${\displaystyle U}$ 中所有頂點为蓝色，${\displaystyle V}$ 中所有頂點着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求^[3][4]。相反的，非二分圖無法被二著色，例如 ${\displaystyle K_{3}}$(3 個頂點的完全圖)，將其中一个顶点着蓝色并且另外一个着绿色后，第三个顶点与上述具有两个颜色的顶点相连，无法再对它着蓝色或绿色。

二分图的一种描述方式为：${\displaystyle G=(U,V,E)}$，包含了独立集 ${\displaystyle U}$ 和 ${\displaystyle V}$，以及边 ${\displaystyle E}$ 的資訊。假如${\displaystyle G}$不是连通图，可能有多種將所有頂點分成 ${\displaystyle U}$ 和 ${\displaystyle V}$的方式^[5]；在特定的應用場合中，將頂點的兩部分${\displaystyle U}$、${\displaystyle V}$寫出來是有必要的。如果${\displaystyle |U|=|V|}$，則 ${\displaystyle G}$ 称为平衡二分图^[3]。如果二分图 ${\displaystyle U}$ 以及 ${\displaystyle V}$的顶点分別有相同的度數，則 ${\displaystyle G}$ 被稱為是雙正則的（英语：Biregular graph）。

给定一个二分图 ${\displaystyle G}$，在 ${\displaystyle G}$ 的一个子图 ${\displaystyle M}$ 中，${\displaystyle M}$ 的边集中的任意两条边都沒有共同的端点，则称 ${\displaystyle M}$ 是一个匹配。

例子

二分圖經常出用來研究兩種不同類型的物件之間的關係。例如，如果要討論足球球員和球隊的關係，可以畫一個二分圖，頂點的兩部分分別是所有球員和所有球隊，如果球員受僱於球隊，則在二者之間連邊。這種二分圖模型叫做附屬網絡（英语：affiliate network），經常用於社會網絡分析（英语：social network analysis）^[6]。

另一個例子出現在鐵路規畫問題：給定許多班火車及許多車站，每輛火車中途停靠的站不盡相同，問最少個數的車站集合使得每輛火車都停靠至少一個集合中的車站。以圖論的觀點來看，將火車和車站視為頂點，火車有停靠車站則連邊，問題轉化成是二分圖的點覆蓋問題。

第三個例子出現在古幣學，古代的硬幣有正面及反面之分，不同時期和地區的政府會使用不同的正反面組合，因此，將所有可能的組合畫成圖就是一個二分圖的結構^[7]。

其他一般性的例子諸如：

• 所有的樹都是二分圖^[4]。
• 有偶數頂點個數的環 (圖論)是二分圖^[4]。
• 所有的平面圖滿足各個面的邊界有偶數個邊是二分圖^[8]，因此格子點圖（英语：lattice graph）和四邊形圖（英语：squaregraph）都是二分圖^[9]。
• 一個完全二分圖 K_m,n 是一個二分圖，滿足兩個頂點集 U、V 分別有 m、n 個頂點，並且任取一個 U 中的點，所有 U 中的頂點都連邊到所有 V 中的頂點^[10]。
• 皇冠圖（英语：crown graph） 是將完全二分圖 K_n,n 扣掉一個完美匹配的所有邊所得到的圖，因此也是個二分圖^[11]。
• 超方形圖（英语：hypercube graph）、部分超方形圖（英语：partial cube）、和中間圖（英语：median cube）都是二分圖，而且它們的頂點可以被看做是位元向量（英语：bit vector）（一串由0和1組成的字串），使得兩個頂點連邊若且唯若它們只有一個位元是相異的，而它們的二分性的驗證可以藉由考慮兩個獨立集是分別蒐集所有擁有奇數和偶數個1的位元向量。此外，所有的樹和四邊形圖都是中間圖，而所有的中間圖都是部分超方形圖^[12]。

特性

等價條件

• 一個圖是二分圖若且唯若它不包含奇環作為子圖^[13]。
• 一個圖是二分圖若且唯若它的著色數是 2^[3]。
• 一個圖是二分圖若且唯若它的谱是正負對稱的^[14]。

柯尼希定理

主条目：柯尼希定理 (图论)

柯尼希定理於1931年，由匈牙利數學家德內斯·柯尼希提出^[15][16]：

一個圖是二分圖若且唯若它的最小頂點覆蓋的頂點數等於最大匹配的邊數。

該定理有一個等價形式，一個圖是二分圖若且唯若它的最大獨立集的頂點數與最大匹配的邊數之和，等於總頂點個數。再配合一個性質，一個沒有孤立頂點的圖會滿足最小邊覆蓋的邊數加上最大匹配的邊數等於總頂點個數^[17]，我們有對任何沒有孤立頂點的二分圖，最小邊覆蓋的邊數等於最大獨立集的頂點數，以及最小邊覆蓋的邊數加上最小頂點覆蓋的頂點數等於總頂點數。

完美圖

所有的二分圖和二分圖的線圖，以及它們的補圖都是完美圖。很明顯的，二分圖是完美圖，因為他的著色數和最大點團數皆為 2，但另一方面，二分圖的補圖的完美性是相對難以證明的，該性質等價於前面小節的倒數第二個敘述。類似的，二分圖的線圖的補圖的完美性等價於柯尼希定理的敘述，這也是會如此定義完美圖的動機之一^[18]。而最後剩下的，是二分圖的線圖的完美性，而這個等價於柯尼希於早些年證明出的定理：二分圖的邊著色數等於最大度數。

強完美圖定理給出完美圖的等價條件：一個圖是完美圖若且唯若所有奇環和奇環的補圖都不是它的導出子圖。這個刻畫可與二分圖沒有奇環作為子圖類比，實際上，在強完美圖定理的證明中，二分圖、二分圖的線圖，以及它們的補圖佔了 5 個基本類型中的 4 個^[19]。

度數

一個頂點 v 的度數定義為以它為端點的邊數，記做 ${\displaystyle \deg(v)}$，很明顯的，對於二分圖 ${\displaystyle G=(U,V,E)}$，有以下的度數和公式

${\displaystyle \sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|}$

一個二分圖的度數序列是兩個序列，分別列出 U 和 V 中各頂點的個數。例如完全二分圖 K_3,5 的度數序列是 (3,3,3,3,3) 和 (5,5,5)。同構的二分圖會有相同的度數序列，但一般而言，擁有相同度數序列的圖卻不一定是同構的。可二分圖化問題（英语：partial cube）是給定兩個正整數序列，要尋找出一個二分圖使得它的度數序列是那兩個正整數序列。本問題中的序列中的 0 可以被忽略，因為那只是在為二分圖增加孤立頂點而已。

與超圖及有向圖的關係

一個兩部分分別有 m 和 n 個頂點二分圖的雙相鄰矩陣是一個 ${\displaystyle m\times n}$(0,1) 矩陣，滿足如果兩個頂點相鄰，矩陣中的該行該列對應到的元素是 1，反之如果兩點不相鄰則對應到 0^[20]。雙相鄰矩陣可以用來描述二分圖、超圖和有向圖的等價關係。

超圖的定義如同簡單圖，由頂點和邊組成，但是一個邊可以有超過兩個段點，因為一個邊被重新定義做頂點集合的一個子集合。可以用二分圖 (U,V,E) 來描述超圖，其中 U 是超圖的頂點集合，V 是超圖的邊集合，U、V 中的兩元素 u, v 有連邊若且唯若在超圖中，u 是 v 的一個段點。在這個對應之下，二分圖的雙相鄰矩陣等於它所對應到的超圖的關聯矩陣（英语：incidence matrix #Graph theory）。特別的多重圖 (可能會有不同邊有相同的兩個端點) 可以被視為是超圖的特例，只是每個點都恰有兩個邊而已，根據上述，多重圖對應到的二分圖滿足 V 中的頂點度數皆為 2^[21]。

類似的，所有有向圖 (允許兩端點相同的自環) 可以一對一對應到所有平衡二分圖，方法是將有向圖的 n 個頂點複製兩份，得到集合 U、V，U 中的頂點 u 有連邊到 V 中的頂點 v 若且為唯若在原本有向圖中，有一條邊從 u 出發指向 v。此時，有向圖的相鄰矩陣可以是任意 ${\displaystyle n\times n}$ 階 (0,1) 矩陣，而且會一對一對應到平衡二分圖的雙相鄰矩陣^[22]。

霍尔定理

主条目：霍爾婚配定理

霍尔定理（Hall's Theorem)表明了一个二分图G，X与Y分别是两个独立集。X能被Y匹配当且仅当${\displaystyle |N(S)|\geq |S|}$，其中S是X的任意子集。

霍尔定理给出了一种证明完美匹配是否存在的方式，该定理也常常被用于求解SDR问题（system of distinct representatives，不同代表问题）。

在SDR问题中，你拥有n个不同的集合，你需要为每个集合找到一个独特的代表元素。一个集合集拥有SDR当且仅当任意t个集合的并包含t个不同的元素。

霍尔定理有时也被称作霍尔婚姻定理（Hall's Marriage Theorem），用以解决男女的婚姻匹配问题。

演算法

二分性測試

給定一個圖，使用深度優先搜尋法，可以在線性時間內判斷它是否為二分圖，並輸出一個二著色 (若答案為是)，或是一個奇環 (若答案為否)。方法是先用深度優先搜尋法找出圖的一個深度優先搜尋森林 (各連通部分取一個深度優先搜尋樹)，這是圖的一個生成森林。接著運用樹的搜尋將森林二著色，也就是依序各頂點著和它的父節點相異的顏色。現在檢查原圖中深度優先搜尋森林以外的其他邊，如果所有邊的兩端點都不同顏色，則這也是原圖的一個二著色，並且輸出它；如果有一個邊 e 的兩端點相同顏色，則此兩端點在同一個連通部分，也就是在森林的同一棵樹上，找出在森林中，連接兩端點的路徑 P，因為 P 上的頂點的顏色是交錯出現的，因此 P 有偶數個頂點，加上 e 就形成一個奇環，並且輸出它^[23]。

事實上，在上述的演算法中，深度優先搜尋森林只是作為一個生成森林，讓我們來著色。因此，用不同的方式獲得的別的生成森林仍然可以使演算法可以運作，例如，可以用廣度優先搜尋取出廣度優先搜尋森林^[24]。

如果原圖是線段，或其他二維空間的物件，的交集圖（英语：intersection graph），並且有 n 個頂點，則可以在 ${\displaystyle O(n\log n)}$時間內輸出一個二著色或奇環，縱使它的邊樹可能會高達 ${\displaystyle O(n^{2})}$^[25]。

奇環代表系

主条目：奇環代表系

本圖有一個包含 2 個頂點的奇環代表系，把圖中的藍色頂點刪掉就可以把圖變成二分圖。

奇環代表系問題是一個NP完全問題，問給一個圖 G(V,E) 和一個正整數 k，是否可以刪掉 k 個頂點使得 G 變成一個二分圖^[26]。這個問題是可定變數決定的 (FTP（英语：Parameterized complexity#FTP）)，更精確地說，存在一個演算法所花費時間不超過一個 k 的函數乘上一個 n 的多項式^[27]，其中 n 是G 的頂點數。奇環代表系這個名字是來自二分圖的一個等價特性：不存在奇環作為子圖。因此，要刪掉點使得 G 變成二分圖其實是在破壞所有的奇環，或者說找出所有奇環的代表系。在右圖的中，所有的奇環都包含一個藍色的頂點 (最下面那排的)，因此刪掉那兩個藍色頂點會把圖變成二分圖。

刪邊二分性問題則是問給定一個圖，至少要刪除幾個邊才能讓該圖變成二分圖，這和奇環代表系問題都是重要的圖修改演算法問題，而且也都是可定變數決定的。事實上，刪邊二分性問題可以在 ${\displaystyle O(2^{k}m^{2})}$被解決^[28]，其中 m 是原圖中的邊數。

匹配

主条目：匹配 (圖論)

一个圖的匹配是这个图中一些邊所形成的集合，滿足任意集合中的两条边都没有公共的顶点。許多關於匹配的問題都有可以被多項式時間的演算法解決，例如最大匹配問題 (尋找一個匹配包含最多的邊)，極大加權匹配問題（英语：Maximum weight matching），和穩定婚姻問題^[29]。在大部分的情況，如果已知原圖是二分圖，匹配問題會變得單純很多^[30]，而且許多演算法只能處理二分圖上的情況，例如專門用來計算最大匹配的邊數的霍普克洛夫特－卡普演算法^[31]。

舉個簡單的例子，假設有一些人想要找尋工作，他們形成集合 P，此外還有一些職缺，它們形成集合 J，並不是所有人都適合所有的工作，但一個人只能做一份工作。這個案例可以被建模成一個二分圖${\displaystyle (P,J,E)}$，如果一個人可以做某項工作則將二者連邊^[32]。一個完美匹配是一個工作的指派使得所有人都有工作做而且每個職缺都有人做。霍爾婚配定理給出一個二分圖有完美匹配的刻畫。

杜爾馬基-孟德爾索分解（英语：Dulmage–Mendelsohn decomposition）將圖依據其結構分解成多塊，經常用於找尋圖的最大匹配^[33]。

應用

二分圖廣泛應用於編碼理論中，尤其常應用在收到從通道傳來的訊息之後解碼過程中。常見的例子有坦納圖和因子圖。坦納圖是一個二分圖，其中一個獨立集蒐集所有的一個碼字裡可以放數碼的位置，另一個獨立集則包含一些可以放數碼的位置的組合，其中每個組合代表一個碼字所該符合的限制──那些位置的數碼加起來總和是 0^[34]，而連邊就代表了屬於。因子圖則與低密度奇偶檢查碼及渦輪碼的機率解碼中所用到的貝氏網路密切相關^[35]。

在電腦科學中，佩特里網是一個數學工具用來分析及模擬並行計算，它將系統模擬成一個有向二分圖，其中一部分的頂點被稱為「位置」節點，包含一些資源，另一部分的頂點被稱為「事件」節點，消耗或生產資源，節點和邊之間的關係還有一些限制，這些限制來自系統本身的限制。佩特里網藉由有向二分圖的性質讓系統的行為可以用數學來證明，並且讓系統的模擬容易被執行^[36]。

在射影幾何中，列維圖（英语：Levi graph）是一個二分圖，描述幾何構形（英语：Configuration (geometry)）中點跟邊的關係。頂點的兩部分分別對應到構形的點跟邊，圖中兩頂點之間連邊若且唯若構形中的邊通過點，因為兩條邊頂多交於一點，或者說，兩點決定唯一一條邊，所以列維圖中不存在長度為 4 的環作為子圖，換言之，列維圖的圍長大於等於 6^[37]。

参考资料

1. Diestel, Reinard. Graph Theory, Grad. Texts in Math. Springer. 2005 [2019-04-29]. ISBN 978-3-642-14278-9. （原始内容存档于2011-04-09）. 
2. Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland, Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics 131, Cambridge University Press, 1998, ISBN 9780521593458 .
3. Asratian, Denley & Häggkvist (1998), p. 7.
4. Scheinerman, Edward R., Mathematics: A Discrete Introduction 3rd, Cengage Learning: 363, 2012 [2014-04-11], ISBN 9780840049421, （原始内容存档于2020-11-09） .
5. Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, Discrete Mathematics And Its Applications 53, CRC Press: 223, 2008 [2014-04-11], ISBN 9781584888000, （原始内容存档于2020-11-09） .
6. Wasserman, Stanley; Faust, Katherine, Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences 8, Cambridge University Press: 299–302, 1994 [2019-03-01], ISBN 9780521387071, （原始内容存档于2020-04-14） .
7. Bracey, Robert. On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins. 2012: 65–84 [2019-03-01]. （原始内容存档于2019-01-13）. 
8. Soifer, Alexander, The Mathematical Coloring Book, Springer-Verlag: 136–137, 2008, ISBN 978-0-387-74640-1 . This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of Alfred Kempe containing a false proof of the four color theorem.
9. Bandelt, H.-J.; Chepoi, V.; Eppstein, D., Combinatorics and geometry of finite and infinite squaregraphs, SIAM Journal on Discrete Mathematics, 2010, 24 (4): 1399–1440, arXiv:0905.4537 , doi:10.1137/090760301 .
10. Asratian, Denley & Häggkvist (1998), p. 11.
11. Archdeacon, D.; Debowsky, M.; Dinitz, J.; Gavlas, H., Cycle systems in the complete bipartite graph minus a one-factor, Discrete Mathematics, 2004, 284 (1–3): 37–43, doi:10.1016/j.disc.2003.11.021 .
12. Ovchinnikov, Sergei, Graphs and Cubes, Universitext, Springer, 2011 . See especially Chapter 5, "Partial Cubes", pp. 127–181.
13. Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig. For infinite graphs, this result requires the axiom of choice.
14. Biggs, Norman, Algebraic Graph Theory, Cambridge Mathematical Library 2nd, Cambridge University Press: 53, 1994 [2019-03-01], ISBN 9780521458979, （原始内容存档于2020-11-09） .
15. Kőnig, Dénes. Gráfok és mátrixok. Matematikai és Fizikai Lapok. 1931, 38: 116–119. .
16. Gross, Jonathan L.; Yellen, Jay, Graph Theory and Its Applications, Discrete Mathematics And Its Applications 2nd, CRC Press: 568, 2005 [2019-03-01], ISBN 9781584885054, （原始内容存档于2019-06-09） .
17. Chartrand, Gary; Zhang, Ping, A First Course in Graph Theory, Courier Dover Publications: 189–190, 2012 [2019-03-01], ISBN 9780486483689, （原始内容存档于2019-06-11） .
18. Béla Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer: 165, 1998 [2019-03-01], ISBN 9780387984889, （原始内容存档于2019-06-10） .
19. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229 [2019-03-01], CiteSeerX 10.1.1.111.7265 , arXiv:math/0212070 , doi:10.4007/annals.2006.164.51, （原始内容存档于2010-06-18） .
20. Asratian, Denley & Häggkvist (1998), p. 17.
21. A. A. Sapozhenko, Hypergraph, Hazewinkel, Michiel (编), 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 
22. Brualdi, Richard A.; Harary, Frank; Miller, Zevi, Bigraphs versus digraphs via matrices, Journal of Graph Theory, 1980, 4 (1): 51–73, MR 0558453, doi:10.1002/jgt.3190040107 . Brualdi et al. credit the idea for this equivalence to Dulmage, A. L.; Mendelsohn, N. S., Coverings of bipartite graphs, Canadian Journal of Mathematics, 1958, 10: 517–534, MR 0097069, doi:10.4153/CJM-1958-052-0 .
23. Sedgewick, Robert, Algorithms in Java, Part 5: Graph Algorithms 3rd, Addison Wesley: 109–111, 2004 .
24. Kleinberg, Jon; Tardos, Éva, Algorithm Design, Addison Wesley: 94–97, 2006 .
25. Eppstein, David, Testing bipartiteness of geometric intersection graphs, ACM Transactions on Algorithms, 2009, 5 (2): Art. 15, MR 2561751, arXiv:cs.CG/0307023 , doi:10.1145/1497290.1497291 .
26. Yannakakis, Mihalis, Node-and edge-deletion NP-complete problems, Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78): 253–264, 1978, doi:10.1145/800133.804355 
27. Reed, Bruce; Smith, Kaleigh; Vetta, Adrian, Finding odd cycle transversals, Operations Research Letters, 2004, 32 (4): 299–301, CiteSeerX 10.1.1.112.6357 , MR 2057781, doi:10.1016/j.orl.2003.10.009 .
28. Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, 2006, 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001 
29. Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B., 12. Assignments and Matchings, Network Flows: Theory, Algorithms, and Applications, Prentice Hall: 461–509, 1993 .
30. Ahuja, Magnanti & Orlin (1993), p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."
31. Hopcroft, John E.; Karp, Richard M., An n^5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, 1973, 2 (4): 225–231, doi:10.1137/0202019 .
32. Ahuja, Magnanti & Orlin (1993), Application 12.1 Bipartite Personnel Assignment, pp. 463–464.
33. Dulmage & Mendelsohn (1958).
34. Moon, Todd K., Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons: 638, 2005 [2019-04-29], ISBN 9780471648000, （原始内容存档于2019-06-08） .
35. Moon (2005), p. 686.
36. Cassandras, Christos G.; Lafortune, Stephane, Introduction to Discrete Event Systems 2nd, Springer: 224, 2007 [2019-04-29], ISBN 9780387333328, （原始内容存档于2019-01-13） .
37. Grünbaum, Branko, Configurations of Points and Lines, Graduate Studies in Mathematics 103, American Mathematical Society: 28, 2009 [2019-04-29], ISBN 9780821843086, （原始内容存档于2019-06-05） .

參見

• 完全二分图
• 因子圖
• Tanner圖
• Petri網