Namespaces
Variants
Actions

Difference between revisions of "Hypergraph"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A generalization of the concept of a [[Graph|graph]]. A hypergraph is defined by a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484701.png" />, whose elements are known as vertices, and by a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484702.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484703.png" />, known as edges or hyperedges. A hypergraph is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484704.png" />. The concept of a hypergraph is a variant of the familiar concepts of a [[Complex|complex]], a [[Block design|block design]] and a [[Network|network]].
+
<!--
 +
h0484701.png
 +
$#A+1 = 46 n = 0
 +
$#C+1 = 46 : ~/encyclopedia/old_files/data/H048/H.0408470 Hypergraph
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
Two vertices of a hypergraph are said to be adjacent if there exists an edge containing these vertices. A vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484705.png" /> and an edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484706.png" /> of a hypergraph are said to be incident if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484707.png" />. A hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484708.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h0484709.png" /> vertices and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847010.png" /> edges may be defined by an incidence matrix, i.e. by the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847011.png" /> of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847012.png" /> in which the columns correspond to the edges while the rows correspond to the vertices of the hypergraph, and where
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847013.png" /></td> </tr></table>
+
A generalization of the concept of a [[Graph|graph]]. A hypergraph is defined by a set  $  V $,
 +
whose elements are known as vertices, and by a family  $  {\mathcal E} $
 +
of subsets of  $  V $,
 +
known as edges or hyperedges. A hypergraph is denoted by  $  ( V, {\mathcal E} ) $.
 +
The concept of a hypergraph is a variant of the familiar concepts of a [[Complex|complex]], a [[Block design|block design]] and a [[Network|network]].
  
It is possible to assign to each matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847014.png" /> consisting of zeros and ones a hypergraph for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847015.png" /> is the incidence matrix. The hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847016.png" /> is called the dual of the hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847017.png" /> if the incidence matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847018.png" /> is obtained by transposing the incidence matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847019.png" />. The number of edges of a hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847020.png" /> that are incident to a given vertex is called the degree of the vertex. The degree of an edge is the number of vertices of the hypergraph incident to this edge. A hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847021.png" /> is called a subhypergraph of a hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847022.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847024.png" />, and if a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847025.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847026.png" /> and an edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847027.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847028.png" /> are incident in the hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847029.png" /> if and only if they are incident in the hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847030.png" />.
+
Two vertices of a hypergraph are said to be adjacent if there exists an edge containing these vertices. A vertex  $  v $
 +
and an edge  $  E $
 +
of a hypergraph are said to be incident if  $  v \in E $.  
 +
A hypergraph $  H $
 +
with  $  n $
 +
vertices and  $  m $
 +
edges may be defined by an incidence matrix, i.e. by the matrix $  \| a _ {ij} \| $
 +
of dimension  $  n \times m $
 +
in which the columns correspond to the edges while the rows correspond to the vertices of the hypergraph, and where
  
A hypergraph may be represented in a plane by identifying the vertices of the hypergraph with points of the plane and by identifying the edges with connected domains containing the vertices incident with these edges. For instance, it is possible to represent the hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847031.png" /> with set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847032.png" /> and family of edges
+
$$
 +
a _ {ij}  = \
 +
\left \{
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847033.png" /></td> </tr></table>
+
\begin{array}{ll}
 +
1  &\textrm{ if }  v _ {i} \in E _ {j} ,  \\
 +
0  &\textrm{ if }  v _ {i} \notin E _ {j} ,  \\
 +
\end{array}
 +
\ \
 +
i = 1 \dots n; \  j = 1 \dots m.
 +
\right .$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847034.png" /></td> </tr></table>
+
It is possible to assign to each matrix  $  M $
 +
consisting of zeros and ones a hypergraph for which  $  M $
 +
is the incidence matrix. The hypergraph  $  H  ^ {*} $
 +
is called the dual of the hypergraph  $  H $
 +
if the incidence matrix of  $  H  ^ {*} $
 +
is obtained by transposing the incidence matrix of  $  H $.
 +
The number of edges of a hypergraph  $  H $
 +
that are incident to a given vertex is called the degree of the vertex. The degree of an edge is the number of vertices of the hypergraph incident to this edge. A hypergraph  $  ( V ^ { \prime } , {\mathcal E} ^ { \prime } ) $
 +
is called a subhypergraph of a hypergraph  $  ( V, {\mathcal E} ) $
 +
if  $  V ^ { \prime } \subseteq V $,
 +
$  {\mathcal E} ^ { \prime } \subseteq {\mathcal E} $,
 +
and if a vertex  $  v $
 +
from  $  V ^ { \prime } $
 +
and an edge  $  E $
 +
from  $  {\mathcal E} ^ { \prime } $
 +
are incident in the hypergraph  $  ( V ^ { \prime } , {\mathcal E} ^ { \prime } ) $
 +
if and only if they are incident in the hypergraph  $  ( V, {\mathcal E} ) $.
 +
 
 +
A hypergraph may be represented in a plane by identifying the vertices of the hypergraph with points of the plane and by identifying the edges with connected domains containing the vertices incident with these edges. For instance, it is possible to represent the hypergraph  $  H $
 +
with set of vertices  $  V = \{ v _ {1} \dots v _ {6} \} $
 +
and family of edges
 +
 
 +
$$
 +
{\mathcal E}  = \{ E _ {1} = \{ v _ {1} \} ,\
 +
E _ {2} = \{ v _ {1} , v _ {3} \} ,\
 +
E _ {3} = \{ v _ {1} , v _ {2} , v _ {3} \} ,
 +
$$
 +
 
 +
$$
 +
{} E _ {4} = E _ {5} = \{ v _ {2} , v _ {4} \} ,\
 +
E _ {6} = \{ v _ {3} , v _ {4} ,
 +
v _ {5} \} , E _ {7} = \emptyset \}
 +
$$
  
 
in a plane, as shown in the figure.
 
in a plane, as shown in the figure.
Line 19: Line 79:
 
Figure: h048470a
 
Figure: h048470a
  
A hypergraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847035.png" /> may be represented by a bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847036.png" /> in which the vertices of one part <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847037.png" /> correspond to the vertices of the hypergraph, while the vertices of the other part <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847038.png" /> correspond to the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847039.png" />. Two vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847040.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847042.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847043.png" /> will be connected by an edge in the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847044.png" /> if the vertex of the hypergraph corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847045.png" /> is incident to the edge of the hypergraph corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h048/h048470/h04847046.png" />. A hypergraph is a graph if each of its edges has degree two. An important special case of the concept of a  "hypergraph"  is that of a [[Matroid|matroid]]. Many concepts in the theory of graphs, such as connectedness, planarity, the chromatic number, and the external and internal stability numbers, may be applied to hypergraphs, as may many theorems that are applicable to graphs.
+
A hypergraph $  H $
 +
may be represented by a bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]) $  K( H) $
 +
in which the vertices of one part $  U _ {1} $
 +
correspond to the vertices of the hypergraph, while the vertices of the other part $  U _ {2} $
 +
correspond to the edges of $  H $.  
 +
Two vertices $  u  ^  \prime  $
 +
from $  U _ {1} $
 +
and $  u  ^ {\prime\prime} $
 +
from $  U _ {2} $
 +
will be connected by an edge in the graph $  K( H) $
 +
if the vertex of the hypergraph corresponding to $  u  ^  \prime  $
 +
is incident to the edge of the hypergraph corresponding to $  u  ^ {\prime\prime} $.  
 +
A hypergraph is a graph if each of its edges has degree two. An important special case of the concept of a  "hypergraph"  is that of a [[Matroid|matroid]]. Many concepts in the theory of graphs, such as connectedness, planarity, the chromatic number, and the external and internal stability numbers, may be applied to hypergraphs, as may many theorems that are applicable to graphs.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Zykov,  "Hypergraphs"  ''Russian Math. Surveys'' , '''29''' :  6  (1974)  pp. 89–156  ''Uspekhi Mat. Nauk'' , '''29''' :  6  (1974)  pp. 80–154</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C. Berge,  "Graphs and hypergraphs" , North-Holland  (1973)  (Translated from French)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Zykov,  "Hypergraphs"  ''Russian Math. Surveys'' , '''29''' :  6  (1974)  pp. 89–156  ''Uspekhi Mat. Nauk'' , '''29''' :  6  (1974)  pp. 80–154</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C. Berge,  "Graphs and hypergraphs" , North-Holland  (1973)  (Translated from French)</TD></TR></table>

Latest revision as of 22:11, 5 June 2020


A generalization of the concept of a graph. A hypergraph is defined by a set $ V $, whose elements are known as vertices, and by a family $ {\mathcal E} $ of subsets of $ V $, known as edges or hyperedges. A hypergraph is denoted by $ ( V, {\mathcal E} ) $. The concept of a hypergraph is a variant of the familiar concepts of a complex, a block design and a network.

Two vertices of a hypergraph are said to be adjacent if there exists an edge containing these vertices. A vertex $ v $ and an edge $ E $ of a hypergraph are said to be incident if $ v \in E $. A hypergraph $ H $ with $ n $ vertices and $ m $ edges may be defined by an incidence matrix, i.e. by the matrix $ \| a _ {ij} \| $ of dimension $ n \times m $ in which the columns correspond to the edges while the rows correspond to the vertices of the hypergraph, and where

$$ a _ {ij} = \ \left \{ \begin{array}{ll} 1 &\textrm{ if } v _ {i} \in E _ {j} , \\ 0 &\textrm{ if } v _ {i} \notin E _ {j} , \\ \end{array} \ \ i = 1 \dots n; \ j = 1 \dots m. \right .$$

It is possible to assign to each matrix $ M $ consisting of zeros and ones a hypergraph for which $ M $ is the incidence matrix. The hypergraph $ H ^ {*} $ is called the dual of the hypergraph $ H $ if the incidence matrix of $ H ^ {*} $ is obtained by transposing the incidence matrix of $ H $. The number of edges of a hypergraph $ H $ that are incident to a given vertex is called the degree of the vertex. The degree of an edge is the number of vertices of the hypergraph incident to this edge. A hypergraph $ ( V ^ { \prime } , {\mathcal E} ^ { \prime } ) $ is called a subhypergraph of a hypergraph $ ( V, {\mathcal E} ) $ if $ V ^ { \prime } \subseteq V $, $ {\mathcal E} ^ { \prime } \subseteq {\mathcal E} $, and if a vertex $ v $ from $ V ^ { \prime } $ and an edge $ E $ from $ {\mathcal E} ^ { \prime } $ are incident in the hypergraph $ ( V ^ { \prime } , {\mathcal E} ^ { \prime } ) $ if and only if they are incident in the hypergraph $ ( V, {\mathcal E} ) $.

A hypergraph may be represented in a plane by identifying the vertices of the hypergraph with points of the plane and by identifying the edges with connected domains containing the vertices incident with these edges. For instance, it is possible to represent the hypergraph $ H $ with set of vertices $ V = \{ v _ {1} \dots v _ {6} \} $ and family of edges

$$ {\mathcal E} = \{ E _ {1} = \{ v _ {1} \} ,\ E _ {2} = \{ v _ {1} , v _ {3} \} ,\ E _ {3} = \{ v _ {1} , v _ {2} , v _ {3} \} , $$

$$ {} E _ {4} = E _ {5} = \{ v _ {2} , v _ {4} \} ,\ E _ {6} = \{ v _ {3} , v _ {4} , v _ {5} \} , E _ {7} = \emptyset \} $$

in a plane, as shown in the figure.

Figure: h048470a

A hypergraph $ H $ may be represented by a bipartite graph (cf. Graph, bipartite) $ K( H) $ in which the vertices of one part $ U _ {1} $ correspond to the vertices of the hypergraph, while the vertices of the other part $ U _ {2} $ correspond to the edges of $ H $. Two vertices $ u ^ \prime $ from $ U _ {1} $ and $ u ^ {\prime\prime} $ from $ U _ {2} $ will be connected by an edge in the graph $ K( H) $ if the vertex of the hypergraph corresponding to $ u ^ \prime $ is incident to the edge of the hypergraph corresponding to $ u ^ {\prime\prime} $. A hypergraph is a graph if each of its edges has degree two. An important special case of the concept of a "hypergraph" is that of a matroid. Many concepts in the theory of graphs, such as connectedness, planarity, the chromatic number, and the external and internal stability numbers, may be applied to hypergraphs, as may many theorems that are applicable to graphs.

References

[1] A.A. Zykov, "Hypergraphs" Russian Math. Surveys , 29 : 6 (1974) pp. 89–156 Uspekhi Mat. Nauk , 29 : 6 (1974) pp. 80–154
[2] C. Berge, "Graphs and hypergraphs" , North-Holland (1973) (Translated from French)
How to Cite This Entry:
Hypergraph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hypergraph&oldid=47300
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article