|
|
|
|
|
A hypergraph
 is an ordered pair
 where  is a set of vertices and
 is a set of edges such that
 . In other words, an edge is nothing more than a set of vertices. A hypergraph is the same thing as a simple incidence structure, but with terminology that focuses on the relationship with graphs.
Sometimes it is desirable to restrict this definition more. The empty hypergraph is not very interesting, so we usually accept that
 . Singleton edges are allowed in general, but not the empty one. Most applications consider only finite hypergraphs, but occasionally it is also useful to allow  to be infinite.
Many of the definitions of graphs carry verbatim to hypergraphs.
 is said to be  -uniform if every edge
 has cardinality  . The degree of a vertex  is the number of edges in
 that contain this vertex, often denoted  .  is  -regular if every vertex has degree  . Notice that an ordinary graph is merely a  uniform hypergraph.
Let
 and
 . Associated to any hypergraph is the
 incidence matrix
 where
For example, let
 , where
 and
 . Defining  and  in the obvious manner (as they are listed in the sets), we have
Notice that the sum of the entries in any column is the cardinality of the corresponding edge. Similarly, the sum of the entries in a particular row is the degree of the corresponding vertex.
The transpose  of the incidence matrix also defines a hypergraph
 , the dual of
 , in an obvious manner. To be explicit, let
 where  is an  -element set and
 is an  -element set of subsets of  . For
 and
 if and only if
 .
Continuing from the example above, the dual
 of
 consists of
 and
 , where  and  are defined in the obvious manner.
By the remark immediately after the definition of the incidence matrix of a hypergraph, it is easy to see that the dual of a uniform hypergraph is regular and vice-versa. It is not rare to see fruitful results emerge by considering the dual of a hypergraph.
|
"hypergraph" is owned by CWoo. [ full author list (6) | owner history (6) ]
|
|
(view preamble)
Cross-references: subsets, transpose, row, column, sum, obvious, regular, contain, number, vertex, degree, cardinality, definitions, infinite, finite, singleton, graphs, incidence structure, simple, edges, vertices, ordered pair
There are 6 references to this entry.
This is version 14 of hypergraph, born on 2002-10-07, modified 2007-08-17.
Object id is 3508, canonical name is Hypergraph.
Accessed 20008 times total.
Classification:
| AMS MSC: | 05C65 (Combinatorics :: Graph theory :: Hypergraphs) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
