ГИПЕРГРАФ

ГИПЕРГРАФ - обобщение понятия графа. Г. задается множеством V, элементы к-рого наз. вершинами, и семейством подмножеств множества V, называемых ребрами Г.; Г. обозначается (V, ). Понятие Г. является вариантом давно известных понятий комплекса, блок-схемы, а также понятия сети.

Две вершины u и v Г. наз. смежными, если существует ребро, содержащее эти вершины. Вершина v и ребро Е Г. наз. инцидентными, если v ∈ E. Г. Н с n вершинами и m ребрами можно задать матрицей инцидентности, т. е. матрицей ||а_ij|| размера n × m, в к-рой столбцы соответствуют ребрам, а строки - вершинам Г. и.

Всякой прямоугольной матрице М из нулей и единиц можно сопоставить Г., для к-рого М является матрицей инцидентности. Г. Н* наз. двойственным по отношению к Г. Н, если матрица инцидентности Г. Н* получается транспонированием матрицы инцидентности Г. Н. Число ребер Г., инцидентных данной вершине, наз. степенью вершины. Степенью ребра наз. число вершин Г., инцидентных этому ребру. Г. (V, ') наз. подгиперграфом Г. (V, ), если V' = V, ' = и вершина v из V' и ребро Е из ' инцидентны в Г. (V, ') тогда и только тогда, когда они инцидентны в Г. (V, ).

Г. можно изобразить на плоскости, сопоставляя вершинам Г. точки плоскости, а ребрам - связные области, охватывающие вершины, инцидентные этим ребрам. Напр., Г. Н с множеством вершин V = {v₁, v₂, ..., v₆} и семейством ребер

= {E₁ = {v₁}, E₂ = {v₁, v₃}, Е₃ = {v₁, v₂, v₃}, E₄ = E₅ = {v₂, v₄}, E₆ = {v₃, v₄, v₅}, E₇ = ∅}

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

Г. Н можно представлять графом двудольным K(Н), в к-ром вершины одной доли U₁ соответствуют вершинам Г., а вершины другой доли U₂ - ребрам Г. Н. При этом две вершины u' из U₁ и u'' из U₂ соединены в графе К(Н) ребром, если вершина Г., соответствующая вершине u', инцидентна ребру Г., соответствующему вершине u''. Г. является графом, если каждое ребро его имеет степень, равную 2. Важным частным случаем понятия «Г.» является матроид. Многие понятия теории графов, такие, как связность, планарность, хроматич. число, числа внутренней и внешней устойчивости, переносятся и на Г. На Г. переносятся также многие утверждения, справедливые для графов.

Лит.: [1] Зыков А. А., «Успехи матем. наук», 1974, т. 29, в. 6, с. 89-154; [2] Веrgе С. Graphes et hypergraphes, Р., 1970.

А. А. Сапоженко.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.