| 第1行： |
第1行： |
| | + | 在数学中, '''超图 hypergraph'''是一种广义上的图，是有限集合中最一般的离散结构，在信息科学、生命科学等领域有着广泛的应用。它的一条'''边 edge'''可以连接任意数量的'''顶点 vertices'''。相对而言，在普通图中，一条边只能连接两个顶点。形式上，超图 <math>H</math> 是一个有序二元组 <math>H = (X,E)</math> 其中<math>X</math> 是一个以节点 nodes或顶点为元素的非空集合，即顶点集，而 <math>E</math> 是<math>X</math> 的一组非空子集簇，<math>E</math>的元素被称为边或超边 hyperedges。 没有相同边的超图称为单超图。 |
| | | | |
| − | 我们在组织翻译超图这个词条，这个词条是之前Wolfram发的那篇长文中一个非常重要的概念，我们希望可以整理好这个词条，帮助大家更好的理解那篇文章。
| |
| − |
| |
| − |
| |
| − | 现在招募6个小伙伴一起翻译超图这个词条 https://wiki.swarma.org/index.php?title=超图_Hypergraph
| |
| − |
| |
| − | *开头正文部分+术语定义（Terminology)——十三维
| |
| − | *二分图模型+不对称性+同构与平等——淑慧
| |
| − | *对称超图+横截面——瑾晗
| |
| − | *关联矩阵+超图着色+分区---厚朴
| |
| − | *定理+超图绘制+超图语法——十三维
| |
| − | *概括+超图学习——世康
| |
| − |
| |
| − | 截止时间：北京时间18：00之前。
| |
| − |
| |
| − |
| |
| − |
| |
| − | In [[mathematics]], a '''hypergraph''' is a generalization of a [[Graph (discrete mathematics)|graph]] in which an [[graph theory|edge]] can join any number of [[vertex (graph theory)|vertices]]. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, a hypergraph <math>H</math> is a pair <math>H = (X,E)</math> where <math>X</math> is a set of elements called ''nodes'' or ''vertices'', and <math>E</math> is a set of non-empty subsets of <math>X</math> called ''[[hyperedges]]'' or ''edges''. Therefore, <math>E</math> is a subset of <math>\mathcal{P}(X) \setminus\{\emptyset\}</math>, where <math>\mathcal{P}(X)</math> is the [[power set]] of <math>X</math>. The size of the vertex set is called the ''order of the hypergraph'', and the size of edges set is the ''size of the hypergraph''.
| |
| − |
| |
| − | 在数学中, '''超图 hypergraph'''是一种广义上的图，是有限集合中最一般的离散结构，在信息科学、生命科学等领域有着广泛的应用。它的一条'''边 edge'''可以连接任意数量的'''顶点 vertices'''。相对而言，在普通图中，一条边只能连接两个顶点。形式上，超图 <math>H</math> 是一个有序二元组 <math>H = (X,E)</math> 其中<math>X</math> 是一个以节点 nodes或顶点为元素的非空集合，即顶点集，而 <math>E</math> 是<math>X</math> 的一组非空子集簇，<math>E</math>的元素被称为边或超边 hyperedges。 没有相同边的超图称为单超图。
| |
| | | | |
| | 因此，若<math>\mathcal{P}(X)</math>是 <math>E</math>的幂集 power set，则<math>X</math>是 <math>\mathcal{P}(X) \setminus\{\emptyset\}</math> 的一个子集。在<math>H</math>中，顶点集的大小被称为'''超图的阶数 order of the hypergraph'''，边集的大小被称为'''超图的大小 size of the hypergraph'''。 | | 因此，若<math>\mathcal{P}(X)</math>是 <math>E</math>的幂集 power set，则<math>X</math>是 <math>\mathcal{P}(X) \setminus\{\emptyset\}</math> 的一个子集。在<math>H</math>中，顶点集的大小被称为'''超图的阶数 order of the hypergraph'''，边集的大小被称为'''超图的大小 size of the hypergraph'''。 |
| | | | |
| − | While graph edges are 2-element subsets of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a ''k-uniform hypergraph'' is a hypergraph such that all its hyperedges have size ''k''. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting ''k'' nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. A hypergraph is also called a ''set system'' or a ''[[family of sets]]'' drawn from the [[universal set]].
| |
| | | | |
| − | 普通图的边是节点的二元子集，超边则是节点的任意集合，所以可以包含任意数量的节点。但我们总先需要研究具有相同基数超边的超图，即一个'''k-一致超图 k-uniform hypergraph'''（所有超边的大小都为 k，也译作k-均匀超图）。因此一个2-一致超图就是普通图，一个3-一致 | + | 普通图的边是节点的二元子集，超边则是节点的任意集合，所以可以包含任意数量的节点。但我们总先需要研究具有相同基数超边的超图，即一个'''k-一致超图 k-uniform hypergraph'''（所有超边的大小都为 k，也译作k-均匀超图）。因此一个2-一致超图就是普通图，一个3-一致超图就是无序三元组 unordered triples 的集合，依此类推。超图也被称为从泛集 universal set 中抽取的一个集系统 set system 或集族 family of sets。 |
| | | | |
| − | 超图就是无序三元组 unordered triples 的集合，依此类推。超图也被称为从泛集 universal set 中抽取的一个集系统 set system 或集族 family of sets。
| |
| − |
| |
| − | Hypergraphs can be viewed as [[incidence structure]]s. In particular, there is a bipartite "incidence graph" or "[[Levi graph]]" corresponding to every hypergraph, and conversely, most, but not all, [[bipartite graph]]s can be regarded as incidence graphs of hypergraphs.
| |
| | | | |
| | 超图可以看做是'''关联结构 incidence structure'''。特别的，每个超图都有一个与超图相对应的二分 "关联图 incidence graph"或 "列维图 Levi graph"，反之，大多数（但不是全部）'''二分图 bipartite graph'''都可以看作是超图的关联图。 | | 超图可以看做是'''关联结构 incidence structure'''。特别的，每个超图都有一个与超图相对应的二分 "关联图 incidence graph"或 "列维图 Levi graph"，反之，大多数（但不是全部）'''二分图 bipartite graph'''都可以看作是超图的关联图。 |
| | | | |
| − | Hypergraphs have many other names. In [[computational geometry]], a hypergraph may sometimes be called a '''range space''' and then the hyperedges are called ''ranges''.<ref>{{citation
| |
| − | | last1 = Haussler | first1 = David | author1-link = David Haussler
| |
| − | | last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
| |
| − | | doi = 10.1007/BF02187876
| |
| − | | issue = 2
| |
| − | | journal = [[Discrete and Computational Geometry]]
| |
| − | | mr = 884223
| |
| − | | pages = 127–151
| |
| − | | title = ε-nets and simplex range queries
| |
| − | | volume = 2
| |
| − | | year = 1987| doi-access = free
| |
| − | }}.</ref>
| |
| − | In [[cooperative game]] theory, hypergraphs are called '''simple games''' (voting games); this notion is applied to solve problems in [[social choice theory]]. In some literature edges are referred to as ''hyperlinks'' or ''connectors''.<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>
| |
| | | | |
| | 超图还有许多其它名称。在'''计算几何学 family of sets'''中，超图有时可以被称为'''范围空间 range space'''，将超图的边称为''范围 ranges''.<ref>{{citation | | 超图还有许多其它名称。在'''计算几何学 family of sets'''中，超图有时可以被称为'''范围空间 range space'''，将超图的边称为''范围 ranges''.<ref>{{citation |
| 第58行： |
第23行： |
| | | year = 1987 | | | year = 1987 |
| | }}.</ref> | | }}.</ref> |
| | + | |
| | + | |
| | 在合作博弈论 cooperative game中，超图被称为'''简单博弈 simple games'''（投票博弈 voting games）；这个概念被应用于解决社会选择理论 social choice theory 中的问题。在一些文献中，超边被称为''超连接''或''连接器''。<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref> | | 在合作博弈论 cooperative game中，超图被称为'''简单博弈 simple games'''（投票博弈 voting games）；这个概念被应用于解决社会选择理论 social choice theory 中的问题。在一些文献中，超边被称为''超连接''或''连接器''。<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref> |
| | | | |
| − | Special kinds of hypergraphs include: [[#Symmetric hypergraphs|''k''-uniform ones]], as discussed briefly above; [[clutter (mathematics)|clutter]]s, where no edge appears as a subset of another edge; and [[abstract simplicial complex]]es, which contain all subsets of every edge.
| |
| − | The collection of hypergraphs is a [[Category (mathematics)|category]] with hypergraph [[homomorphism]]s as [[morphism]]s.
| |
| | | | |
| | 特殊类型的超图包括：上文简单讨论过的k-一致超图；散簇 clutter，也即没有一条边作是另一条边的子集；以及'''抽象单纯复形 abstract simplicial complexes'''，这里面包含每条边的所有子集。 | | 特殊类型的超图包括：上文简单讨论过的k-一致超图；散簇 clutter，也即没有一条边作是另一条边的子集；以及'''抽象单纯复形 abstract simplicial complexes'''，这里面包含每条边的所有子集。 |
| | + | |
| | | | |
| | 超图是一个以超图同态 homomorphism 为'''态射 morphism '''的范畴。 | | 超图是一个以超图同态 homomorphism 为'''态射 morphism '''的范畴。 |
| | | | |
| | | | |
| − | ==术语 Terminology== | + | ==术语== |
| − | | + | ====定义==== |
| − | ====定义 Definitions ==== | |
| − | There are different types of hypergraphs such as:
| |
| − | * ''Empty hypergraph'': a hypergraph with no edges.
| |
| − | * ''Non-simple (or multiple) hypergraph'': a hypergraph allowing loops (hyperedges with a single vertex) or repeated edges, which means there can be two or more edges containing the same set of vertices.
| |
| − | * ''Simple hypergraph'': a hypergraph that contains no loops and no repeated edges.
| |
| − | * ''<math>k </math>-uniform hypergraph'': a hypergraph where each edge contains precisely <math>k</math> vertices.
| |
| − | * ''<math>d </math>-regular hypergraph'': a hypergraph where every vertex has degree <math>d </math>.
| |
| − | * ''Acyclic hypergraph'': a hypergraph that does not contain any cycles.
| |
| − | | |
| | 超图有不同的类型，如： | | 超图有不同的类型，如： |
| | | | |
| − | * 空超图 Empty hypergraph：没有边的超图 | + | * 空超图 Empty hypergraph：没有边的超图； |
| | | | |
| − | * 非简单（或多重）超图 Non-simple (or multiple) hypergraph ：允许有环 loops（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点。 | + | * 非简单（或多重）超图 Non-simple (or multiple) hypergraph ：允许有环 loops（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点； |
| | | | |
| − | * 简单超图 Simple hypergraph ：不包含循环和重复边的超图。 | + | * 简单超图 Simple hypergraph ：不包含循环和重复边的超图； |
| | | | |
| − | * <math>k </math>-一致超图 <math>k </math>-uniform hypergraph：每条超边都正好包含 k 个顶点的超图。 | + | * <math>k </math>-一致超图 <math>k </math>-uniform hypergraph：每条超边都正好包含 k 个顶点的超图； |
| | | | |
| − | * <math>d </math>-正则超图 <math>d </math>-regular hypergraph：每个顶点的度数都是 𝑑 的超图。 | + | * <math>d </math>-正则超图 <math>d </math>-regular hypergraph：每个顶点的度数都是 𝑑 的超图； |
| | | | |
| | * 无环超图 Acyclic hypergraph：不包含任何环的超图。 | | * 无环超图 Acyclic hypergraph：不包含任何环的超图。 |