二分图 - 版本历史

2021年11月2日 (二) 13:24 薄荷

2021-11-02T13:24:05Z

薄荷：/* 编辑推荐 */

2021-11-02T13:22:29Z

编辑推荐

2021年11月2日 (二) 13:18 薄荷

2021-11-02T13:18:15Z

薄荷：/* 匹配 */

2021-11-02T13:17:43Z

匹配

薄荷：/* 与超图和有向图的关系 */

2021-11-02T13:16:13Z

与超图和有向图的关系

薄荷：/* 特征表述 */

2021-11-02T13:14:59Z

特征表述

薄荷：/* 柯尼希定理和完美图 Kőnig's theorem and perfect graphs */

2021-11-02T13:13:25Z

柯尼希定理和完美图 Kőnig's theorem and perfect graphs

薄荷：/* 特征表述 */

2021-11-02T13:12:38Z

特征表述

薄荷：/* 案例 */

2021-11-02T13:08:10Z

案例

薄荷：/* 属性 */

2021-11-02T13:07:23Z

属性

←上一版本		2021年11月2日 (二) 13:24的版本
第1行：		第1行：
		+	{{#seo:
		+	\|keywords=图论,树，二分图
		+	\|description=是一个曲线图，其所有顶点可以分为两个互不相交且独立的集合<math>U</math>和集合<math>V</math>，并且邻边（无向或有向）的两个顶点分别属于集合<math>U</math>和集合<math>V</math>
		+	}}


第5行：		第9行：
	[[文件:Biclique K 3 5.svg.png\|缩略图\|m=5和n=3的完全二分图示例]]		[[文件:Biclique K 3 5.svg.png\|缩略图\|m=5和n=3的完全二分图示例]]

−	~~在图论的数学领域中，~~'''二分图 Bipartite graph'''（或二部图）是一个曲线图，其所有顶点可以分为两个互不相交且独立的集合<math>U</math>和集合<math>V</math>，并且邻边（无向或有向）的两个顶点分别属于集合<math>U</math>和集合<math>V</math>。通常集合<math>U</math>和集合<math>V</math>被称为该二分图的子集。同时，二分图中不包含任何形式的奇数环，即：集合<math>U</math>和集合<math>V</math>构造的点集所形成的循环圈边数不为奇数。<ref>Diestel, Reinard (2005), Graph Theory, Graduate Texts in Mathematics, Springer, ISBN 978-3-642-14278-9</ref><ref>Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458.</ref>	+	在[[图论]]的数学领域中，'''二分图 Bipartite graph'''（或二部图）是一个曲线图，其所有顶点可以分为两个互不相交且独立的集合<math>U</math>和集合<math>V</math>，并且邻边（无向或有向）的两个顶点分别属于集合<math>U</math>和集合<math>V</math>。通常集合<math>U</math>和集合<math>V</math>被称为该二分图的子集。同时，二分图中不包含任何形式的奇数环，即：集合<math>U</math>和集合<math>V</math>构造的点集所形成的循环圈边数不为奇数。<ref>Diestel, Reinard (2005), Graph Theory, Graduate Texts in Mathematics, Springer, ISBN 978-3-642-14278-9</ref><ref>Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458.</ref>

@@ 第159行： / 第159行： @@
 ==编辑推荐==
 ===集智课程===
-====[]====
+====[https://campus.swarma.org/course/1054 二分图神经网络(BGNN)与推荐系统]====

@@ 第59行： / 第59行： @@
 根据''' 强完美图定理 Strong perfect graph theorem'''，完美图具有类似于二分图的''' 禁止图特征 Forbidden graph characterization'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为''' 导出子图Induced subgraph'''时，图才是完美的。二分图及其线图、补图占据了完美图五种基本类别中的四个，它们可以用于证明了强完美图定理。<ref>{{citation | last1 = Chudnovsky | first1 = Maria  | last2 = Robertson | first2 = Neil | last3 = Seymour | first3 = Paul | last4 = Thomas | first4 = Robin | doi = 10.4007/annals.2006.164.51 | issue = 1 | journal = Annals of Mathematics| pages = 51–229
-  | title = The strong perfect graph theorem | volume = 164 | year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070| s2cid = 119151552 }}.</ref>
+  | title = The strong perfect graph theorem | volume = 164 | year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070}}.</ref>
 <br>

@@ 第116行： / 第116行： @@
-举一个简单的例子，假设一组<math>P</math>的所有人都在一组<math>J</math>的职位中寻找工作，但并不是所有人都适合所有职位。可以将这种情况建模为一个二分图<math>(P,J,E)</math>，其中当每个求职者找到其合适的工作时产生的关系就作为连边。<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref>一个完美的匹配描述的是所有求职者同时找到所有工作的情况；''' 霍尔的婚姻定理 Hall's marriage theorem'''阐述的就是二分图允许完美匹配的特征。美国国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。
+举一个简单的例子，假设一组<math>P</math>的所有人都在一组<math>J</math>的职位中寻找工作，但并不是所有人都适合所有职位。可以将这种情况建模为一个二分图<math>(P,J,E)</math>，其中当每个求职者找到其合适的工作时产生的关系就作为连边。<ref>Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Assignments and Matchings", Network Flows: Theory, Algorithms, and Applications, Prentice Hall, pp. 463–464.</ref>一个完美的匹配描述的是所有求职者同时找到所有工作的情况；''' 霍尔的婚姻定理 Hall's marriage theorem'''阐述的就是二分图允许完美匹配的特征。美国国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。
-'''Dulmage–Mendelsohn 分解'''是二分图的结构分解，可用于寻找最大匹配。<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>
+'''Dulmage–Mendelsohn 分解'''是二分图的结构分解，可用于寻找最大匹配。<ref>Dulmage, A. L.; Mendelsohn, N. S. (1958), "Coverings of bipartite graphs", Canadian Journal of Mathematics, 10: 517–534, doi:10.4153/CJM-1958-052-0, MR 0097069</ref>
 ==其他应用 ==

@@ 第77行： / 第77行： @@
 === 与超图和有向图的关系 ===
-一个二分图<math>(U,V,E)</math>的双邻矩阵是大小为<math>|U|\times|V|</math>的（0,1）矩阵，其分别代表了每对相邻顶点集合和非相邻顶点的集合（全零矩阵）。<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref>双邻接矩阵可用于描述二分图，超图和定向图之间的等价关系。
+一个二分图<math>(U,V,E)</math>的双邻矩阵是大小为<math>|U|\times|V|</math>的（0,1）矩阵，其分别代表了每对相邻顶点集合和非相邻顶点的集合（全零矩阵）。<ref>Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458, p. 17.</ref>双邻接矩阵可用于描述二分图，超图和定向图之间的等价关系。
-超图是一种类似于无向图的组合结构。它具有顶点和连边，但是其中的边可以是任意子集组的顶点，而不必具有两个端点。可以使用二分图<math>(U,V,E)</math>来建模超图，其中<math>U</math>是超图的其中一个顶点集，<math>V</math>是该超图的连边集（称为超边集），<math>E</math>包含的连边定义为：从一个超图顶点<math>v</math>到超图连边<math>e</math>恰好当<math>v</math>是<math>e</math>的端点集之一时。在这种对应关系下，二分图的双邻矩阵正好是其相应超图的关联矩阵。作为二分图和超图之间这种对应关系的特例，任何''' 多重图 Multigraph'''（即在相同两点之间可能存在的多条边的图）都可以解释为其中一些超边具有相同端点集的超图，并且由不具有多个邻接关系的二分图表示，其中二分图的同边顶点的度数均为2。<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>
+超图是一种类似于无向图的组合结构。它具有顶点和连边，但是其中的边可以是任意子集组的顶点，而不必具有两个端点。可以使用二分图<math>(U,V,E)</math>来建模超图，其中<math>U</math>是超图的其中一个顶点集，<math>V</math>是该超图的连边集（称为超边集），<math>E</math>包含的连边定义为：从一个超图顶点<math>v</math>到超图连边<math>e</math>恰好当<math>v</math>是<math>e</math>的端点集之一时。在这种对应关系下，二分图的双邻矩阵正好是其相应超图的关联矩阵。作为二分图和超图之间这种对应关系的特例，任何''' 多重图 Multigraph'''（即在相同两点之间可能存在的多条边的图）都可以解释为其中一些超边具有相同端点集的超图，并且由不具有多个邻接关系的二分图表示，其中二分图的同边顶点的度数均为2。<ref>A. A. Sapozhenko (2001) [1994], "Hypergraph", Encyclopedia of Mathematics, EMS Press</ref>
@@ 第86行： / 第86行： @@
   | pages = 51–73 | title = Bigraphs versus digraphs via matrices | volume = 4 | year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation | doi = 10.4153/CJM-1958-052-0 | last1 = Dulmage | first1 = A. L. | last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn | mr = 0097069 | journal = Canadian Journal of Mathematics | pages = 517–534 | title = Coverings of bipartite graphs | volume = 10
   | year = 1958}}.</ref>通过这种构建方式，二分图可以被解释为是一个[[有向图]]的''' 二分双重覆盖 Bipartite double cover'''。
 == 算法 ==

@@ 第40行： / 第40行： @@
 * 当且仅当它不包含奇数环的时候，该图为二分图。
-* 当且仅当图是它是2-可着色的（即其色数小于或等于2）时，该图为二分图。<ref name="adh98-7"/>
+* 当且仅当图是它是2-可着色的（即其色数小于或等于2）时，该图为二分图。<ref name="adh98-7">Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458</ref>
 * 一个图是二部图当且仅当它的顶点集 <math>V</math>可分为2个集合 <math>A</math>和<math>B</math>，以至于<math>\sum_{v \in A} \deg(v) = \sum_{v \in B} \deg(v)</math>, <math> \forall v \in A \deg(v) \leq |B| </math> 和<math> \forall v \in B \deg(v) \leq |A| </math>
 * 任何由以下组成的二部图 <math>n</math> 顶点最多可以有 <math>n^2 / 4</math>边缘。

@@ 第50行： / 第50行： @@
 ===柯尼希定理和完美图  Kőnig's theorem and perfect graphs ===
-在二分图中，''' 最小顶点覆盖Minimum vertex cover'''（顶点数）等于''' 最大匹配数Maximum matching'''(边数)；这就是''' 柯尼希定理Kőnig's theorem'''。<ref>{{citation  | author = Kőnig, Dénes  | title = Gráfok és mátrixok  | journal = Matematikai és Fizikai Lapok  | volume = 38  | year = 1931
+在二分图中，''' 最小顶点覆盖 Minimum vertex cover'''（顶点数）等于''' 最大匹配数 Maximum matching'''(边数)；这就是''' 柯尼希定理 Kőnig's theorem'''。<ref>{{citation  | author = Kőnig, Dénes  | title = Gráfok és mátrixok  | journal = Matematikai és Fizikai Lapok  | volume = 38  | year = 1931
    | pages = 116–119}}.</ref><ref>{{citation | last1 = Gross | first1 = Jonathan L. | last2 = Yellen | first2 = Jay | edition = 2nd | isbn = 9781584885054 | page = 568 | publisher = CRC Press | series = Discrete Mathematics And Its Applications | title = Graph Theory and Its Applications
-  | url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568 | year = 2005}}.</ref> 该定理的另一种等价形式是，''' 最大独立集Maximum independent set'''（顶点数）加上最大匹配数等于顶点的数量。在任意没有孤立顶点的图中，''' 最小边覆盖Minimum edge cover'''（边数）加上最大匹配数等于顶点数。<ref>{{citation | last1 = Chartrand | first1 = Gary | last2 = Zhang | first2 = Ping | isbn = 9780486483689 | pages = 189–190 | publisher = Courier Dover Publications | title = A First Course in Graph Theory | url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189 | year = 2012}}.</ref>于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。
+  | url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568 | year = 2005}}.</ref> 该定理的另一种等价形式是，''' 最大独立集 Maximum independent set'''（顶点数）加上最大匹配数等于顶点的数量。在任意没有孤立顶点的图中，''' 最小边覆盖 Minimum edge cover'''（边数）加上最大匹配数等于顶点数。<ref>{{citation | last1 = Chartrand | first1 = Gary | last2 = Zhang | first2 = Ping | isbn = 9780486483689 | pages = 189–190 | publisher = Courier Dover Publications | title = A First Course in Graph Theory | url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189 | year = 2012}}.</ref>于是，将以上等式与柯尼希定理相结合，得出以下事实：在二分图中，最小边覆盖数值等于最大独立集数值，最小边覆盖数值加上最小顶点覆盖数值等于顶点数。
-另一类相关特性与''' 完美图Perfect graph'''有关：每个二分图及其补图、线图、线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（它们的色数为2，最大的团数同样为2），但是二分图的补图完美性的判定更简单些，且可以看作是柯尼希定理的另一种表述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。<ref>{{citation|title=Modern Graph Theory|volume= 184 |series= Graduate Texts in Mathematics|author=Béla Bollobás|publisher	=Springer|year= 1998|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> 同时完美图线图的补图完美性也是作为柯尼希定理的另一种表述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
+另一类相关特性与''' 完美图 Perfect graph'''有关：每个二分图及其补图、线图、线图的补图均为完美图。其实关于二分图的完美性很容易就可以看出来（它们的色数为2，最大的团数同样为2），但是二分图的补图完美性的判定更简单些，且可以看作是柯尼希定理的另一种表述。其实在定义完美图这一概念的初期，它是作为其中之一的论证结果而存在的。<ref>{{citation|title=Modern Graph Theory|volume= 184 |series= Graduate Texts in Mathematics|author=Béla Bollobás|publisher	=Springer|year= 1998|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> 同时完美图线图的补图完美性也是作为柯尼希定理的另一种表述，线图的完美性陈述了比较早期的柯尼希定理，即每一个二分图的着色边，其色数都等于其最大节点度数。
-根据''' 强完美图定理Strong perfect graph theorem'''，完美图具有类似于二分图的''' 禁止图特征Forbidden graph characterization'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为''' 导出子图Induced subgraph'''时，图才是完美的。二分图及其线图、补图占据了完美图五种基本类别中的四个，它们可以用于证明了强完美图定理。<ref>{{citation | last1 = Chudnovsky | first1 = Maria  | last2 = Robertson | first2 = Neil | last3 = Seymour | first3 = Paul | last4 = Thomas | first4 = Robin | doi = 10.4007/annals.2006.164.51 | issue = 1 | journal = Annals of Mathematics| pages = 51–229
+根据''' 强完美图定理 Strong perfect graph theorem'''，完美图具有类似于二分图的''' 禁止图特征 Forbidden graph characterization'''：当且仅当它没有奇环的子图时，图才是二分的；当且仅当它没有奇环或其补图作为''' 导出子图Induced subgraph'''时，图才是完美的。二分图及其线图、补图占据了完美图五种基本类别中的四个，它们可以用于证明了强完美图定理。<ref>{{citation | last1 = Chudnovsky | first1 = Maria  | last2 = Robertson | first2 = Neil | last3 = Seymour | first3 = Paul | last4 = Thomas | first4 = Robin | doi = 10.4007/annals.2006.164.51 | issue = 1 | journal = Annals of Mathematics| pages = 51–229
   | title = The strong perfect graph theorem | volume = 164 | year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070| s2cid = 119151552 }}.</ref>
 === 度相关问题===

@@ 第15行： / 第15行： @@
 == 案例 ==
 在建立两类不同对象之间的关系时，人们常常会很自然地选择二分图。以建立足球运动员和俱乐部的关系图为例，如果该球员曾为该俱乐部效力，那么在运动员和俱乐部之间就形成了一条边。这是二分图在建立隶属关系网络中的应用示例。在社交网络分析中，隶属关系便形成一种二分图。<ref>{{citation | last1 = Wasserman | first1 = Stanley | last2 = Faust | first2 = Katherine | isbn = 9780521387071 | pages = 299–302 | publisher = Cambridge University Press
   | series = Structural Analysis in the Social Sciences | title = Social Network Analysis: Methods and Applications | url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299 | volume = 8 | year = 1994}}.</ref>
@@ 第38行： / 第33行： @@
 * ''' 超立方体图 Hypercube graph'''，''' 局部立方体 Partial cube'''和''' 中位数图 Median graph'''均为二分图。判别方法是将这些图中的顶点用''' 位向量Bitvector'''（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树状图和方图都是中位数图，而所有中位数图都是局部立方体。<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.</ref>
 == 属性 ==

@@ 第43行： / 第43行： @@
 二分图可以用以下几种不同的方式来描述其特征：
-* A graph is bipartite [[if and only if]] it does not contain an [[Cycle (graph theory)|odd cycle]]. 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]].
+* 当且仅当它不包含奇数环的时候，该图为二分图。
 * 当且仅当图是2色系图2-colorable（即，其色数小于或等于2，详见“图着色”）时，该图为二分图。<ref name="adh98-7"/>
 * 当且仅当它是二分图时，图的频谱是对称的。<ref>{{citation | last = Biggs | first = Norman | edition = 2nd | isbn = 9780521458979 | page = 53
@@ 第89行： / 第86行： @@
   | pages = 51–73 | title = Bigraphs versus digraphs via matrices | volume = 4 | year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation | doi = 10.4153/CJM-1958-052-0 | last1 = Dulmage | first1 = A. L. | last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn | mr = 0097069 | journal = Canadian Journal of Mathematics | pages = 517–534 | title = Coverings of bipartite graphs | volume = 10
   | year = 1958}}.</ref>通过这种构建方式，二分图可以被解释为是一个[[有向图]]的''' 二分双重覆盖 Bipartite double cover'''。
 == 算法 ==