Гиперграф

В математике гиперграф — это обобщение графа , в котором ребро может соединять любое количество вершин . Напротив, в обычном графе ребро соединяет ровно две вершины.

Формально неориентированный гиперграф — это пара , где — набор элементов, называемых узлами или вершинами , и (в неориентированном гиперграфе) — набор непустых подмножеств называемых гиперребрами или ребрами . Следовательно, является подмножеством , где является набором мощности . Размер множества вершин называется порядком гиперграфа , а размер множества ребер — размером гиперграфа .${\ Displaystyle Н}$${\ Displaystyle Н = (Х, Е)}$${\ Displaystyle Х}$${\ Displaystyle Е}$${\ Displaystyle Х}$${\ Displaystyle Е}$${\ displaystyle {\ mathcal {P}} (X) \ setminus \ {\ emptyset \}}$${\ displaystyle {\ mathcal {P}} (X)}$${\ Displaystyle Х}$

Ориентированный гиперграф отличается тем, что его гиперребра являются не множествами, а упорядоченной парой подмножеств , составляющих хвост и голову гиперребра.${\ Displaystyle Х}$

В то время как ребра графа соединяют только 2 узла, гиперребра соединяют произвольное количество узлов. Однако часто желательно изучать гиперграфы, в которых все гиперребра имеют одинаковую мощность; k - однородный гиперграф — это гиперграф, все гиперребра которого имеют размер k . (Другими словами, один такой гиперграф — это набор множеств, каждое такое множество — гиперребро, соединяющее k узлов.) Таким образом, 2-однородный гиперграф — это граф, 3-однородный гиперграф — это набор неупорядоченных троек и так далее. Неориентированный гиперграф также называется системой множеств или семейством множеств , взятых из универсального множества .

Гиперграфы можно рассматривать как структуры инцидентности . В частности, существует двудольный «граф инцидентности» или « граф Леви », соответствующий каждому гиперграфу, и, наоборот, большинство, но не все двудольные графы можно рассматривать как графы инцидентности гиперграфов.

Гиперграфы имеют много других названий. В вычислительной геометрии неориентированный гиперграф иногда может называться диапазонным пространством , а гиперребра называются диапазонами . ^[2] В теории кооперативных игр гиперграфы называются простыми играми (играми с голосованием); это понятие применяется для решения задач теории социального выбора . В некоторых источниках ребра называются гиперссылками или соединителями . ^[3]

Пример неориентированного гиперграфа с и . Этот гиперграф имеет порядок 7 и размер 4. Здесь ребра соединяют не просто две вершины, а несколько, и представлены цветами.${\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}$${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}=}$ ${\displaystyle \{\{v_{1},v_{2},v_{3}\},}$ ${\displaystyle \{v_{2},v_{3}\},}$ ${\displaystyle \{v_{3},v_{5},v_{6}\},}$ ${\displaystyle \{v_{4}\}\}}$

Альтернативное представление гиперграфа, представленное на рисунке выше, называется PAOH. ^[1] Ребра — это вертикальные линии, соединяющие вершины. V7 — изолированная вершина. Вершины выровнены по левому краю. В легенде справа показаны названия ребер.

Пример ориентированного гиперграфа с и .${\displaystyle X=\{1,2,3,4,5,6\}}$${\displaystyle E=\{a_{1},a_{2},a_{3},a_{4},a_{5}\}=}$ ${\displaystyle \{(\{1\},\{2\}),}$ ${\displaystyle (\{2\},\{3\}),}$ ${\displaystyle (\{3\},\{1\}),}$ ${\displaystyle (\{2,3\},\{4,5\}),}$ ${\displaystyle (\{3,5\},\{6\})\}}$

Эту принципиальную схему можно интерпретировать как рисунок гиперграфа, в котором четыре вершины (изображенные в виде белых прямоугольников и дисков) соединены тремя гиперребрами, нарисованными в виде деревьев.

Диаграмма Венна 4-го порядка, которую можно интерпретировать как рисунок подразделения гиперграфа с 15 вершинами (15 цветных областей) и 4 гиперребрами (4 эллипса).