Гиперграф

Гипергра́ф, обобщение понятия графа. Гиперграф задаётся множеством ${\displaystyle V}$, элементы которого называются вершинами, и семейством ${\displaystyle {\mathcal {E}}}$ подмножеств множества ${\displaystyle V}$, называемых рёбрами гиперграфа; гиперграф обозначается ${\displaystyle (V,{\mathcal {E}})}$. Понятие гиперграф является вариантом давно известных понятий комплекса, блок-схемы, а также понятия сети.

Две вершины ${\displaystyle u}$ и ${\displaystyle v}$ гиперграфа называются смежными, если существует ребро, содержащее эти вершины. Вершина ${\displaystyle v}$ и ребро ${\displaystyle E}$ гиперграфа называются инцидентными, если ${\displaystyle v\in E}$. Гиперграф ${\displaystyle H}$ с ${\displaystyle n}$ вершинами и ${\displaystyle m}$ рёбрами можно задать матрицей инцидентности, т. е. матрицей ${\displaystyle \ \mid a_{ij}\ \mid }$ размера ${\displaystyle n\times m}$, в которой столбцы соответствуют рёбрам, а строки – вершинам гиперграфа и

${\displaystyle a_{ij}={\begin{cases}1,\ &{\text{если }}v_{i}\in E_{j},\\0,&{\text{если }}v_{i}\notin E_{j},\end{cases}}\quad i=1,\ldots ,n;\quad j=1,\ldots ,m.}$

Всякой прямоугольной матрице ${\displaystyle M}$ из нулей и единиц можно сопоставить гиперграф, для которого ${\displaystyle M}$ является матрицей инцидентности. Гиперграф ${\displaystyle H^{*}}$ называется двойственным по отношению к гиперграфу ${\displaystyle H}$, если матрица инцидентности гиперграфа ${\displaystyle H^{*}}$ получается транспонированием матрицы инцидентности гиперграфа ${\displaystyle H}$. Число рёбер гиперграфа, инцидентных данной вершине, называется степенью вершины. Степенью ребра называется число вершин гиперграфа, инцидентных этому ребру. Гиперграф ${\displaystyle (V',{\mathcal {E}}')}$ называется подгиперграфом гиперграфа ${\displaystyle (V,{\mathcal {E}})}$, если ${\displaystyle V'\subseteq V}$, ${\displaystyle {\mathcal {E}}'\subseteq {\mathcal {E}}}$ и вершина ${\displaystyle v}$ из ${\displaystyle V'}$ и ребро ${\displaystyle E}$ из ${\displaystyle {\mathcal {E}}'}$ инцидентны в гиперграфе ${\displaystyle (V',{\mathcal {E}}')}$ тогда и только тогда, когда они инцидентны в гиперграфе ${\displaystyle (V,{\mathcal {E}})}$.

Гиперграф можно изобразить на плоскости, сопоставляя вершинам гиперграфа точки плоскости, а рёбрам – связные области, охватывающие вершины, инцидентные этим рёбрам. Например, гиперграф ${\displaystyle H}$ с множеством вершин ${\displaystyle V=\{v_{1},v_{2},\ldots v_{6}\}}$ и семейством рёбер

${\displaystyle {\mathcal {E}}={\bigl \{}E_{1}=\{v_{1}\}}$
${\displaystyle E_{2}=\{v_{1},v_{3}\},}$
${\displaystyle E_{3}=\{v_{1},v_{2},v_{3}\}}$
${\displaystyle E_{4}=E_{5}=\{v_{2},v_{4}\}}$
${\displaystyle E_{6}=\{v_{3},v_{4},v_{5}\},}$
${\displaystyle E_{7}=\varnothing {\bigr \}}}$

можно изобразить на плоскости, как показано на рис.

Гиперграф ${\displaystyle H}$ можно представлять двудольным графом ${\displaystyle K(H)}$, в котором вершины одной доли ${\displaystyle U_{1}}$ соответствуют вершинам гиперграфа, а вершины другой доли ${\displaystyle U_{2}}$ – рёбрам гиперграфа ${\displaystyle H}$. При этом две вершины ${\displaystyle u'}$ из ${\displaystyle U_{1}}$ и ${\displaystyle u''}$ из ${\displaystyle U_{2}}$ соединены в графе ${\displaystyle K(H)}$ ребром, если вершина гиперграфа H, соответствующая вершине ${\displaystyle u'}$, инцидентна ребру гиперграфа ${\displaystyle H}$, соответствующему вершине ${\displaystyle u''}$. Гиперграф является графом, если каждое ребро его имеет степень, равную ${\displaystyle 2}$. Важным частным случаем понятия «гиперграф» является матроид.

Многие понятия теории графов, такие, как связность, планарность, хроматическое число, числа внутренней и внешней устойчивости (см. Числовые характеристики графов), переносятся и на гиперграфы. На гиперграфы переносятся также многие утверждения, справедливые для графов.