|
|
|
Viewing Version
4
of
'hypergraph'
|
[ view 'hypergraph'
|
back to history
]
| Title of object: |
hypergraph |
| Canonical Name: |
Hypergraph |
| Type: |
Definition |
| Created on: |
2002-10-07 03:46:10.533826-04 |
| Modified on: |
2002-10-07 05:32:11.550528-04 |
| Classification: |
msc:05C65 |
| Defines: |
regular, uniform, degree, incidence matrix |
Preamble:
\documentclass{article}
\usepackage{amssymb, amsmath, amsthm, alltt, setspace}
\newtheorem{thm}{Theorem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\theoremstyle{definition}
\newtheorem*{rem}{Remark}
\theoremstyle{definition}
\newtheorem*{nott}{Notation}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem*{eg}{Example}
\newtheorem*{ex}{Exercise}
\newtheorem*{prop}{Proposition}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\leftbb}{[ \! [}
\newcommand{\rightbb}{] \! ]}
\newcommand{\bt}{\begin{thm}}
\newcommand{\et}{\end{thm}}
\newcommand{\Rel}{\mathbf{R}}
\newcommand{\er}{\thicksim}
\newcommand{\sqle}{\sqsubseteq}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil}[1]{\lceil{#1}\rceil} |
Content:
A \emph{hypergraph} $\mathcal{H}$ is an ordered pair $(V, \mathcal{E})$ where $V$ is a set of vertices and $\mathcal{E}$ is a set of edges such that $\mathcal{E} \subseteq \mathcal{P}(V)$. In other words, an edge is nothing more than a set of vertices.
Sometimes it is useful to restrict this definition more. The empty hypegraph 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 transp
\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 transpose 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. |
|
|
|
|
|
