Введение

Обобщение теории графов

В математике гиперграф — это обобщение графа, в котором ребро может соединять любое число вершин. В отличие от этого, в обычном графе ребро соединяет ровно две вершины. Формально, ориентированный гиперграф — это пара (V, E), где V — множество элементов, называемых узлами, вершинами, точками или элементами, а E — множество пар подмножеств V. Каждая из этих пар (A, B) называется ребром или гиперребром; подмножество вершин A известно как его хвост или домен, а B — как его голова или кодомен. Порядок гиперграфа — это число вершин в V. Размер гиперграфа — это число ребер в E. Порядок ребра (A, B) в ориентированном гиперграфе равен |A| + |B|: то есть число вершин в хвосте плюс число вершин в голове. Приведенное выше определение обобщает переход от ориентированного графа к ориентированному гиперграфу, определяя голову или хвост каждого ребра как множество вершин (A или B), а не как одну вершину. Граф является частным случаем, когда каждый из этих множеств содержит только один элемент. Следовательно, любая стандартная теоретико-графовая концепция, не зависящая от порядка ребер, обобщается на теорию гиперграфов. По одному из определений, неориентированный гиперграф — это ориентированный гиперграф, имеющий симметричное множество ребер: если (A, B) ∈ E, то (B, A) ∈ E. Для упрощения обозначений можно удалить «дублирующиеся» гиперребра, поскольку модификатор «неориентированный» точно указывает на их существование: если (A, B) ∈ E, то (B, A) ∈ E, где (B, A) означает неявно в E. В то время как ребра графа соединяют только 2 узла, гиперребра соединяют произвольное число узлов. Однако часто желательно изучать гиперграфы, в которых все гиперребра имеют одинаковую кардинальность; k-однородный гиперграф — это гиперграф, в котором все его гиперребра имеют размер k. (Другими словами, такой гиперграф — это коллекция множеств, каждое из которых является гиперребром, соединяющим k узлов). Таким образом, 2-однородный гиперграф — это граф, 3-однородный гиперграф — это коллекция неупорядоченных троек и так далее. Неориентированный гиперграф также называют системой множеств или семейством множеств, взятых из универсального множества. Гиперграфы можно рассматривать как структуры инцидентности. В частности, существует двудольный «граф инцидентности» или «граф Леви», соответствующий каждому гиперграфу, и наоборот, каждый двудольный граф можно рассматривать как граф инцидентности гиперграфа, если он 2-раскрашен и указано, какой класс цвета соответствует вершинам гиперграфа, а какой — ребрам гиперграфа. Гиперграфы имеют много других названий. В вычислительной геометрии неориентированный гиперграф иногда называют пространством областей, а гиперребра — областями. В теории кооперативных игр гиперграфы называются простыми играми (играми голосования); это понятие применяется для решения задач в теории социального выбора. В некоторых публикациях ребра называют гиперссылками или коннекторами. Коллекция гиперграфов — это категория с гиперграфными гомоморфизмами в качестве морфизмов.

График заболеваемости

Гиперграф H может быть представлен двудольным графом BG следующим образом: множества X и E являются долями BG, и (x1, e1) соединены ребром, если и только если вершина x1 содержится в ребре e1 в H.

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

Матрица соседства

Можно провести аналогию между матрицей смежности гиперграфа и матрицей смежности графа. В случае графа матрица смежности является квадратной матрицей, которая показывает, соединены ли пары вершин. Аналогично, мы можем определить матрицу смежности для гиперграфа в общем случае, где гиперрёбра имеют вещественные веса, причём

Дальнейшие обобщения

Одним из возможных обобщений гиперграфа является разрешение краям указывать на другие края. Существует две вариации этого обобщения. В одной из них края состоят не только из множества вершин, но также могут содержать подмножества вершин, подмножества подмножеств вершин и так далее до бесконечности. По сути, каждый край — это просто внутренний узел дерева или направленного ациклического графа, а вершины — узлы-листья. Гиперграф — это просто коллекция деревьев с общими узлами (то есть, данный внутренний узел или лист может встречаться в нескольких разных деревьях). И наоборот, любую коллекцию деревьев можно интерпретировать как этот обобщенный гиперграф. Поскольку деревья широко используются в информатике и многих других областях математики, можно сказать, что гиперграфы возникают естественным образом. Например, это обобщение естественно возникает как модель алгебры термов: края соответствуют термам, а вершины — константам или переменным. Для такого гиперграфа принадлежность к множеству обеспечивает упорядочение, но это упорядочение не является ни частичным порядком, ни предпорядком, поскольку оно не транзитивно. Граф, соответствующий графу Леви этого обобщения, является направленным ациклическим графом. Рассмотрим, например, обобщенный гиперграф, у которого множество вершин — это , а множество краев — это и . Тогда, хотя и , неверно, что . Однако транзитивное замыкание принадлежности к множеству для таких гиперграфов индуцирует частичный порядок и "сглаживает" гиперграф до частично упорядоченного множества. В качестве альтернативы, можно разрешить краям указывать на другие края, независимо от требования, чтобы края были упорядочены как направленные ациклические графы. Это позволяет создавать графы с петлями на краях, которые не обязательно содержат вершины вообще. Например, рассмотрим обобщенный гиперграф, состоящий из двух краев и и нулевого числа вершин, так что и . Поскольку эта петля бесконечно рекурсивна, множества, являющиеся краями, нарушают аксиому основания. В частности, для таких гиперграфов не существует транзитивного замыкания принадлежности к множеству. Хотя такие структуры могут показаться странными на первый взгляд, их можно легко понять, заметив, что эквивалентное обобщение их графа Леви больше не является двудольным, а является просто общим направленным графом. Обобщенная матрица инцидентности для таких гиперграфов, по определению, является квадратной матрицей ранга, равного общему числу вершин плюс краев. Таким образом, для приведенного выше примера матрица инцидентности просто .