二分图

在图论中，二分图（bipartite graph）是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点[1][2]。

二分图的范例

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

二分图的一种描述方式为：，包含了独立集 和 ，以及边 的资讯。假如不是连通图，可能有多种将所有顶点分成 和 的方式[5]；在特定的应用场合中，将顶点的两部分、写出来是有必要的。如果，则 称为平衡二分图[3]。如果二分图 以及 的顶点分别有相同的度数，则 被称为是双正则的（英语：Biregular graph）。

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

例子

二分图经常出用来研究两种不同类型的物件之间的关系。例如，如果要讨论足球球员和球队的关系，可以画一个二分图，顶点的两部分分别是所有球员和所有球队，如果球员受雇于球队，则在二者之间连边。这种二分图模型叫做附属网络（英语：affiliate network），经常用于社会网络分析（英语：social network analysis）[6]。

另一个例子出现在铁路规划问题：给定许多班火车及许多车站，每辆火车中途停靠的站不尽相同，问最少个数的车站集合使得每辆火车都停靠至少一个集合中的车站。以图论的观点来看，将火车和车站视为顶点，火车有停靠车站则连边，问题转化成是二分图的点覆盖问题。

第三个例子出现在古币学，古代的硬币有正面及反面之分，不同时期和地区的政府会使用不同的正反面组合，因此，将所有可能的组合画成图就是一个二分图的结构[7]。

其他一般性的例子诸如：

  • 所有的树都是二分图[4]。
  • 有偶数顶点个数的环 (图论)是二分图[4]。
  • 所有的平面图满足各个面的边界有偶数个边是二分图[8]，因此格子点图（英语：lattice graph）和四边形图（英语：squaregraph）都是二分图[9]。
  • 一个完全二分图 Km,n 是一个二分图，满足两个顶点集 U、V 分别有 m、n 个顶点，并且任取一个 U 中的点，所有 U 中的顶点都连边到所有 V 中的顶点[10]。
  • 皇冠图（英语：crown graph） 是将完全二分图 Kn,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 的度数定义为以它为端点的边数，记做  ，很明显的，对于二分图  ，有以下的度数和公式

 

一个二分图的度数序列是两个序列，分别列出 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]。

霍尔定理

主条目：霍尔婚配定理

霍尔定理（Hall's Theorem)表明了一个二分图G，X与Y分别是两个独立集。X能被Y匹配当且仅当 ，其中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 个顶点，则可以在  时间内输出一个二着色或奇环，纵使它的边树可能会高达  [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]。一个完美匹配是一个工作的指派使得所有人都有工作做而且每个职缺都有人做。霍尔婚配定理给出一个二分图有完美匹配的刻画。

杜尔马基-孟德尔索分解（英语：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. ^ 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 [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 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 [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网