Editing Hypergraph (section)

{{Short description|Generalization of graph theory}}
[[File:Hypergraph-wikipedia.svg|frame|An example of an undirected hypergraph, with
<math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math> and
<math>E = \{e_1,e_2,e_3,e_4\} = </math>
<math>\{\{v_1, v_2, v_3\},</math>
<math>\{v_2,v_3\},</math>
<math>\{v_3,v_5,v_6\},</math>
<math>\{v_4\}\}</math>.
This hypergraph has order 7 and size 4. Here, edges do not just connect two vertices but several, and are represented by colors.]]
[[File:PAOH hypergraph representation.png|alt=PAOH visualization of a hypergraph|thumb|Alternative representation of the hypergraph reported in the figure above, called PAOH.<ref name="paoh">{{Cite journal|last1=Valdivia|first1=Paola|last2=Buono|first2=Paolo|last3=Plaisant|first3=Catherine|last4=Dufournaud|first4=Nicole|last5=Fekete|first5=Jean-Daniel|date=2020|title=Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization|journal=IEEE Transactions on Visualization and Computer Graphics|publisher=IEEE|volume=26|issue=1|pages=12|doi=10.1109/TVCG.2019.2933196|pmid=31398121|s2cid=199518871|issn=1077-2626|url=https://hal.inria.fr/hal-02264960/file/Paohvis.pdf|eissn=1941-0506|access-date=2020-09-08|archive-date=2021-01-26|archive-url=https://web.archive.org/web/20210126021713/https://hal.inria.fr/hal-02264960/file/Paohvis.pdf|url-status=live}}</ref> 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.]]
[[File:Directed hypergraph example.svg|thumb|An example of a directed hypergraph, with
<math>X = \{1, 2, 3, 4, 5, 6\}</math> and
<math>E = \{a_1, a_2, a_3, a_4, a_5\} = </math>
<math>\{(\{1\}, \{2\}),</math>
<math>(\{2\}, \{3\}),</math>
<math>(\{3\}, \{1\}),</math>
<math>(\{2, 3\}, \{4, 5\}),</math>
<math>(\{3, 5\}, \{6\})\}</math>.
]]
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 '''directed hypergraph''' is a pair <math>(X,E)</math>, where <math>X</math> is a set of elements called ''nodes'', ''vertices'', ''points'', or ''elements'' and <math>E</math> is a set of pairs of subsets of <math>X</math>. Each of these pairs <math>(D,C)\in E</math> is called an ''edge'' or ''[[hyperedge]]'';  the vertex subset <math>D</math> is known as its ''tail'' or ''domain'', and  <math>C</math> as its  ''head'' or ''[[codomain]]''.

The '''order of a hypergraph''' <math>(X,E)</math> is the number of vertices in <math>X</math>. The '''size of the hypergraph''' is the number of edges in <math>E</math>. The '''order of an edge''' <math>e=(D,C)</math> in a directed hypergraph is <math>|e| = (|D|,|C|)</math>: 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 (<math>C\subseteq X</math> or <math>D\subseteq X</math>) 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 <math>|e|</math> will generalize to hypergraph theory.

An '''undirected hypergraph''' <math>(X, E)</math> is an undirected graph whose edges connect not just two vertices, but an arbitrary number.<ref>{{cite arXiv |mode=cs2
 | last1 = Ouvrard | first1 = Xavier | author1-link = Xavier Ouvrard
 | eprint=2002.05014
 | title = Hypergraphs: an introduction and review
 | year = 2020
 | class = cs.DM }}.</ref> 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 structure]]s.  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''.<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|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>{{cite book |first=Judea |last=Pearl |title=Heuristics: Intelligent Search Strategies for Computer Problem Solving |url=https://books.google.com/books?id=0XtQAAAAMAAJ |year=1984 |publisher=Addison-Wesley Publishing Company |isbn=978-0-201-05594-8 |page=25 |access-date=2021-06-12 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204155707/https://books.google.com/books?id=0XtQAAAAMAAJ |url-status=live }}</ref>

The collection of hypergraphs is a [[Category (mathematics)|category]] with hypergraph [[homomorphism]]s as [[morphism]]s.