|
|
|
Viewing Version
12
of
'hypergraph'
|
[ view 'hypergraph'
|
back to history
]
| Title of object: |
hypergraph |
| Canonical Name: |
Hypergraph |
| Type: |
Definition |
| Created on: |
2002-10-07 03:46:10 |
| Modified on: |
2006-10-23 12:19:50 |
| Classification: |
msc:05C65 |
| Defines: |
regular, uniform, degree, incidence matrix, edge, vertex |
Revision comment (for changes between this and next version):
| Changes for correction #11057 ('linking policy'). |
Preamble:
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{bbm}
\newcommand{\Z}{\mathbbmss{Z}}
\newcommand{\C}{\mathbbmss{C}}
\newcommand{\R}{\mathbbmss{R}}
\newcommand{\Q}{\mathbbmss{Q}}
\newcommand{\mathbb}[1]{\mathbbmss{#1}}
\newcommand{\figura}[1]{\begin{center}\includegraphics{#1}\end{center}}
\newcommand{\figuraex}[2]{\begin{center}\includegraphics[#2]{#1}\end{center}} |
Content:
A \emph{hypergraph} $\mathcal{H}$ is an ordered pair $(V, \mathcal{E})$ where $V$ is a set of \emph{vertices} and $\mathcal{E}$ is a set of edges such that $\mathcal{E} \subseteq \mathcal{P}(V)$. In other words, an \emph{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 $V \not= \emptyset$. 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 $V$ to be infinite.
Many of the definitions of graphs carry verbatim to hypergraphs. $\mathcal{H}$ is said to be $k$-\emph{uniform} if every edge $e \in \mathcal{E}$ has cardinality $k$. The \emph{degree} of a vertex $v$ is the number of edges in $\mathcal{E}$ that contain this vertex, often denoted $d(v)$. $H$ is $k$-\emph{regular} if every vertex has degree $k$. Notice that an ordinary graph is merely a $2-$uniform hypergraph.
Let $V = \{v_1, v_2, ~\ldots, ~ v_n\}$ and $\mathcal{E} = \{e_1, e_2, ~ \ldots, ~ e_m\}$. Associated to any hypergraph is the $n \times m$ \emph{incidence matrix} $A = (a_{ij})$ where
\[a_{ij} =
\begin{cases}
1 &\text{ if } ~ v_i \in e_j \\
0 &\text{ otherwise }
\end{cases}\]
The transpose $A^t$ of the incidence matrix also defines a hypergraph $\mathcal{H}^*$, the \emph{dual} of $\mathcal{H}$, in an obvious manner. To be explicit, let $\mathcal{H}^* = (V^*, \mathcal{E}^*)$ where $V^*$ is an $m-$element set and $\mathcal{E}^*$ is an $n-$element set of subsets of $V^*$. For $v^*_j \in V^*$ and $e^*_i \in \mathcal{E}^*, ~ v^*_j \in e^*_i$ if and only if $a_{ij} = 1$.
Notice, of course, 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. |
|
|
|
|
|
