跳转到内容

二分图

维基百科，自由的百科全书

这是本页的一个历史版本，由Roland Feng（留言 | 贡献）在2019年8月8日 (四) 18:45 （→，而事實上，這個問題的難度是NP完全的：​删除了这句话。二分图的顶点覆盖问题不是NP完全问题，有P类算法可以解决。）编辑。这可能和当前版本存在着巨大的差异。

二分圖的範例

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

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

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

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

例子

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

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

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

其他一般性的例子諸如：

特性

等價條件

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

柯尼希定理

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

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

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

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

完美圖

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

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

度數

一個頂點 v 的度數定義為以它為端點的邊數，記做 ，很明顯的，對於二分圖 ，有以下的度數和公式

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

與超圖及有向圖的關係

一個兩部分分別有 m 和 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。此時，有向圖的相鄰矩陣可以是任意 階 (0,1) 矩陣，而且會一對一對應到平衡二分圖的雙相鄰矩陣[22]。

演算法

二分性測試

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

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

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

奇環代表系

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

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

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

匹配

主条目：匹配 (圖論)

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

舉個簡單的例子，假設有一些人想要找尋工作，他們形成集合 P，此外還有一些職缺，它們形成集合 J，並不是所有人都適合所有的工作，但一個人只能做一份工作。這個案例可以被建模成一個二分圖，如果一個人可以做某項工作則將二者連邊[32]。一個完美匹配是一個工作的指派使得所有人都有工作做而且每個職缺都有人做。赫爾婚姻定理（英语：Hall's marriage theorem）給出一個二分圖有完美匹配的刻畫。

杜爾馬基-孟德爾索分解（英语：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. ISBN 978-3-642-14278-9. 
  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. ^ 3.0 3.1 3.2 Asratian, Denley & Häggkvist (1998), p. 7.
  4. ^ 4.0 4.1 4.2 Scheinerman, Edward R., Mathematics: A Discrete Introduction 3rd, Cengage Learning: 363, 2012, ISBN 9780840049421 .
  5. ^ Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, Discrete Mathematics And Its Applications 53, CRC Press: 223, 2008, ISBN 9781584888000 .
  6. ^ Wasserman, Stanley; Faust, Katherine, Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences 8, Cambridge University Press: 299–302, 1994, ISBN 9780521387071 .
  7. ^ Bracey, Robert. On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins. 2012: 65–84. 
  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, ISBN 9780521458979 .
  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, ISBN 9781584885054 .
  17. ^ Chartrand, Gary; Zhang, Ping, A First Course in Graph Theory, Courier Dover Publications: 189–190, 2012, ISBN 9780486483689 .
  18. ^ Béla Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer: 165, 1998, ISBN 9780387984889 .
  19. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229, CiteSeerX 10.1.1.111.7265 可免费查阅, arXiv:math/0212070 可免费查阅, doi:10.4007/annals.2006.164.51 .
  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 n5/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, ISBN 9780471648000 .
  35. ^ Moon (2005), p. 686.
  36. ^ Cassandras, Christos G.; Lafortune, Stephane, Introduction to Discrete Event Systems 2nd, Springer: 224, 2007, ISBN 9780387333328 .
  37. ^ Grünbaum, Branko, Configurations of Points and Lines, Graduate Studies in Mathematics 103, American Mathematical Society: 28, 2009, ISBN 9780821843086 .

參見

检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=二分图&oldid=55571734”