Metraipolis › archive › dc_7628385c30ff

Hypergraph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Hypergraph
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T18:29:16.760Z
SHA-256 of the archived text
e3c01465a8c88495b668dcdc1e032a2b6822b733097d7d5c6c92b63ec9289612
Stable URL of this page
https://metraipolis.com/documento/dc_7628385c30ff

How to cite

Hypergraph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Hypergraph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7628385c30ff (Metraipolis archive dc_7628385c30ff, sha256 e3c01465a8c88495b668dcdc1e032a2b6822b733097d7d5c6c92b63ec9289612)
BibTeX
@misc{dc7628385c30ff,
  title = {Hypergraph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Hypergraph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7628385c30ff; sha256 e3c01465a8c88495b668dcdc1e032a2b6822b733097d7d5c6c92b63ec9289612},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Hypergraph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 ( X , E ) {\displaystyle (X,E)} , where X {\displaystyle X} is a set of elements called nodes, vertices, points, or elements and E {\displaystyle E} is a set of pairs of subsets of X {\displaystyle X} . Each of these pairs ( D , C ) ∈ E {\displaystyle (D,C)\in E} is called an edge or hyperedge; the vertex subset D {\displaystyle D} is known as its tail or domain, and C {\displaystyle C} as its head or codomain. The order of a hypergraph ( X , E ) {\displaystyle (X,E)} is the number of vertices in X {\displaystyle X} . The size of the hypergraph is the number of edges in E {\displaystyle E} . The order of an edge e = ( D , C ) {\displaystyle e=(D,C)} in a directed hypergraph is | e | = ( | D | , | C | ) {\displaystyle |e|=(|D|,|C|)} : 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 ( C ⊆ X {\displaystyle C\subseteq X} or D ⊆ X {\displaystyle D\subseteq X} ) 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 | e | {\displaystyle |e|} will generalize to hypergraph theory. Given a set X {\displaystyle {X}} with its power set P ( X ) {\displaystyle {{\mathcal {P}}\left(X\right)}} , furthermore a set E {\displaystyle {E}} with E ⊆ P ( X ) {\displaystyle {E\subseteq {\mathcal {P}}\left(X\right)}} , the pair ( X , E ) {\displaystyle {\left(X,E\right)}} shall be called an undirected hypergraph. 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. 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. The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Hypergraph» — https://en.wikipedia.org/wiki/Hypergraph
Wikidata Q840247: «generalized undirected graph in which generalized edges connect one, two, or more nodes» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q840247
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Hypergraph?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1373724538, consultata il 2026-10-07T17:57:30.286Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d7b1eecc409dcf965a41f281875009b7c66e215b5567c19f3b60b7703be95010