Hypergraph

An example of an undirected hypergraph, with and . This hypergraph has order 7 and size 4. Here, edges do not just connect two vertices but several, and are represented by colors.
PAOH visualization of a hypergraph
Alternative representation of the hypergraph reported in the figure above, called PAOH.[1] Edges are vertical lines connecting vertices. V7 is an isolated vertex. Vertices are aligned to the left. The legend on the right shows the names of the edges.
An example of a directed hypergraph, with and .

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

Formally, a directed hypergraph is a pair , where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of . Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain.

The order of a hypergraph is the number of vertices in . The size of the hypergraph is the number of edges in . The order of an edge in a directed hypergraph is : that is, the number of vertices in its tail followed by the number of vertices in its head.

The definition above generalizes from a directed graph to a directed hypergraph by defining the head or tail of each edge as a set of vertices ( or ) rather than as a single vertex. A graph is then the special case where each of these sets contains only one element. Hence any standard graph theoretic concept that is independent of the edge orders will generalize to hypergraph theory.

An undirected hypergraph is an undirected graph whose edges connect not just two vertices, but an arbitrary number.[2] An undirected hypergraph is also called a set system or a family of sets drawn from the universal set.

Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, every bipartite graph can be regarded as the incidence graph of a hypergraph when it is 2-colored and it is indicated which color class corresponds to hypergraph vertices and which to hypergraph edges.

Hypergraphs have many other names. In computational geometry, an undirected hypergraph may sometimes be called a range space and then the hyperedges are called ranges.[3] 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.[4]

The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.

Applications

Undirected hypergraphs are useful in modelling such things as satisfiability problems,[5] databases,[6] machine learning,[7] and Steiner tree problems.[8] They have been extensively used in machine learning tasks as the data model and classifier regularization (mathematics).[9] The applications include recommender system (communities as hyperedges),[10] [11] image retrieval (correlations as hyperedges),[12] and bioinformatics (biochemical interactions as hyperedges).[13] Representative hypergraph learning techniques include hypergraph spectral clustering that extends the spectral graph theory with hypergraph Laplacian,[14] and hypergraph semi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results.[15] For large scale hypergraphs, a distributed framework[7] built using Apache Spark is also available. It can be 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.

Directed hypergraphs can be used to model things including telephony applications,[16] detecting money laundering,[17] operations research,[18] and transportation planning. They can also be used to model Horn-satisfiability.[19]

Generalizations of concepts from graphs

Many theorems and concepts involving graphs also hold for hypergraphs, in particular:

In directed hypergraphs: transitive closure, and shortest path problems.[18]

Hypergraph drawing

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.[20][21] 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 curves that enclose sets of points.[22][23][24]

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).

In another style of hypergraph visualization, the subdivision model of hypergraph drawing,[25] 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 2n − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of planar graphs, it is NP-complete to determine whether a hypergraph has a planar subdivision drawing,[26] 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.[27]

An alternative representation of the hypergraph called PAOH[1] 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.

Hypergraph coloring

Classic hypergraph coloring is assigning one of the colors from set to every vertex of a hypergraph in such a way that each hyperedge contains at least two vertices of distinct colors. In other words, there must be no monochromatic hyperedge with cardinality at least 2. In this sense it is a direct generalization of graph coloring. Minimum number of used distinct colors over all colorings is called the chromatic number of a hypergraph.

Hypergraphs for which there exists a coloring using up to k colors are referred to as k-colorable. The 2-colorable hypergraphs are exactly the bipartite ones.

There are many generalizations of classic hypergraph coloring. One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed. Some mixed hypergraphs are uncolorable for any number of colors. A general criterion for uncolorability is unknown. When a mixed hypergraph is colorable, then the minimum and maximum number of used colors are called the lower and upper chromatic numbers respectively.[28]

Properties of hypergraphs

A hypergraph can have various properties, such as:

  • Empty - has no edges.
  • Non-simple (or multiple) - has 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 - has no loops and no repeated edges.
  • -regular - every vertex has degree , i.e., contained in exactly hyperedges.
  • 2-colorable - 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. An alternative term is Property B.
  • -uniform - each hyperedge contains precisely vertices.
  • -partite - the vertices are partitioned into parts, and each hyperedge contains precisely one vertex of each type.
    • Every -partite hypergraph (for ) is both -uniform and bipartite (and 2-colorable).
  • Reduced:[29] no hyperedge is a strict subset of another hyperedge; equivalently, every hyperedge is maximal for inclusion. The reduction of a hypergraph is the reduced hypergraph obtained by removing every hyperedge which is included in another hyperedge.
  • Downward-closed - every subset of an undirected hypergraph's edges is a hyperedge too. A downward-closed hypergraph is usually called an abstract simplicial complex. It is generally not reduced, unless all hyperedges have cardinality 1.
    • An abstract simplicial complex with the augmentation property is called a matroid.
  • Laminar: for any two hyperedges, either they are disjoint, or one is included in the other. In other words, the set of hyperedges forms a laminar set family.

Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called subhypergraphs, partial hypergraphs and section hypergraphs.

Let be the hypergraph consisting of vertices

and having edge set

where and are the index sets of the vertices and edges respectively.

A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph induced by is defined as

An alternative term is the restriction of H to A.[30]: 468 

An extension of a subhypergraph is a hypergraph where each hyperedge of which is partially contained in the subhypergraph is fully contained in the extension . Formally

with and .

The partial hypergraph is a hypergraph with some edges removed.[30]: 468  Given a subset of the edge index set, the partial hypergraph generated by is the hypergraph

Given a subset , the section hypergraph is the partial hypergraph

The dual of is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by and whose edges are given by where

When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, i.e.,

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 induces a connected subgraph in G. For a disconnected hypergraph H, G is a host graph if there is a bijection between the connected components of G and of H, such that each connected component G' of G is a host of the corresponding H'.

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.

Incidence matrix

Let and . Every hypergraph has an incidence matrix.

For an undirected hypergraph, where

The transpose of the incidence matrix defines a hypergraph called the dual of , where is an m-element set and is an n-element set of subsets of . For and if and only if .

For a directed hypergraph, the heads and tails of each hyperedge are denoted by and respectively.[19] where

Incidence graph

A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the parts of BG, and (x1, e1) are connected with an edge if and only if vertex x1 is contained in edge e1 in H.

Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.

Adjacency matrix

A parallel for the adjacency matrix of a hypergraph can be drawn from the adjacency matrix of a graph. In the case of a graph, the adjacency matrix is a square matrix which indicates whether pairs of vertices are adjacent. Likewise, we can define the adjacency matrix for a hypergraph in general where the hyperedges have real weights with

Cycles

In contrast with ordinary undirected graphs for which there is a single natural notion of cycles and acyclic graphs, there are multiple natural non-equivalent definitions of acyclicity for hypergraphs which collapse to ordinary graph acyclicity for the special case of ordinary graphs.

A first definition of acyclicity for hypergraphs was given by Claude Berge:[31] a hypergraph is Berge-acyclic if its incidence graph (the bipartite graph defined above) is acyclic. This definition is very restrictive: for instance, if a hypergraph has some pair of vertices and some pair of hyperedges such that and , then it is Berge-cyclic. Berge-cyclicity can obviously be tested in linear time by an exploration of the incidence graph.

We can define a weaker notion of hypergraph acyclicity,[6] later termed α-acyclicity. This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph being chordal; it is also equivalent to reducibility to the empty graph through the GYO algorithm[32][33] (also known as Graham's algorithm), a confluent iterative process which removes hyperedges using a generalized definition of ears. In the domain of database theory, it is known that a database schema enjoys certain desirable properties if its underlying hypergraph is α-acyclic.[34] Besides, α-acyclicity is also related to the expressiveness of the guarded fragment of first-order logic.

We can test in linear time if a hypergraph is α-acyclic.[35]

Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming, Ronald Fagin[36] defined the stronger notions of β-acyclicity and γ-acyclicity. We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent[36] to an earlier definition by Graham.[33] The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to Bachman diagrams. Both β-acyclicity and γ-acyclicity can be tested in polynomial time.

Those four notions of acyclicity are comparable: Berge-acyclicity implies γ-acyclicity which implies β-acyclicity which implies α-acyclicity. However, none of the reverse implications hold, so those four notions are different.[36]

Isomorphism, symmetry, and equality

A hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.

A hypergraph is isomorphic to a hypergraph , written as if there exists a bijection

and a permutation of such that

The bijection is then called the isomorphism of the graphs. Note that

if and only if .

When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism. One says that is strongly isomorphic to if the permutation is the identity. One then writes . Note that all strongly isomorphic graphs are isomorphic, but not vice versa.

When the vertices of a hypergraph are explicitly labeled, one has the notions of equivalence, and also of equality. One says that is equivalent to , and writes if the isomorphism has

and

Note that

if and only if

If, in addition, the permutation is the identity, one says that equals , and writes . Note that, with this definition of equality, graphs are self-dual:

A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph H (= (XE)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H).

Examples

Consider the hypergraph with edges

and

Then clearly and are isomorphic (with , etc.), but they are not strongly isomorphic. So, for example, in , vertex meets edges 1, 4 and 6, so that,

In graph , there does not exist any vertex that meets edges 1, 4 and 6:

In this example, and are equivalent, , and the duals are strongly isomorphic: .

Symmetry

The rank of a hypergraph is the maximum cardinality of any of the edges in the hypergraph. If all edges have the same cardinality k, the hypergraph is said to be uniform or k-uniform, or is called a k-hypergraph. A graph is just a 2-uniform hypergraph.

The degree d(v) of a vertex v is the number of edges that contain it. H is k-regular if every vertex has degree k.

The dual of a uniform hypergraph is regular and vice versa.

Two vertices x and y of H are called symmetric if there exists an automorphism such that . Two edges and are said to be symmetric if there exists an automorphism such that .

A hypergraph is said to be vertex-transitive (or vertex-symmetric) if all of its vertices are symmetric. Similarly, a hypergraph is edge-transitive if all edges are symmetric. If a hypergraph is both edge- and vertex-symmetric, then the hypergraph is simply transitive.

Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity.

Partitions

A partition theorem due to E. Dauber[37] states that, for an edge-transitive hypergraph , there exists a partition

of the vertex set such that the subhypergraph generated by is transitive for each , and such that

where is the rank of H.

As a corollary, an edge-transitive hypergraph that is not vertex-transitive is bicolorable.

Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design[38] and parallel computing.[39][40][41] Efficient and scalable hypergraph partitioning algorithms are also important for processing large scale hypergraphs in machine learning tasks.[7]

Further generalizations

One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ad infinitum. In essence, every edge is just an internal node of a tree or directed acyclic graph, and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout computer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of term algebra; edges correspond to terms and vertices correspond to constants or variables.

For such a hypergraph, set membership then provides an ordering, but the ordering is neither a partial order nor a preorder, since it is not transitive. The graph corresponding to the Levi graph of this generalization is a directed acyclic graph. Consider, for example, the generalized hypergraph whose vertex set is and whose edges are and . Then, although and , it is not true that . However, the transitive closure of set membership for such hypergraphs does induce a partial order, and "flattens" the hypergraph into a partially ordered set.

Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges and , and zero vertices, so that and . As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer bipartite, but is rather just some general directed graph.

The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply

See also

  • BF-graph – Type of directed hypergraph
  • Combinatorial design – Symmetric arrangement of finite sets
  • Factor graph – bipartite graph representing the factorization of a function
  • Greedoid – Set system used in greedy optimization
  • Incidence structure – Abstract mathematical system of two types of objects and a relation between them
  • Multigraph – Graph with multiple edges between two vertices
  • P system – Computational model
  • Sparse matrix–vector multiplication – Computation routine
  • Petri Net – Model to describe distributed systems

Notes

  1. ^ a b Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization" (PDF). IEEE Transactions on Visualization and Computer Graphics. 26 (1). IEEE: 12. doi:10.1109/TVCG.2019.2933196. eISSN 1941-0506. ISSN 1077-2626. PMID 31398121. S2CID 199518871. Archived (PDF) from the original on 2021-01-26. Retrieved 2020-09-08.
  2. ^ Ouvrard, Xavier (2020), "Hypergraphs: an introduction and review", arXiv:2002.05014 [cs.DM].
  3. ^ Haussler, David; Welzl, Emo (1987), "ε-nets and simplex range queries", Discrete and Computational Geometry, 2 (2): 127–151, doi:10.1007/BF02187876, MR 0884223.
  4. ^ Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Company. p. 25. ISBN 978-0-201-05594-8. Archived from the original on 2023-02-04. Retrieved 2021-06-12.
  5. ^ Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006). Witnesses for non-satisfiability of dense random 3CNF formulas. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE. pp. 497–508. doi:10.1109/FOCS.2006.78. Archived from the original on 2021-01-27. Retrieved 2021-01-20.
  6. ^ a b Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M. (1983). "On the Desirability of Acyclic Database Schemes" (PDF). Journal of the ACM. 30 (3): 479–513. doi:10.1145/2402.322389. S2CID 2418740. Archived (PDF) from the original on 2021-04-21. Retrieved 2021-01-03.
  7. ^ a b c Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015). "Scalable Hypergraph Learning and Processing". 2015 IEEE International Conference on Data Mining (PDF). pp. 775–780. doi:10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. S2CID 5130573. Archived (PDF) from the original on 2021-01-26. Retrieved 2021-01-08.
  8. ^ Brazil, M; Zachariasen, M (2015). "Steiner Trees in Graphs and Hypergraphs". Optimal Interconnection Trees in the Plane. Algorithms and Combinatorics. Vol. 29. Springer. pp. 301–317. doi:10.1007/978-3-319-13915-9_5. ISBN 978-3-319-13915-9. Archived from the original on 2021-01-29. Retrieved 2021-01-20.
  9. ^ Zhou, Dengyong; Huang, Jiayuan; Scholkopf, Bernhard (2006), "Learning with hypergraphs: clustering, classification, and embedding", Advances in Neural Information Processing Systems, MIT Press, pp. 1601–8, ISBN 9780262256919, archived from the original on 2021-10-22, retrieved 2021-07-24
  10. ^ Ghoshal, Gourab; Zlatic, Vinko; Caldarelli, Guido; Newman, Mark E.J. (2009), "Random Hypergraphs and their applications", Physical Review E, 79 (6): 066118, arXiv:0903.0419, Bibcode:2009PhRvE..79f6118G, doi:10.1103/PhysRevE.79.066118, PMID 19658575, S2CID 6391099
  11. ^ Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (October 2011), "Using rich social media information for music recommendation via hypergraph model", ACM Transactions on Multimedia Computing, Communications, and Applications, 7S (1), Article 22, Bibcode:2011smma.book..213T, doi:10.1145/2037676.2037679, S2CID 432036
  12. ^ Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013), "Hypergraph with sampling for image retrieval", Pattern Recognition, 44 (10–11): 2255–2262, doi:10.1016/j.patcog.2010.07.014
  13. ^ Patro, Rob; Kingsoford, Carl (2013), "Predicting protein interactions via parsimonious network history inference", Bioinformatics, 29 (10–11): 237–246, doi:10.1093/bioinformatics/btt224, PMC 3694678, PMID 23812989
  14. ^ Gao, Tue; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Visual-textual joint relevance learning for tag-based social image search", IEEE Transactions on Image Processing, 22 (1): 363–376, Bibcode:2013ITIP...22..363Y, doi:10.1109/tip.2012.2202676, PMID 22692911, S2CID 7432373, archived from the original on 2017-09-23, retrieved 2017-09-22
  15. ^ Tian, Ze; Hwang, TaeHyun; Kuang, Rui (2009), "A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge", Bioinformatics, 25 (21): 2831–2838, doi:10.1093/bioinformatics/btp467, PMID 19648139
  16. ^ Goldstein, A. (1982). "A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant". Bell System Technical Journal. 61 (9): 2529–54. doi:10.1002/j.1538-7305.1982.tb03439.x. S2CID 11290643.
  17. ^ Ranshous, Stephen; Joslyn, Cliff; Kreyling, Sean; Nowak, Kathleen; Samatova, Nagiza; West, Curtis; Winters, Samuel (2017). Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph (PDF). Financial Cryptography and Data Security. Springer. doi:10.1007/978-3-319-70278-0_16. Archived (PDF) from the original on 2021-07-15. Retrieved 2021-01-20.
  18. ^ a b Ausiello, Giorgio; Laura, Luigi (2017). "Directed hypergraphs: Introduction and fundamental algorithms - A survey". Theoretical Computer Science. 658: 293–306. doi:10.1016/j.tcs.2016.03.016.
  19. ^ a b Gallo, G.; Longo, G.; Pallottino, S.; Nguyen, S. (1993). "Directed hypergraphs and applications". Discrete Applied Mathematics. 42 (2–3): 177–201. doi:10.1016/0166-218X(93)90045-P.
  20. ^ Sander, G. (2003), "Layout of directed hypergraphs with orthogonal hyperedges", Proc. 11th International Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, vol. 2912, Springer, pp. 381–6, ISBN 978-3-540-24595-7, archived from the original on 2011-07-18, retrieved 2010-05-17.
  21. ^ Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Orthogonal hypergraph drawing for improved visibility" (PDF), Journal of Graph Algorithms and Applications, 10 (2): 141–157, doi:10.7155/jgaa.00122, archived (PDF) from the original on 2011-07-18, retrieved 2010-05-17.
  22. ^ Mäkinen, Erkki (1990), "How to draw a hypergraph", International Journal of Computer Mathematics, 34 (3): 177–185, doi:10.1080/00207169008803875.
  23. ^ Bertault, François; Eades, Peter (2001), "Drawing hypergraphs in the subset standard", Graph Drawing, Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, pp. 45–76, doi:10.1007/3-540-44541-2_15, ISBN 978-3-540-41554-1.
  24. ^ Naheed Anjum, Arafat; Bressan, Stéphane (2017), "Hypergraph Drawing by Force-Directed Placement", Database and Expert Systems Applications, Lecture Notes in Computer Science, vol. 10439, Springer International Publishing, pp. 387–394, doi:10.1007/978-3-319-64471-4_31, ISBN 978-3-319-64470-7.
  25. ^ Kaufmann, Michael; van Kreveld, Marc; Speckmann, Bettina (2009), "Subdivision drawings of hypergraphs", Graph Drawing, Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, pp. 396–407, doi:10.1007/978-3-642-00219-9_39, ISBN 978-3-642-00218-2.
  26. ^ Johnson, David S.; Pollak, H. O. (2006), "Hypergraph planarity and the complexity of drawing Venn diagrams", Journal of Graph Theory, 11 (3): 309–325, doi:10.1002/jgt.3190110306.
  27. ^ Buchin, Kevin; van Kreveld, Marc; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2010), "On planar supports for hypergraphs", Graph Drawing, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 345–356, doi:10.1007/978-3-642-11805-0_33, ISBN 978-3-642-11804-3.
  28. ^ "Vitaly Voloshin: Mixed Hypergraph Coloring Website". spectrum.troy.edu. Archived from the original on 2022-01-20. Retrieved 2022-04-27.
  29. ^ Fagin, Ronald (1983-07-01). "Degrees of acyclicity for hypergraphs and relational database schemes". Journal of the ACM. 30 (3): 514–550. doi:10.1145/2402.322390. ISSN 0004-5411.
  30. ^ a b Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
  31. ^ Berge, Claude (1973). Graphs and Hypergraphs. Amsterdam: North-Holland. ISBN 0-7204-2450-X.
  32. ^ Yu, C. T.; Özsoyoğlu, M. Z. (1979). "An algorithm for tree-query membership of a distributed query" (PDF). Proc. IEEE COMPSAC: 306–312. doi:10.1109/CMPSAC.1979.762509. Archived (PDF) from the original on 2018-09-02. Retrieved 2018-09-02.
  33. ^ a b Graham, M. H. (1979). "On the universal relation". Technical Report. Toronto, Ontario, Canada: University of Toronto.
  34. ^ Abiteboul, S.; Hull, R. B.; Vianu, V. (1995). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.
  35. ^ Tarjan, R. E.; Yannakakis, M. (1984). "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs". SIAM Journal on Computing. 13 (3): 566–579. doi:10.1137/0213035.
  36. ^ a b c Fagin, Ronald (1983). "Degrees of Acyclicity for Hypergraphs and Relational Database Schemes". Journal of the ACM. 30 (3): 514–550. doi:10.1145/2402.322390. S2CID 597990.
  37. ^ Harary, F. (2018) [1969]. Graph Theory. CRC Press. p. 172. ISBN 978-0-429-96231-8. Archived from the original on 2023-02-04. Retrieved 2021-06-12. We next state a theorem due to Elayne Dauber whose corollaries describe properties of line-symmetric graphs. Note the obvious but important observation that every line-symmetric graph is line-regular.
  38. ^ Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (March 1999), "Multilevel hypergraph partitioning: applications in VLSI domain", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1): 69–79, CiteSeerX 10.1.1.553.2367, doi:10.1109/92.748202.{{citation}}: CS1 maint: multiple names: authors list (link)
  39. ^ Hendrickson, B., Kolda, T.G. (2000), "Graph partitioning models for parallel computing", Parallel Computing (Submitted manuscript), 26 (12): 1519–1545, doi:10.1016/S0167-8191(00)00048-X, archived from the original on 2021-01-26, retrieved 2018-10-13.{{citation}}: CS1 maint: multiple names: authors list (link)
  40. ^ Catalyurek, U.V.; Aykanat, C. (1995). A Hypergraph Model for Mapping Repeated Sparse Matrix–Vector Product Computations onto Multicomputers. Proc. International Conference on Hi Performance Computing (HiPC'95).
  41. ^ Catalyurek, U.V.; Aykanat, C. (1999), "Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", IEEE Transactions on Parallel and Distributed Systems, 10 (7): 673–693, CiteSeerX 10.1.1.67.2498, doi:10.1109/71.780863.

References

  • PAOHVis: open-source PAOHVis system for visualizing dynamic hypergraphs.

Read other articles:

ماكس بويغ   معلومات شخصية الميلاد العقد 1940  مواطنة جمهورية الدومينيكان  الحياة العملية المهنة سياسي  تعديل مصدري - تعديل   ماكس بويغ هو سياسي دومينيكاني، ولد في 1945.[1][2][3] مراجع ^ Entregan Medalla al Mérito a 10 mujeres (بالإسبانية). Santo Domingo: Diario Libre. 10 Mar 2009. Archived from the origin...

Ніна МаракінаЗагальна інформаціяГромадянство  СРСР РосіяНародження 18 лютого 1947(1947-02-18) (76 років)ХарківСпортКраїна  СРСР →  УкраїнаВид спорту легка атлетикаДисципліна метання списа Участь і здобутки У Вікіпедії є статті про інших людей із прізвищем Маракіна. �...

Ehemaliger Kanton Marseille-Mazargues Region Provence-Alpes-Côte d’Azur Département Bouches-du-Rhône Arrondissement Marseille Auflösungsdatum 29. März 2015 Einwohner 38.005 (1. Jan. 2012) Bevölkerungsdichte 662 Einw./km² Fläche 57.41 km² Gemeinden 1 INSEE-Code 1346 Lage des Kantons Marseille-Mazargues im Département Bouches-du-Rhône Der Kanton Marseille-Mazargues war bis 2015 ein französischer Wahlkreis im Arrondissement Marseille, im Département Bouches-du-Rh

Cancionero de Upsala The Cancionero de Upsala [sic], also known by the titles Cancionero del Duque de Calabria and Cancionero de Venecia, is a volume of mostly anonymous Spanish music printed in Venice in 1556. Its actual title is Villancicos de diversos Autores, a dos, y a tres, y a quatro, y a cinco bozes, agora nuevamente corregidos. Ay mas ocho tonos de Canto llano, y ocho tonos de Canto de Organo para que puedan aprovechar los que A cantar començaren. Venetiis, Apud Hieronym...

Species of hummingbird Blue-headed sapphire Colombia Conservation status Least Concern (IUCN 3.1)[1] CITES Appendix II (CITES)[2] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Clade: Strisores Order: Apodiformes Family: Trochilidae Genus: Chrysuronia Species: C. grayi Binomial name Chrysuronia grayi(Delattre & Bourcier, 1846) Synonyms Hylocharis grayi[3] Gray's hummingbird Amazilia grayi[4] The blu...

Yesus menyembuhkan orang buta di pintu gerbang. Peristiwa ini terdapat pada Injil Matius 9, Injil Markus 8 Misio Dei diartikan secara literer sebagai misi Allah.[1] Kata missio dei berasal dari bahasa Latin, missio adalah misi atau tugas, dan dei adalah tuhan atau Allah.[2] Sebuah bentuk yang digunakan dalam teologi Trinitarian.[1] Misi Allah di dunia adalah maksud Allah untuk menyelamatkan dunia dalam hubungan khusus dalam Allah, Yesus dan Roh Kudus.[1] Allah ...

American television drama series (2012–2013) This article is about the BBC America series. For the Canadian series produced under the title Copper, see Rookie Blue. CopperGenrePeriod dramaCreated byTom FontanaWill RokosStarringTom Weston-JonesKyle SchmidAnastasia GriffithFranka PotenteAto EssandohKevin RyanComposerBrian KeaneCountry of originUnited StatesOriginal languageEnglishNo. of seasons2No. of episodes23 (list of episodes)ProductionExecutive producersBarry LevinsonTom FontanaProducers...

County in Texas, United States County in TexasSomervell CountyCountyThe Somervell County Courthouse in Glen RoseLocation within the U.S. state of TexasTexas's location within the U.S.Coordinates: 32°13′N 97°46′W / 32.22°N 97.77°W / 32.22; -97.77Country United StatesState TexasFounded1875Named forAlexander SomervellSeatGlen RoseLargest cityGlen RoseArea • Total192 sq mi (500 km2) • Land186 sq mi (480...

Lyon 2010–11 football seasonLyon2010–11 seasonOwnerOL GroupeChairmanJean-Michel AulasManagerClaude PuelGroundStade de GerlandLigue 13rdChampions LeagueRound of 16Coupe de la LigueRound of 16Coupe de FranceRound of 32Top goalscorerLeague: Lisandro López (17)All: Lisandro López (19)Highest home attendance39,548 (25 September vs Marseille, Ligue 1)Lowest home attendance26,587 (27 October vs Paris SG, Coupe de la Ligue) Home colours Away colours Third colours ← 2009–102011–12...

UU Antihomoseksualitas 2014Parlemen UgandaUndang-undang untuk melarang segala bentuk hubungan seksual antara orang yang berjenis kelamin sama; melarang promosi atau pengakuan hubungan semacam itu dan untuk menyediakan hal-hal terkait lainnya.KutipanUndang-Undang Antihomoseksualitas 2014Jangkauan teritorialSeluruh UgandaDiterapkan olehParlemen UgandaTanggal pengesahan20 December 2013 (tidak sah)Tanggal penandatanganan24 Februari 2014 (tidak sah)Ditandatangani olehYoweri MuseveniTanggal pengumu...

Indian politician Rajeshwara PatelMember of Parliament, Lok SabhaIn office1952–1967Succeeded byValmiki ChoudharyConstituencyHajipur, Bihar Personal detailsBorn(1911-07-05)5 July 1911Hajipur, Bihar, British IndiaPolitical partyIndian National CongressSource: [1] Rajeshwara Patel (born 5 July 1911, date of death unknown) was an Indian politician. He was elected to the Lok Sabha, the lower house of the Parliament of India from the Hajipur in Bihar as a member of the Indian National Congress.&#...

Komando Distrik Militer 0620/Kabupaten CirebonLambang Korem 063/Sunan Gunung JatiAktif11 Oktober 1978NegaraIndonesiaCabangTNI Angkatan DaratTipe unitKomando distrik militerBagian dariTentara Nasional IndonesiaMarkasKabupaten Cirebon, Jawa BaratBaret H I J A U Situs webwww.kodim0620-kabcbn.comTokohDandimLetnan Kolonel Infanteri Afriandy Bayu Laksono, S.Sos., M.I.Pol.KasdimMayor Infanteri R. Nurbiantoro Markas Kodim 0620 Komando Distrik Militer 0620/Kabupaten Cirebon atau Kodim 0620/K...

Mikoyan-Gurevich MiG-15MiG-15 kursi tunggal di Poznan, Polandia, 6 Juni 2008TipeTempurTerbang perdana30 Desember 1947Diperkenalkan1949StatusLatih opersionalPengguna utamaAngkatan Udara Uni SovietPengguna lainAngkatan Udara Tentara Pembebasan RakyatAngkatan Udara Korea UtaraTNI-AU41 lainnyaJumlah produksi~12,000VarianMiG-17 Mikoyan-Gurevich MiG-15 (bahasa Rusia: Микоян и Гуревич МиГ-15) (kode NATO Fagot) adalah pesawat tempur jet yang dikembangkan untuk Uni Soviet oleh Art...

US Space Force function Space Rapid Capabilities OfficeSpRCO insigniaOffice overviewFormedDecember 14, 2018 (2018-12-14)HeadquartersKirtland Air Force Base,New MexicoMottoEgo sum ille qui pulsatI am the one who knocksOffice executivesKelly D. Hammett[1], DirectorRobert D. Eidsmoe, Deputy Director[2]Parent departmentUnited States Space ForceWebsitekirtland.af.mil/Units/Space-Rapid-Capabilities-Office/ The Space Rapid Capabilities Office (Space RCO or SpRCO) is a ...

County in Massachusetts, United States County in MassachusettsPlymouth CountyCountyFirst Church Site marker, Men of Kent Cemetery, Meetinghouse Lane, Scituate, Massachusetts SealLocation within the U.S. state of MassachusettsMassachusetts's location within the U.S.Coordinates: 41°58′44″N 70°49′08″W / 41.978878°N 70.818954°W / 41.978878; -70.818954Country United StatesState MassachusettsFounded2 June 1685SeatPlymouth and BrocktonLargest cityBrockto...

Stanislav Horuna Nazionalità  Ucraina Karate Specialità Kumite Società Union Karate Club Armed Forces Sports Society Carriera Nazionale Ucraina Palmarès Competizione Ori Argenti Bronzi Giochi olimpici 0 0 1 Mondiali 0 0 1 Giochi mondiali 1 1 0 Giochi europei 1 0 0 Europei 1 2 5 Per maggiori dettagli vedi qui Statistiche aggiornate al 24 agosto 2021 Modifica dati su Wikidata · Manuale Stanislav Mykolayovych Horuna (Leopoli, 1º marzo 1989) è un karateka ucraino, vincitore d...

Ramli Sarwi Gozali Kartowidjojo (01 November 1950 – 23 Januari 2013) adalah seorang perancang busana berkebangsaan Indonesia. Profesi ini dijalaninya sejak 1975. Busana rancangannya dikenal berbasis bahan tradisional Indonesia, seperti batik, bordir, kain songket, dan tenun ikat. Ramli meninggal setelah beberapa tahun mengidap kanker usus. Artikel bertopik biografi Indonesia ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs

2004 live album by Keller WilliamsStageLive album by Keller WilliamsReleasedJune 29, 2004RecordedMarch 11-November 15, 2003GenreRock, JamLabelSCI FidelityKeller Williams chronology Home(2003) Stage(2004) Grass(2004) Professional ratingsReview scoresSourceRatingAllmusic[1] Stage is a live compilation of Keller Williams's 2003 tour and is divided into 2 CDs. Stage Left, features songs from the west coast shows, and Stage Right containing songs from the east coast leg of the tour...

American actress This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Mabel Paige – news · newspapers · books · scholar · JSTOR (April 2019) (Learn how and when to remove this message) Mabel PaigeMabel Paige, The Idol of the South, 1899BornMabel Paige Roberts(1880-12-19)December 19, 1880New York, New York, U.S.Di...

Warner Bros. theatrical cartoon character Tweety Pie redirects here. For the cartoon, see Tweetie Pie. This article is about the Warner Bros. fictional character. For other uses, see Tweety (disambiguation). Fictional character TweetyLooney Tunes/Merrie Melodies characterTweety in the Friz Freleng design. This is also his current appearance.First appearanceA Tale of Two Kitties (November 21, 1942; 81 years ago (1942-11-21)) (as Orson) Birdy and the Beast (August 19, 194...