| 第225行： |
第225行： |
| | 一致超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。 | | 一致超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。 |
| | | | |
| − | ==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.
| |
| − |
| |
| | 尽管超图比普通图更难画在纸上，但一些研究者对超图可视化方法已展开研究。 | | 尽管超图比普通图更难画在纸上，但一些研究者对超图可视化方法已展开研究。 |
| | | | |
| − | 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
| |
| − | | last = Sander | first = G.
| |
| − | | contribution = Layout of directed hypergraphs with orthogonal hyperedges
| |
| − | | pages = 381–386
| |
| − | | publisher = Springer-Verlag
| |
| − | | series = [[Lecture Notes in Computer Science]]
| |
| − | | title = Proc. 11th International Symposium on Graph Drawing (GD 2003)
| |
| − | | contribution-url = http://gdea.informatik.uni-koeln.de/585/1/hypergraph.ps
| |
| − | | volume = 2912
| |
| − | | year = 2003| title-link = International Symposium on Graph Drawing
| |
| − | }}.</ref><ref>{{citation
| |
| − | | last1 = Eschbach | first1 = Thomas
| |
| − | | last2 = Günther | first2 = Wolfgang
| |
| − | | last3 = Becker | first3 = Bernd
| |
| − | | issue = 2
| |
| − | | journal = [[Journal of Graph Algorithms and Applications]]
| |
| − | | pages = 141–157
| |
| − | | title = Orthogonal hypergraph drawing for improved visibility
| |
| − | | url = http://jgaa.info/accepted/2006/EschbachGuentherBecker2006.10.2.pdf
| |
| − | | volume = 10
| |
| − | | year = 2006 | doi=10.7155/jgaa.00122}}.</ref> If the vertices are represented as points, the hyperedges may also be shown as smooth curves that connect sets of points, or as [[simple closed curve]]s that enclose sets of points.<ref>{{citation
| |
| − | | last = Mäkinen | first = Erkki
| |
| − | | doi = 10.1080/00207169008803875
| |
| − | | issue = 3
| |
| − | | journal = International Journal of Computer Mathematics
| |
| − | | pages = 177–185
| |
| − | | title = How to draw a hypergraph
| |
| − | | volume = 34
| |
| − | | year = 1990}}.</ref><ref>{{citation
| |
| − | | last1 = Bertault | first1 = François
| |
| − | | last2 = Eades | first2 = Peter | author2-link = Peter Eades
| |
| − | | contribution = Drawing hypergraphs in the subset standard
| |
| − | | doi = 10.1007/3-540-44541-2_15
| |
| − | | pages = 45–76
| |
| − | | publisher = Springer-Verlag
| |
| − | | series = Lecture Notes in Computer Science
| |
| − | | title = Proc. 8th International Symposium on Graph Drawing (GD 2000)
| |
| − | | volume = 1984
| |
| − | | year = 2001| title-link = International Symposium on Graph Drawing
| |
| − | | isbn =
| |
| − | | doi-access = free
| |
| − | }}.</ref><ref>{{citation
| |
| − | | last1 = Naheed Anjum | first1 = Arafat
| |
| − | | last2 = Bressan | first2 = Stéphane
| |
| − | | contribution = Hypergraph Drawing by Force-Directed Placement
| |
| − | | doi = 10.1007/_31
| |
| − | | pages = 387–394
| |
| − | | publisher = Springer International Publishing
| |
| − | | series = Lecture Notes in Computer Science
| |
| − | | title = 28th International Conference on Database and Expert Systems Applications (DEXA 2017)
| |
| − | | volume = 10439
| |
| − | | year = 2017| isbn =
| |
| − | }}.</ref>
| |
| | | | |
| | 其中超图的一种可视化表示法，类似于标准的图的画法 graph drawing：用平面内的曲线来描绘图的边，将超图的顶点画成点状、圆盘或盒子，超边则被描绘成以顶点为叶子的树。<ref>{{citation | | 其中超图的一种可视化表示法，类似于标准的图的画法 graph drawing：用平面内的曲线来描绘图的边，将超图的顶点画成点状、圆盘或盒子，超边则被描绘成以顶点为叶子的树。<ref>{{citation |
| 第342行： |
第286行： |
| | [[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个椭圆）的超图的细分图）]] | | [[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
| |
| − | | last1 = Kaufmann | first1 = Michael
| |
| − | | last2 = van Kreveld | first2 = Marc
| |
| − | | last3 = Speckmann | first3 = Bettina | author3-link = Bettina Speckmann
| |
| − | | contribution = Subdivision drawings of hypergraphs
| |
| − | | doi = 10.1007/_39
| |
| − | | pages = 396–407
| |
| − | | publisher = Springer-Verlag
| |
| − | | series = Lecture Notes in Computer Science
| |
| − | | title = Proc. 16th International Symposium on Graph Drawing (GD 2008)
| |
| − | | volume = 5417
| |
| − | | year = 2009| title-link = International Symposium on Graph Drawing
| |
| − | | isbn =
| |
| − | | 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
| |
| − | | last1 = Johnson | first1 = David S. | author1-link = David S. Johnson
| |
| − | | last2 = Pollak | first2 = H. O.
| |
| − | | doi = 10.1002/jgt.3190110306
| |
| − | | issue = 3
| |
| − | | journal = Journal of Graph Theory
| |
| − | | pages = 309–325
| |
| − | | title = Hypergraph planarity and the complexity of drawing Venn diagrams
| |
| − | | volume = 11
| |
| − | | year = 2006}}.</ref> but the existence of a drawing of this type may be tested efficiently when the adjacency pattern of the regions is constrained to be a path, cycle, or tree.<ref>{{citation
| |
| − | | last1 = Buchin | first1 = Kevin
| |
| − | | last2 = van Kreveld | first2 = Marc
| |
| − | | last3 = Meijer | first3 = Henk
| |
| − | | last4 = Speckmann | first4 = Bettina
| |
| − | | last5 = Verbeek | first5 = Kevin
| |
| − | | contribution = On planar supports for hypergraphs
| |
| − | | doi = 10.1007/_33
| |
| − | | pages = 345–356
| |
| − | | publisher = Springer-Verlag
| |
| − | | series = Lecture Notes in Computer Science
| |
| − | | title = Proc. 17th International Symposium on Graph Drawing (GD 2009)
| |
| − | | volume = 5849
| |
| − | | year = 2010| title-link = International Symposium on Graph Drawing
| |
| − | | isbn =
| |
| − | | doi-access = free
| |
| − | }}.</ref>
| |
| − |
| |
| − | 超图可视化的另一种样式，是绘制超图的细分 subdivision 模型<ref>{{citation
| |
| − | | last1 = Kaufmann | first1 = Michael
| |
| − | | last2 = van Kreveld | first2 = Marc
| |
| − | | last3 = Speckmann | first3 = Bettina | author3-link = Bettina Speckmann
| |
| − | | contribution = Subdivision drawings of hypergraphs
| |
| − | | doi = 10.1007/_39
| |
| − | | pages = 396–407
| |
| − | | publisher = Springer-Verlag
| |
| − | | series = Lecture Notes in Computer Science
| |
| − | | title = Proc. 16th International Symposium on Graph Drawing (GD 2008)
| |
| − | | volume = 5417
| |
| − | | year = 2009| title-link = International Symposium on Graph Drawing
| |
| − | | isbn =
| |
| − | | doi-access = free
| |
| − | }}.</ref> ，
| |
| − | 平面被细分为区域，每个区域代表超图的一个顶点。超图的超边用这些区域的相邻子集来表示，这些子集可以通过着色，或在它们周围画轮廓来表示，或者兼而有之。<ref>{{citation
| |
| − | | last1 = Johnson | first1 = David S. | author1-link = David S. Johnson
| |
| − | | last2 = Pollak | first2 = H. O.
| |
| − | | doi = 10.1002/jgt.3190110306
| |
| − | | issue = 3
| |
| − | | journal = Journal of Graph Theory
| |
| − | | pages = 309–325
| |
| − | | title = Hypergraph planarity and the complexity of drawing Venn diagrams
| |
| − | | volume = 11
| |
| − | | year = 2006}}.</ref> but the existence of a drawing of this type may be tested efficiently when the adjacency pattern of the regions is constrained to be a path, cycle, or tree.<ref>{{citation
| |
| − | | last1 = Buchin | first1 = Kevin
| |
| − | | last2 = van Kreveld | first2 = Marc
| |
| − | | last3 = Meijer | first3 = Henk
| |
| − | | last4 = Speckmann | first4 = Bettina
| |
| − | | last5 = Verbeek | first5 = Kevin
| |
| − | | contribution = On planar supports for hypergraphs
| |
| − | | doi = 10.1007/_33
| |
| − | | pages = 345–356
| |
| − | | publisher = Springer-Verlag
| |
| − | | series = Lecture Notes in Computer Science
| |
| − | | title = Proc. 17th International Symposium on Graph Drawing (GD 2009)
| |
| − | | volume = 5849
| |
| − | | year = 2010| title-link = International Symposium on Graph Drawing
| |
| − | | isbn =
| |
| − | | doi-access = free
| |
| − | }}.</ref>
| |
| − |
| |
| − | 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<ref name="paoh" />，如上图所示，边是连接顶点的垂线，顶点是左对齐的。右边的图例显示了边的名称。它是为动态超图而设计的，但也可以用于简单的超图。 | | 超图的另一种表示法被称做 PAOH<ref name="paoh" />，如上图所示，边是连接顶点的垂线，顶点是左对齐的。右边的图例显示了边的名称。它是为动态超图而设计的，但也可以用于简单的超图。 |