Bretto 2013

Chapter 7
Applications of Hypergraph Theory: A Brief

Overview
ike in most fruitful mathematical theories, the theory of hypergraphs has many
L applications. Hypergraphs model many practical problems in many different
sciences. it makes very little time (20 years) that the theory of hypergraphs is used to
model situations in the applied sciences. We find this theory in psychology, genetics,
. . . but also in various human activities. Hypergraphs have shown their power as a
tool to understand problems in a wide variety of scientific field.
Moreover it well known now that hypergraph theory is a very useful tool to resolve
optimization problems such as scheduling problems, location problems and so on.
This chapter shows some possible uses of hypergraphs in Applied Sciences.
7.1 Hypergraph Theory and System Modeling

for Engineering
Modeling is a particularly important aspect in apprehending the continuous or dis-

crete physical systems. The mathematical foundations of the modeling come from:
• Algebraic theory
• The concepts of duality
• Complex and real analysis
• And many others
Since combinatorics is the common denominator of these mathematical areas,
combinatorial paradigms are suited to express the mathematical properties of physi-
cal objects. Thus, it is natural to develop the hypergraph theory as a modeling concept.
In this section, we are going to briefly present some applications of hypergraphs in
science and engineering. It turns out that hypergraph theory can be used in many
areas of sciences. We does not claim to be exhaustive. We limit ourselves to present
some aspects of the application of hypergraphs in order to prove the relevance of this
theory in science and engineering.
A. Bretto, Hypergraph Theory, Mathematical Engineering, 111

DOI: 10.1007/978-3-319-00080-0_7,
© Springer International Publishing Switzerland 2013
112 7 Applications of Hypergraph Theory: A Brief Overview
7.1.1 Chemical Hypergraph Theory
The graph theory is very useful in chemistry. The representation of molecular struc-
tures by graphs is widely used in computational chemistry. But the main drawback
of the graph theory is the lack of convenient tools to represent organometallic com-
pounds, benzenoid systems and so on.
A hypergraph H = (V, E) is a molecular hypergraph if it represents molecular
structure, where x ∈ V corresponds to an individual atom, hyperedges with degrees
greater than 2 correspond to polycentric bonds and hyperedges with deg(x) = 2
correspond to simple covalent bonds.
Hypergraphs appear to be more convenient to describe some chemical structures.
Hence the concept of molecular hypergraph may be seen as a generalization of the
concept of molecular graph. More informations can be found in [KS01] . Hypergraphs
have also shown their interest in biology [KHT09].
7.1.2 Hypergraph Theory for Telecomunmications
A hypergraph theory can be used to model cellular mobile communication systems.

A cellular system is a set of cells where two cells can use the same channel if the
distance between them is at least some predefined value D. This situation can be
represented by a graph where:
(a) Each vertex represents a cell.
(b) An edge exists between two vertices if and only if the distance between the
corresponding cells is less than the distance called reuse distance and denoted
by D.
A forbidden set is a group of cells all of which cannot use a channel simultane-
ously.
A minimal forbidden set is a forbidden set which is minimal with respect to this
property, i.e. no proper subset of a minimal forbidden set is forbidden.
From these definitions it is possible to derive a better modelization using hypergraphs.
We proceed in the following way:
(a) Each vertex represents a cell.
(b) A hyperedge is minimal forbidden set.
7.1.3 Hypergraph Theory and Parallel Data Structures
Hypergraphs provide an effective mean of modeling parallel data structures. A shared

memory multiprocessor system consists of a number of processors and memory
modules. We define a template as a set of data elements that need to be processed
7.1 Hypergraph Theory and System Modeling for Engineering 113
in parallel. Hence the data elements from a template should be stored in different
memory modules. So we define a hypergraph in the following way:
(a) A data is represented by a vertex.
(b) The hyperedges are the templates.
From this model and by using the properties of hypergraphs one can resolve various
problems such as the conflict-free access to data in parallel memory systems. Some
informations can be found in [HK00] .
7.1.4 Hypergraphs and Constraint Satisfaction Problems
A constraint satisfaction problem, P is defined as a tuple:
P = (V, D, R1 (S1 ), . . . , Rk (Sk ))
where:
• V is a finite set of variables.
• D is a finite set of values which is called the domain of P.
• Each Ri (Si ) is a constraint.
– Si is an ordered list of n i variables, called the constraint scope.
– Ri is a relation over D of arity n i , called the constraint relation.
To a constraint satisfaction problem one can associate a hypergraph in the following
way:
(a) The vertices of the hypergraph are the variables of the problem.
(b) There is a hyperedge containing the vertices v1 , v2 , . . . , vt when there is some
constraint Ri (Si ) with scope Si = {v1 , v2 , . . . vt }.
7.1.5 Hypergraphs and Database Schemes
Hypergraphs have been introduced in database theory in order to model relational

database schemes [Fag83]. The classes of acyclic hypergraphs defined in Sect. 4.5.0.3
play an important part in the modeling of relational database schemes.
A database can be viewed in the following way:
• A set of attributes.
• A set of relations between these attributes.
Hence we have the following hypergraph:
(a) The set of vertices is the set of attributes.
(b) The set of hyperedges is the set of relations between these attributes.
We also find the theory of hypergraphs in data mining [HBC07] .
7.1.6 Hypergraphs and Image Processing
A digital image on a grid (4-connected grid, 8-connected grid, . . .) is a two-

dimensional discrete function that has been digitized both in spatial coordinates
and in feature value. We may represent a digital image by an application
I : X ⊆ Zm → C ⊆ Zn,
with n ≥ 1, m = 2 and we have a 2-dimensional image or m = 3 and we have

a 3-dimensional image and where C is the set of the feature intensity levels and X
represent a set of points called the image points. The couple (x, I (x)) is called a
pixel.
Let d be a distance on C, for given β there exists a neighborhood relation on an image
I defined by:

∀x ∈ X, Γα, β (x) = x ∈ X, x = x | d(I(x), I(x )) < α and d (x, x ) ≤ β
where d is the distance on the grid and α is attribute on the image. The neighborhood
of x on the grid is denoted by Γβ (x). So each image can be associated to a hypergraph:

Hα, β = X, ({x} ∪ Γα, β (x))x∈X .
The attribute α can be computed in an adaptive way depending on local properties

of the image.
• If α is constant, the hypergraph is called the Image Neighborhood Hypergraph
(INH).
• If α is not constant, for instance α may be estimated by the standard deviation of
the intensity levels of the pixels of {x} ∪ Γβ (x), the hypergraph is called the Image
Adaptative Neighborhood Hypergraph (IANH).
From this hypergraph we may developp some applications:
• we can do image segmentation,
• we use also Image (Adaptative) Neighborhood Hypergraph for the edge detection
• and thanks to our model we developed a noise cancellation algorithm.
Some others applications such as data compression can be also developed from our
hypergraph model.
More informations can be found in [BG05, DBRL12] .
7.1 Hypergraph Theory and System Modeling for Engineering 115
Algorithm 10: Image Adaptive Neighborhood Hypergraph.

Data: Image I , and neighborhood order β.
Result: hypergraph Hα,β
begin
X := ∅ ;
foreach For each pixel (x, I (x)) of I do
α = the standard deviation of the intensity levels of the pixels in
{x} ∪ Γβ (x);
Γα,β (x) = ∅;
foreach y of Γβ (x), do
if d(I (x), I (y)) ≤ α then
Γα,β (x) = Γα,β (x) ∪ {y};
end
end
X = X ∪ {x}; E α,β (x) = {Γα,β (x) ∪ {x}};
end
Hα,β = (X, (E α,β (x))x∈X );
end
7.1.7 Other Applications
Hypergraph theory can lead to numerous other applications [HK00, HOS12, Rob39,
STV04, Smo07, Zyk74]. Indeed we can find hypergraph models in machine learning,
data mining, and so on [BP09, STV04, Sla78, Smo07, Rob39].
The properties of hypergraphs are equally important, for example hypergraph
transversal computation has a large number of applications in many areas of com-
puter science, such as distribued systems, databases, artificial intelligence, and so
on. Hypergraph partitioning is also a very interesting property [BP09, HK00]. The
partitioning of a hypergraph can be defined as follows:
(a) The set of vertices is partioned into k disjoint subsets V1 , V2 , . . . , Vk .
(b) The partial subhypergraphs (or the set of hyperedges) generated by V1 , V2 , . . . , Vk
verify the properties P1 , P2 , . . . , Pk .
This property yields interesting results in many areas such as VLSI design, data
mining, and so on.
Directed hypergraphs can be very useful in many areas of sciences. Indeed directed
hypergraphs are used as models in:
• Formal languages.
• Relational data bases.
• Scheduling.
and many other applications. Numerous computational studies using hypergraphs
have shown the importance of this field in many areas of science [Gol11, BP09,
Bre04, HOS12, Hua08] , and other fruitful applications should be developed in the
future.
LOGOS

References
[KS01] E.V. Konstantinova, V.A. Skorobogatov, Application of hypergraph theory in chemistry.

Discret. Math. 235(1–3), 365–383 (2001)
[KHT09] S. Klamt, U.U. Haus, F.J. Theis, Hypergraphs and cellular networks. PLoS Comput. Biol.
5(5), e1000385 (2009)
[HK00] B. Hendrickson, T.G. Kolda, Graph partitioning models for parallel computing. Parallel
Comput. 26, 1519–1545 (2000)
[Fag83] R. Fagin, Degrees of acyclicity for hypergraphs and relational database systems.
J. Assoc. Comput. Mach. 30, 514–550 (1983)
[HBC07] C. Hébert, A. Bretto, B. Crémilleux, A data mining formalization to improve hypergraph
minimal transversal computation. Fundamenta Informaticae 80(4), 415–433 (2007)
[BG05] A. Bretto and L. Gillibert. Hypergraph-based Image Representation, in GbRPR of Lecture
Notes in Computer Science, vol. 3434 (Springer, 2005), pp. 1–11
[DBRL12] A. Ducournau, A. Bretto, S. Rital, B. Laget, A reductive approach to hypergraph clus-
tering: An application to image segmentation. Pattern Recogn. 45(7), 2788–2803 (2012)
[HOS12] Marc Hellmuth, Lydia Ostermeier, Peter F. Stadler, A survey on hypergraph products.
Math. Comput. Sci. 6(1), 1–32 (2012)
[Rob39] H.E. Robbins, A theorem on graphs with an application to a problem of traffic control.
Am. Math. Mon. 46, 281–283 (1939)
[STV04] B. SchÃülkopf, K. Tsuda, J.P. Vert, Kernel Methods in Computational Biology. (MIT
Press, 2004)
[Smo07] S. Smorodinsky, On the chromatic number of geometric hypergraphs. SIAM J. Discret.
Math. 21(3), 676–687 (2007)
[Zyk74] A.A. Zykov, Hypergraphs. Uspekhi Mat. Nauk. 29, 89–154 (1974)
[BP09] S.R. Bulò, M. Pelillo, A Game-Theoretic Approach to Hypergraph Clustering, in pro-
ceedings of the NIPS, pp. 1571–1579 (2009)
[Sla78] P.J. Slater, A characterization of soft hypergraphs. Can. Math. Bull. 21, 335–337 (1978)
[Gol11] O. Goldreich. Using the Fglss-Reduction to Prove Inapproximability Results for Min-
imum Vertex Cover in Hypergraphs, in Studies in Complexity and Cryptography, pp.
88–97 (2011)
[Bre04] A. Bretto, Introduction to Hypergraph Theory and their Use in Engeneering and Image
Processing. Advances in Imaging and Electron Physics (Monographic Series) (Elsevier
Academic Press, 2004)
[Hua08] L. Huang, Advanced dynamic programming in semiring and hypergraph frameworks
(2008)

Bretto 2013

Uploaded by

Copyright:

Available Formats

Bretto 2013

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Bretto 2013

Uploaded by

Copyright:

Available Formats

Chapter 7

Applications of Hypergraph Theory: A Brief

7.1 Hypergraph Theory and System Modeling

Modeling is a particularly important aspect in apprehending the continuous or dis-

A. Bretto, Hypergraph Theory, Mathematical Engineering, 111

7.1.1 Chemical Hypergraph Theory

7.1.2 Hypergraph Theory for Telecomunmications

A hypergraph theory can be used to model cellular mobile communication systems.

7.1.3 Hypergraph Theory and Parallel Data Structures

Hypergraphs provide an effective mean of modeling parallel data structures. A shared

7.1.4 Hypergraphs and Constraint Satisfaction Problems

A constraint satisfaction problem, P is defined as a tuple:

P = (V, D, R1 (S1 ), . . . , Rk (Sk ))

7.1.5 Hypergraphs and Database Schemes

Hypergraphs have been introduced in database theory in order to model relational

7.1.6 Hypergraphs and Image Processing

A digital image on a grid (4-connected grid, 8-connected grid, . . .) is a two-

with n ≥ 1, m = 2 and we have a 2-dimensional image or m = 3 and we have

The attribute α can be computed in an adaptive way depending on local properties

Algorithm 10: Image Adaptive Neighborhood Hypergraph.

7.1.7 Other Applications

[KS01] E.V. Konstantinova, V.A. Skorobogatov, Application of hypergraph theory in chemistry.

You might also like