7,129
个编辑
更改
跳到导航
跳到搜索
第77行：
第77行： − + − + 第86行：
第86行： + +
→与超图和有向图的关系
=== 与超图和有向图的关系 ===
=== 与超图和有向图的关系 ===
一个二分图<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>
| 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
| 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'''。
| year = 1958}}.</ref>通过这种构建方式，二分图可以被解释为是一个[[有向图]]的''' 二分双重覆盖 Bipartite double cover'''。
<br>
== 算法 ==
== 算法 ==