27
个编辑
更改
跳到导航
跳到搜索
第17行：
第17行： + + + + + + + 第35行：
第42行： + + + + + + + + + + + + + + + + + + − The collection of hypergraphs is a [[Category (mathematics)|category]] with hypergraph [[homomorphism]]s as [[morphism]]s. 第50行：
第74行： + + + + + + + + + + + 第91行：
第126行： + + + + + + + 第266行：
第308行： + + + − + + + 第310行：
第357行： − + 第316行：
第363行： − + 第322行：
第369行： − + − + + + + 第331行：
第381行： − + 第338行：
第388行： − + 第366行：
第416行： + + + + + +
无编辑摘要
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''.
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''.
在[[数学中]], '''超图'''是一种广义上的[[graph(discrete mathematics)|图]] ，它的一条[[graph theory|边]]可以连接任意数量的[[vertex (graph theory)|顶点]]. 相对而言，在普通图中，一条边只能连接两个顶点.形式上, 超图 <math>H</math> 是一个集合组 <math>H = (X,E)</math> 其中<math>X</math> 是一个以节点或顶点为元素的集合，即顶点集, 而 <math>E</math> 是一组非空子，被称为边或超边.
因此，若<math>\mathcal{P}(X)</math>是 <math>E</math>的幂集，则<math>E</math>是 <math>\mathcal{P}(X) \setminus\{\emptyset\}</math> 的一个子集。在<math>H</math>中，顶点集的大小被称为超图的阶数，边集的大小被称为超图的大小。
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]].
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。因此一个 2-均匀超图就是图，一个 3-均匀超图就是三元组的集合，依此类推。超图也被称为从[[泛集]]（universal set）中抽取的一个集系统或[[集族]]。
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.
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）。特别的，每个超图都有一个与超图相对应的二分 "关联图 "或 "[[列维图]]"（Levi 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
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
}}.</ref>
}}.</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>
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>
超图还有许多其它名称。在[[计算几何学]]中，超图有时可以被称为'''范围空间'''（range space），将超图的边称为''范围''.<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>
在[[合作博弈论]]中，超图被称为'''简单博弈'''（投票博弈）；这个概念被应用于解决[[社会选择理论]]（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.
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-均匀超图；散簇，没有一条边作是另一条边的子集；以及[[抽象单纯复形]]（abstract simplicial complexes），包含每条边的所有子集。
超图是一个以超图同态为[[态射]]（morphism）的范畴。
==Terminology==
==Terminology==
* ''<math>d </math>-regular hypergraph'': a hypergraph where every vertex has degree <math>d </math>.
* ''<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.
* ''Acyclic hypergraph'': a hypergraph that does not contain any cycles.
超图有不同的类型，如：
* 空超图：没有边的超图
* 非简单（或多重）超图：允许有循环（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点。
* 简单超图：不包含循环和重复边的超图。
* 𝑘-均匀超图：每条超边都正好包含 k 个顶点的超图。
* 𝑑-正则超图：每个顶点的度数都是 𝑑 的超图
* 非循环超图：不包含任何循环的超图。
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''.
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''.
因为超图的链接可以有任意基数，所以有几种子图的概念，分别是''子超图''（subhypergraphs）、''部分超图''（partial hypergraphs）和''分段超图''（section hypergraphs）。
Let <math>H=(X,E)</math> be the hypergraph consisting of vertices
Let <math>H=(X,E)</math> be the hypergraph consisting of vertices
A [[connected graph]] ''G'' with the same vertex set as a connected hypergraph ''H'' is a '''host graph''' for ''H'' if every hyperedge of ''H'' [[induced subgraph|induces]] a connected subgraph in ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the [[connected component (graph theory)|connected components]] of ''G'' and of ''H'', such that each connected component ''G<nowiki>'</nowiki>'' of ''G'' is a host of the corresponding ''H<nowiki>'</nowiki>''.
A [[connected graph]] ''G'' with the same vertex set as a connected hypergraph ''H'' is a '''host graph''' for ''H'' if every hyperedge of ''H'' [[induced subgraph|induces]] a connected subgraph in ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the [[connected component (graph theory)|connected components]] of ''G'' and of ''H'', such that each connected component ''G<nowiki>'</nowiki>'' of ''G'' is a host of the corresponding ''H<nowiki>'</nowiki>''.
对于不连通的超图 G 和具有相同顶点连通的超图 H，如果 H 的每个超边都有 G 中一个子图连接，则 G 是一个主图（host graph）；
对于不连通的超图 H，如果 G 和 H 的连通部分之间存在一个双射，使得 G 的每个连通部分 G' 都是对应的 H' 的主图，则 G 是一个主图。
A hypergraph is ''bipartite'' if and only if its vertices can be partitioned into two classes ''U'' and ''V'' in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. Alternatively, such a hypergraph is said to have [[Property B]].
A hypergraph is ''bipartite'' if and only if its vertices can be partitioned into two classes ''U'' and ''V'' in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. Alternatively, such a hypergraph is said to have [[Property B]].
一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类 U 和 V ：每个基数至少为 2 超边包含两类中的至少一个顶点。相反的，超图则被称为具有属性 B。
The '''2-section''' (or '''clique graph''', '''representing graph''', '''primal graph''', '''Gaifman graph''') of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.
The '''2-section''' (or '''clique graph''', '''representing graph''', '''primal graph''', '''Gaifman graph''') of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.
2-段超图（或团图，代表图、原始图、盖夫曼图）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。
==二部图模型 Bipartite graph model==
==二部图模型 Bipartite graph model==
Two prominent theorems are the [[Erdős–Ko–Rado theorem]] and the [[Kruskal–Katona theorem]] on uniform hypergraphs.
Two prominent theorems are the [[Erdős–Ko–Rado theorem]] and the [[Kruskal–Katona theorem]] on uniform hypergraphs.
许多涉及图的定理和概念也适用于超图，典型的例子有[[拉姆西定理]]（Ramsey's theorem）和超图的线图。研究图的对称性的一些方法也被扩展到超图。
均匀超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。
==Hypergraph drawing==
==Hypergraph drawing==
[[File:CircuitoDosMallas.png|thumb|This [[circuit diagram]] can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.]]
[[File:CircuitoDosMallas.png|thumb|This [[circuit diagram]] can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.]]（这个线路图可以解释为一个超图，其中四个顶点（用白色的矩形和圆盘表示）由三个用树表示的超图连接）
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.
尽管超图比图更难画在纸上，但一些研究者已经研究了超图可视化方法。
In one possible visual representation for hypergraphs, similar to the standard [[graph drawing]] style in which curves in the plane are used to depict graph edges, a hypergraph's vertices are depicted as points, disks, or boxes, and its hyperedges are depicted as trees that have the vertices as their leaves.<ref>{{citation
In one possible visual representation for hypergraphs, similar to the standard [[graph drawing]] style in which curves in the plane are used to depict graph edges, a hypergraph's vertices are depicted as points, disks, or boxes, and its hyperedges are depicted as trees that have the vertices as their leaves.<ref>{{citation
| volume = 1984
| volume = 1984
| year = 2001| title-link = International Symposium on Graph Drawing
| year = 2001| title-link = International Symposium on Graph Drawing
| isbn = 978-3-540-41554-1
| isbn =
| doi-access = free
| doi-access = free
}}.</ref><ref>{{citation
}}.</ref><ref>{{citation
| last2 = Bressan | first2 = Stéphane
| last2 = Bressan | first2 = Stéphane
| contribution = Hypergraph Drawing by Force-Directed Placement
| contribution = Hypergraph Drawing by Force-Directed Placement
| doi = 10.1007/978-3-319-64471-4_31
| doi = 10.1007/_31
| pages = 387–394
| pages = 387–394
| publisher = Springer International Publishing
| publisher = Springer International Publishing
| title = 28th International Conference on Database and Expert Systems Applications (DEXA 2017)
| title = 28th International Conference on Database and Expert Systems Applications (DEXA 2017)
| volume = 10439
| volume = 10439
| year = 2017| isbn = 978-3-319-64470-7
| year = 2017| isbn =
}}.</ref>
}}.</ref>
[[File:Venn's four ellipse construction.svg|thumb|An order-4 Venn diagram, which can be interpreted as a subdivision drawing of a hypergraph with 15 vertices (the 15 colored regions) and 4 hyperedges (the 4 ellipses).]]
其中一种超图的可视化表示法，类似于标准的图的画法：用平面内的曲线来描绘图边，将超图的顶点画成点状、圆盘或盒子，超边则被描绘成以顶点为叶子的树[16][17]。如果顶点表示为点，超边也可以被描绘成连接点集的平滑曲线，或显示为封闭点集的简单闭合曲线[18][19][20]。
[[File:Venn's four ellipse construction.svg|thumb|An order-4 Venn diagram, which can be interpreted as a subdivision drawing of a hypergraph with 15 vertices (the 15 colored regions) and 4 hyperedges (the 4 ellipses).]]（一个4阶维恩图，可以被解释为一个15个顶点（15个有色区域）和4个超边（4个椭圆）的超图的细分图）
In another style of hypergraph visualization, the subdivision model of hypergraph drawing,<ref>{{citation
In another style of hypergraph visualization, the subdivision model of hypergraph drawing,<ref>{{citation
| last1 = Kaufmann | first1 = Michael
| last1 = Kaufmann | first1 = Michael
| last3 = Speckmann | first3 = Bettina | author3-link = Bettina Speckmann
| last3 = Speckmann | first3 = Bettina | author3-link = Bettina Speckmann
| contribution = Subdivision drawings of hypergraphs
| contribution = Subdivision drawings of hypergraphs
| doi = 10.1007/978-3-642-00219-9_39
| doi = 10.1007/_39
| pages = 396–407
| pages = 396–407
| publisher = Springer-Verlag
| publisher = Springer-Verlag
| volume = 5417
| volume = 5417
| year = 2009| title-link = International Symposium on Graph Drawing
| year = 2009| title-link = International Symposium on Graph Drawing
| isbn = 978-3-642-00218-2
| isbn =
| doi-access = free
| doi-access = free
}}.</ref> the plane is subdivided into regions, each of which represents a single vertex of the hypergraph. The hyperedges of the hypergraph are represented by contiguous subsets of these regions, which may be indicated by coloring, by drawing outlines around them, or both. An order-''n'' [[Venn diagram]], for instance, may be viewed as a subdivision drawing of a hypergraph with ''n'' hyperedges (the curves defining the diagram) and 2<sup>''n''</sup> − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of [[planar graph]]s, it is [[NP-complete]] to determine whether a hypergraph has a planar subdivision drawing,<ref>{{citation
}}.</ref> the plane is subdivided into regions, each of which represents a single vertex of the hypergraph. The hyperedges of the hypergraph are represented by contiguous subsets of these regions, which may be indicated by coloring, by drawing outlines around them, or both. An order-''n'' [[Venn diagram]], for instance, may be viewed as a subdivision drawing of a hypergraph with ''n'' hyperedges (the curves defining the diagram) and 2<sup>''n''</sup> − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of [[planar graph]]s, it is [[NP-complete]] to determine whether a hypergraph has a planar subdivision drawing,<ref>{{citation
| doi-access = free
| doi-access = free
}}.</ref>
}}.</ref>
超图可视化的另一种样式，是绘制超图的细分模型[21]，平面被细分为区域，每个区域代表超图的一个顶点。超图的超边用这些区域的相邻子集来表示，这些子集可以通过着色、或在它们周围画轮廓来表示，或者兼而有之。
An alternative representation of the hypergraph called PAOH<ref name="paoh" /> is shown in the figure on top of this article. Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges. It has been designed for dynamic hypergraphs but can be used for simple hypergraphs as well.
An alternative representation of the hypergraph called PAOH<ref name="paoh" /> is shown in the figure on top of this article. Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges. It has been designed for dynamic hypergraphs but can be used for simple hypergraphs as well.
超图的另一种表示法被称做 PAOH[24]，如上图所示，边是连接顶点的垂线，顶点在左边是对齐的。右边的图例显示了边的名称。它是为动态超图设计的，但也可以用于简单的超图。
==Hypergraph grammars==
==Hypergraph grammars==
{{main|Hypergraph grammar}}
{{main|Hypergraph grammar}}
By augmenting a class of hypergraphs with replacement rules, [[graph grammar]]s can be generalised to allow hyperedges.
By augmenting a class of hypergraphs with replacement rules, [[graph grammar]]s can be generalised to allow hyperedges.
通过扩充一组替换规则于超图，[[图语法]]可以被推广超边上。
== Generalizations ==
== Generalizations ==