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

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

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

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

$$\begin{aligned} \mathscr E = \bigl\{ E_1=\{v_1\},\ E_2&=\{v_1,v_3\}, \ E_3 = \{v_1, v_2, v_3\},\\ E_4 = E_5 &= \{v_2, v_4\},\ E_6=\{v_3, v_4, v_5\}, \ E_7 = \varnothing\bigr\} \end{aligned}$$можно изобразить на плоскости, как показано на рис.

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

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