Гиперграф

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

Пример неориентированного гиперграфа с и . Этот гиперграф имеет порядок 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\})\}}$

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

Формально, ориентированный гиперграф — это пара , где — набор элементов, называемых узлами , вершинами , точками или элементами , а — набор пар подмножеств . Каждая из этих пар называется ребром или гиперребром ; подмножество вершин известно как его хвост или домен , а также как его голова или кодомен . ${\displaystyle (X,E)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle X}$ ${\displaystyle (D,C)\in E}$ ${\displaystyle D}$ ${\displaystyle C}$

Порядок гиперграфа — это число вершин в . Размер гиперграфа — это число ребер в . Порядок ребра в ориентированном гиперграфе — это : то есть число вершин в его хвосте, за которым следует число вершин в его голове. ${\displaystyle (X,E)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle e=(D,C)}$ ${\displaystyle |e|=(|D|,|C|)}$

Определение выше обобщает направленный граф на направленный гиперграф, определяя начало или конец каждого ребра как набор вершин ( или ), а не как одну вершину. Граф тогда является особым случаем, когда каждый из этих наборов содержит только один элемент. Следовательно, любая стандартная концепция теории графов, которая не зависит от порядков ребер, будет обобщена до теории гиперграфов. ${\displaystyle C\subseteq X}$ ${\displaystyle D\subseteq X}$ ${\displaystyle |e|}$

Неориентированный гиперграф — это неориентированный граф, ребра которого соединяют не только две вершины, но и произвольное число. ^[2] Неориентированный гиперграф также называется системой множеств или семейством множеств, взятых из универсального множества . ${\displaystyle (X,E)}$

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

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

Совокупность гиперграфов представляет собой категорию с гомоморфизмами гиперграфов в качестве морфизмов .

Приложения

Ненаправленные гиперграфы полезны при моделировании таких вещей, как проблемы выполнимости, ^[5] базы данных, ^[6] машинное обучение, ^[7] и проблемы дерева Штейнера . ^[8] Они широко использовались в задачах машинного обучения в качестве модели данных и регуляризации классификатора (математика) . ^[9] Приложения включают в себя рекомендательную систему (сообщества как гиперребра), ^{[10] [11]} поиск изображений (корреляции как гиперребра), ^[12] и биоинформатику (биохимические взаимодействия как гиперребра). ^[13] Представительные методы обучения гиперграфов включают спектральную кластеризацию гиперграфов , которая расширяет теорию спектральных графов с помощью лапласиана гиперграфов, ^[14] и полуконтролируемое обучение гиперграфов , которое вводит дополнительные структурные затраты гиперграфов для ограничения результатов обучения. ^[15] Для крупномасштабных гиперграфов также доступна распределенная структура ^[7], созданная с использованием Apache Spark . Может быть желательно изучать гиперграфы, в которых все гиперребра имеют одинаковую мощность; k-однородный гиперграф — это гиперграф, все его гиперребра которого имеют размер k . (Другими словами, один такой гиперграф представляет собой набор множеств, каждое такое множество — гиперребро, соединяющее k узлов.) Таким образом, 2-однородный гиперграф — это граф, 3-однородный гиперграф — это набор неупорядоченных троек и т. д.

Направленные гиперграфы могут использоваться для моделирования таких вещей, как приложения телефонии, ^[16] обнаружение отмывания денег , ^[17] исследование операций, ^[18] и планирование транспорта. Они также могут использоваться для моделирования выполнимости Хорна . ^[19]

Обобщения понятий из графов

Многие теоремы и концепции, связанные с графами, справедливы и для гиперграфов, в частности:

• Сопоставление в гиперграфах ;
• Вершинное покрытие в гиперграфах (также известное как: трансверсальное );
• Линейный график гиперграфа ;
• Грамматика гиперграфов — создана путем расширения класса гиперграфов набором правил замены;
• Теорема Рамсея ;
• Теорема Эрдёша–Ко–Радо ;
• Теорема Крускала–Катоны об однородных гиперграфах;
• Теоремы типа Холла для гиперграфов .

В ориентированных гиперграфах: транзитивное замыкание и задачи нахождения кратчайшего пути. ^[18]

Рисунок гиперграфа

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

Хотя гиперграфы сложнее рисовать на бумаге, чем графики, несколько исследователей изучали методы визуализации гиперграфов.

В одном из возможных визуальных представлений гиперграфов, похожем на стандартный стиль рисования графа , в котором кривые на плоскости используются для изображения ребер графа, вершины гиперграфа изображаются как точки, диски или коробки, а его гиперребра изображаются как деревья, вершины которых являются их листьями. ^{[20] [21]} Если вершины представлены как точки, гиперребра также могут быть показаны как гладкие кривые, соединяющие наборы точек, или как простые замкнутые кривые , охватывающие наборы точек. ^{[22] [23] [24]}

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

В другом стиле визуализации гиперграфа, модели подразделения рисунка гиперграфа, ^[25] плоскость подразделяется на области, каждая из которых представляет одну вершину гиперграфа. Гиперрёбра гиперграфа представлены смежными подмножествами этих областей, которые могут быть обозначены раскраской, рисованием контуров вокруг них или и тем, и другим. Например, диаграмму Венна порядка n можно рассматривать как рисунок подразделения гиперграфа с n гиперрёбрами (кривыми, определяющими диаграмму) и 2 ⁿ  − 1 вершинами (представленными областями, на которые эти кривые подразделяют плоскость). В отличие от распознавания планарных графов за полиномиальное время, определение того, имеет ли гиперграф рисунок планарного подразделения, является NP-полной задачей , ^[26] но существование рисунка этого типа может быть эффективно проверено, когда шаблон смежности областей ограничен путем, циклом или деревом. ^[27]

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

Раскраска гиперграфа

Классическая раскраска гиперграфа — это назначение одного из цветов из множества каждой вершине гиперграфа таким образом, чтобы каждое гиперребро содержало не менее двух вершин различных цветов. Другими словами, не должно быть ни одного одноцветного гиперребра с мощностью не менее 2. В этом смысле это прямое обобщение раскраски графа. Минимальное количество используемых различных цветов по всем раскраскам называется хроматическим числом гиперграфа. ${\displaystyle \{1,2,3,...,\lambda \}}$

Гиперграфы, для которых существует раскраска с использованием до k цветов, называются k-раскрашиваемыми . 2-раскрашиваемые гиперграфы являются как раз двудольными.

Существует множество обобщений классической раскраски гиперграфов. Одно из них — так называемая смешанная раскраска гиперграфов, когда разрешены одноцветные ребра. Некоторые смешанные гиперграфы нераскрашиваемы для любого количества цветов. Общий критерий нераскрашиваемости неизвестен. Когда смешанный гиперграф раскрашиваем, то минимальное и максимальное количество используемых цветов называются нижним и верхним хроматическими числами соответственно. ^[28]

Свойства гиперграфов

Гиперграф может иметь различные свойства, такие как:

• Пустой - не имеет рёбер.
• Непростой (или множественный ) — имеет петли (гиперребра с одной вершиной) или повторяющиеся ребра, что означает, что может быть два или более ребер, содержащих один и тот же набор вершин.
• Простой — не имеет петель и повторяющихся рёбер.
• ${\displaystyle d}$-регулярный - каждая вершина имеет степень , т.е. содержится ровно в гиперребрах. ${\displaystyle d}$ ${\displaystyle d}$
• 2-раскрашиваемый — его вершины можно разбить на два класса U и V таким образом, что каждое гиперребро с мощностью не менее 2 содержит не менее одной вершины из обоих классов. Альтернативный термин — Свойство B.
  • Два более сильных свойства — двудольность и сбалансированность .
• ${\displaystyle k}$-равномерный - каждое гиперребро содержит ровно вершин. ${\displaystyle k}$
• ${\displaystyle k}$-partite — вершины разделены на части, и каждое гиперребро содержит ровно одну вершину каждого типа. ${\displaystyle k}$
  • Каждый -дольный гиперграф (для ) является одновременно -однородным и двудольным (и 2-раскрашиваемым). ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k}$
• Сокращение : ^[29] ни одно гиперребро не является строгим подмножеством другого гиперребра; эквивалентно, каждое гиперребро является максимальным для включения. Сокращение гиперграфа — это сокращенный гиперграф, полученный путем удаления каждого гиперребра, которое включено в другое гиперребро.
• Замкнутый вниз — каждое подмножество ребер неориентированного гиперграфа также является гиперребром. Замкнутый вниз гиперграф обычно называется абстрактным симплициальным комплексом . Он, как правило, не редуцируется, если только все гиперребра не имеют мощность 1.
  • Абстрактный симплициальный комплекс со свойством аугментации называется матроидом .
• Ламинарный : для любых двух гиперребер они либо не пересекаются, либо одно включено в другое. Другими словами, множество гиперребер образует ламинарное семейство множеств .

Связанные гиперграфы

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

Пусть — гиперграф, состоящий из вершин ${\displaystyle H=(X,E)}$

${\displaystyle X=\lbrace x_{i}\mid i\in I_{v}\rbrace ,}$

и имея установленный край

${\displaystyle E=\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq X,e_{i}\neq \emptyset \rbrace ,}$

где и — индексные множества вершин и ребер соответственно. ${\displaystyle I_{v}}$ ${\displaystyle I_{e}}$

Подгиперграф — это гиперграф с удаленными вершинами. Формально подгиперграф, индуцированный , определяется как ${\displaystyle H_{A}}$ ${\displaystyle A\subseteq X}$

${\displaystyle H_{A}=\left(A,\lbrace e\cap A\mid e\in E,e\cap A\neq \emptyset \rbrace \right).}$

Альтернативный термин — ограничение H до A. ^[30] : ⁴⁶⁸

Расширение подгиперграфа — это гиперграф, в котором каждое гиперребро , частично содержащееся в подгиперграфе, полностью содержится в расширении . Формально ${\displaystyle H}$ ${\displaystyle H_{A}}$ ${\displaystyle Ex(H_{A})}$

${\displaystyle Ex(H_{A})=(A\cup A',E')}$с и . ${\displaystyle A'=\bigcup _{e\in E}e\setminus A}$ ${\displaystyle E'=\lbrace e\in E\mid e\subseteq (A\cup A')\rbrace }$

Частичный гиперграф — это гиперграф с удаленными некоторыми ребрами. ^{[30] : 468} Если задано подмножество набора индексов ребер, то частичный гиперграф, сгенерированный с помощью, является гиперграфом ${\displaystyle J\subset I_{e}}$ ${\displaystyle J}$

${\displaystyle \left(X,\lbrace e_{i}\mid i\in J\rbrace \right).}$

Если задано подмножество , то гиперграф сечения является частичным гиперграфом ${\displaystyle A\subseteq X}$

${\displaystyle H\times A=\left(A,\lbrace e_{i}\mid i\in I_{e},e_{i}\subseteq A\rbrace \right).}$

Двойственный гиперграф — это гиперграф , вершины и ребра которого поменяны местами, так что вершины задаются как и ребра которого задаются как где ${\displaystyle H^{*}}$ ${\displaystyle H}$ ${\displaystyle \lbrace e_{i}\rbrace }$ ${\displaystyle \lbrace X_{m}\rbrace }$

${\displaystyle X_{m}=\lbrace e_{i}\mid x_{m}\in e_{i}\rbrace .}$

Если понятие равенства определено должным образом, как это сделано ниже, то операция взятия двойственного гиперграфа является инволюцией , т.е.

${\displaystyle \left(H^{*}\right)^{*}=H.}$

Связный граф G с тем же набором вершин, что и связный гиперграф H, является основным графом для H, если каждое гиперребро H индуцирует связный подграф в G. Для несвязного гиперграфа H , G является основным графом, если существует биекция между связными компонентами G и H , такая, что каждая связная компонента G' из G является основным графом соответствующего H' .

2-секционный граф (или граф клик , представляющий граф , первичный граф , граф Гайфмана ) гиперграфа — это граф с теми же вершинами гиперграфа и ребрами между всеми парами вершин, содержащимися в одном и том же гиперребре.

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

Пусть и . Каждый гиперграф имеет матрицу инцидентности . ${\displaystyle V=\{v_{1},v_{2},~\ldots ,~v_{n}\}}$ ${\displaystyle E=\{e_{1},e_{2},~\ldots ~e_{m}\}}$ ${\displaystyle n\times m}$

Для неориентированного гиперграфа, где ${\displaystyle I=(b_{ij})}$

${\displaystyle b_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

Транспонирование матрицы инцидентности определяет гиперграф , называемый двойственным к , где — множество из m элементов, а — множество из n элементов подмножеств . Для и тогда и только тогда, когда . ${\displaystyle I^{t}}$ ${\displaystyle H^{*}=(V^{*},\ E^{*})}$ ${\displaystyle H}$ ${\displaystyle V^{*}}$ ${\displaystyle E^{*}}$ ${\displaystyle V^{*}}$ ${\displaystyle v_{j}^{*}\in V^{*}}$ ${\displaystyle e_{i}^{*}\in E^{*},~v_{j}^{*}\in e_{i}^{*}}$ ${\displaystyle b_{ij}=1}$

Для направленного гиперграфа головы и хвосты каждого гиперребра обозначаются и соответственно. ^[19] где ${\displaystyle e_{j}}$ ${\displaystyle H(e_{j})}$ ${\displaystyle T(e_{j})}$ ${\displaystyle I=(b_{ij})}$

${\displaystyle b_{ij}=\left\{{\begin{matrix}-1&\mathrm {if} ~v_{i}\in T(e_{j})\\1&\mathrm {if} ~v_{i}\in H(e_{j})\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

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

Гиперграф H может быть представлен двудольным графом BG следующим образом: множества X и E являются частями BG , а ( x ₁ , e ₁ ) соединены ребром тогда и только тогда, когда вершина x 1 _{содержится} в ребре e ₁ в H.

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

Матрица смежности

Параллель для матрицы смежности гиперграфа можно провести из матрицы смежности графа. В случае графа матрица смежности представляет собой квадратную матрицу, которая указывает, являются ли пары вершин смежными . Аналогично, мы можем определить матрицу смежности для гиперграфа в общем случае, где гиперребра имеют действительные веса с ${\displaystyle A=(a_{ij})}$ ${\displaystyle e_{k\leq m}}$ ${\displaystyle w_{e_{k}}\in \mathbb {R} }$

${\displaystyle a_{ij}=\left\{{\begin{matrix}w_{e_{k}}&\mathrm {if} ~(v_{i},v_{j})\in E\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

Циклы

В отличие от обычных неориентированных графов, для которых существует единое естественное понятие циклов и ациклических графов , для гиперграфов существует множество естественных неэквивалентных определений ацикличности, которые сводятся к обычной ацикличности графа для частного случая обычных графов.

Первое определение ацикличности для гиперграфов было дано Клодом Берже : ^[31] гиперграф является ацикличным по Берже, если его граф инцидентности ( двудольный граф, определенный выше) является ацикличным. Это определение очень ограничительно: например, если гиперграф имеет некоторую пару вершин и некоторую пару гиперребер, таких что и , то он является цикличным по Берже. Цикличность по Берже, очевидно, может быть проверена за линейное время путем исследования графа инцидентности. ${\displaystyle v\neq v'}$ ${\displaystyle f\neq f'}$ ${\displaystyle v,v'\in f}$ ${\displaystyle v,v'\in f'}$

Мы можем определить более слабое понятие ацикличности гиперграфа, ^[6] позже названное α-ацикличностью. Это понятие ацикличности эквивалентно тому, что гиперграф является конформным (каждая клика первичного графа покрыта некоторым гиперребром), а его первичный граф является хордовым ; оно также эквивалентно сводимости к пустому графу посредством алгоритма GYO ^{[32] [33]} (также известного как алгоритм Грэма), конфлюэнтного итерационного процесса, который удаляет гиперребра, используя обобщенное определение ушей . В области теории баз данных известно, что схема базы данных обладает определенными желаемыми свойствами, если ее базовый гиперграф является α-ацикличным. ^[34] Кроме того, α-ацикличность также связана с выразительностью охраняемого фрагмента логики первого порядка .

Мы можем проверить за линейное время , является ли гиперграф α-ацикличным. ^[35]

Обратите внимание, что α-ацикличность имеет контринтуитивное свойство, заключающееся в том, что добавление гиперребер к α-циклическому гиперграфу может сделать его α-ациклическим (например, добавление гиперребра, содержащего все вершины гиперграфа, всегда сделает его α-ациклическим). Частично мотивированный этим предполагаемым недостатком, Рональд Фейгин ^[36] определил более сильные понятия β-ацикличности и γ-ацикличности. Мы можем сформулировать β-ацикличность как требование, чтобы все подгиперграфы гиперграфа были α-ациклическими, что эквивалентно ^[36] более раннему определению Грэма. ^[33] Понятие γ-ацикличности является более ограничительным условием, которое эквивалентно нескольким желательным свойствам схем баз данных и связано с диаграммами Бахмана . Как β-ацикличность, так и γ-ацикличность могут быть проверены за полиномиальное время .

Эти четыре понятия ацикличности сопоставимы: ацикличность Берже подразумевает γ-ацикличность, которая подразумевает β-ацикличность, которая подразумевает α-ацикличность. Однако ни одно из обратных следствий не выполняется, поэтому эти четыре понятия различны. ^[36]

Изоморфизм, симметрия и равенство

Гомоморфизм гиперграфа — это отображение множества вершин одного гиперграфа на другой, при котором каждое ребро отображается на одно другое ребро.

Гиперграф изоморфен гиперграфу , записанному так, как будто существует биекция ${\displaystyle H=(X,E)}$ ${\displaystyle G=(Y,F)}$ ${\displaystyle H\simeq G}$

${\displaystyle \phi :X\to Y}$

и перестановка такая , что ${\displaystyle \pi }$ ${\displaystyle I}$

${\displaystyle \phi (e_{i})=f_{\pi (i)}}$

Биекция тогда называется изоморфизмом графов. Обратите внимание, что ${\displaystyle \phi }$

${\displaystyle H\simeq G}$тогда и только тогда, когда . ${\displaystyle H^{*}\simeq G^{*}}$

Когда ребра гиперграфа явно помечены, появляется дополнительное понятие сильного изоморфизма . Говорят, что сильно изоморфен , если перестановка является тождеством. Тогда пишут . Обратите внимание, что все сильно изоморфные графы изоморфны, но не наоборот. ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\cong G}$

Когда вершины гиперграфа явно помечены, то есть понятия эквивалентности , а также равенства . Говорят, что эквивалентно , и пишут, если изоморфизм имеет ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\equiv G}$ ${\displaystyle \phi }$

${\displaystyle \phi (x_{n})=y_{n}}$

и

${\displaystyle \phi (e_{i})=f_{\pi (i)}}$

Обратите внимание, что

${\displaystyle H\equiv G}$если и только если ${\displaystyle H^{*}\cong G^{*}}$

Если, кроме того, перестановка является тождеством, говорят, что равно , и пишут . Обратите внимание, что при таком определении равенства графы являются самодвойственными: ${\displaystyle \pi }$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H=G}$

${\displaystyle \left(H^{*}\right)^{*}=H}$

Автоморфизм гиперграфа — это изоморфизм множества вершин в себя, то есть перемаркировка вершин. Множество автоморфизмов гиперграфа H (= ( X ,  E )) — это группа относительно композиции, называемая группой автоморфизмов гиперграфа и обозначаемая как Aut( H ).

Примеры

Рассмотрим гиперграф с ребрами ${\displaystyle H}$

${\displaystyle H=\lbrace e_{1}=\lbrace a,b\rbrace ,e_{2}=\lbrace b,c\rbrace ,e_{3}=\lbrace c,d\rbrace ,e_{4}=\lbrace d,a\rbrace ,e_{5}=\lbrace b,d\rbrace ,e_{6}=\lbrace a,c\rbrace \rbrace }$

и

${\displaystyle G=\lbrace f_{1}=\lbrace \alpha ,\beta \rbrace ,f_{2}=\lbrace \beta ,\gamma \rbrace ,f_{3}=\lbrace \gamma ,\delta \rbrace ,f_{4}=\lbrace \delta ,\alpha \rbrace ,f_{5}=\lbrace \alpha ,\gamma \rbrace ,f_{6}=\lbrace \beta ,\delta \rbrace \rbrace }$

Тогда ясно, что и изоморфны (с и т.д. ), но они не сильно изоморфны. Так, например, в вершина встречается с ребрами 1, 4 и 6, так что, ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \phi (a)=\alpha }$ ${\displaystyle H}$ ${\displaystyle a}$

${\displaystyle e_{1}\cap e_{4}\cap e_{6}=\lbrace a\rbrace }$

В графе не существует вершин, которые пересекаются с ребрами 1, 4 и 6: ${\displaystyle G}$

${\displaystyle f_{1}\cap f_{4}\cap f_{6}=\varnothing }$

В этом примере и эквивалентны, а двойственные элементы сильно изоморфны: . ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H\equiv G}$ ${\displaystyle H^{*}\cong G^{*}}$

Симметрия

Theранг гиперграфа— это максимальная мощность любого из ребер в гиперграфе. Если все ребра имеют одинаковую мощностьk, гиперграф называетсяоднороднымилиk-однородным, или называетсяk-гиперграфом. Граф — это просто 2-однородный гиперграф. ${\displaystyle r(H)}$ ${\displaystyle H}$

Степень d(v) вершины v — это число ребер, которые ее содержат. H является k-регулярным, если каждая вершина имеет степень k .

Двойственный гиперграф однородного гиперграфа является регулярным и наоборот.

Две вершины x и y из H называются симметричными, если существует автоморфизм такой, что . Два ребра и называются симметричными, если существует автоморфизм такой, что . ${\displaystyle \phi (x)=y}$ ${\displaystyle e_{i}}$ ${\displaystyle e_{j}}$ ${\displaystyle \phi (e_{i})=e_{j}}$

Гиперграф называется вершинно-транзитивным (или вершинно-симметричным ), если все его вершины симметричны. Аналогично, гиперграф является реберно-транзитивным, если все ребра симметричны. Если гиперграф является как реберно-, так и вершинно-симметричным, то гиперграф просто транзитивен .

Ввиду двойственности гиперграфа изучение транзитивности ребер идентично изучению транзитивности вершин.

Разделы

Теорема о разбиении, предложенная Э. Даубером ^[37], утверждает, что для реберно-транзитивного гиперграфа существует разбиение ${\displaystyle H=(X,E)}$

${\displaystyle (X_{1},X_{2},\cdots ,X_{K})}$

множества вершин, таких, что подгиперграф, порожденный , является транзитивным для каждого , и таких, что ${\displaystyle X}$ ${\displaystyle H_{X_{k}}}$ ${\displaystyle X_{k}}$ ${\displaystyle 1\leq k\leq K}$

${\displaystyle \sum _{k=1}^{K}r\left(H_{X_{k}}\right)=r(H)}$

где - ранг H. ${\displaystyle r(H)}$

Как следствие, реберно-транзитивный гиперграф, не являющийся вершинно-транзитивным, является двуцветным.

Разбиение графа (и, в частности, разбиение гиперграфа) имеет множество применений в проектировании ИС ^[38] и параллельных вычислениях . ^{[39] [40] [41]} Эффективные и масштабируемые алгоритмы разбиения гиперграфа также важны для обработки крупномасштабных гиперграфов в задачах машинного обучения. ^[7]

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

Одним из возможных обобщений гиперграфа является разрешение ребрам указывать на другие ребра. Существует два варианта этого обобщения. В одном из них ребра состоят не только из набора вершин, но также могут содержать подмножества вершин, подмножества подмножеств вершин и так далее до бесконечности . По сути, каждое ребро — это просто внутренний узел дерева или направленного ациклического графа , а вершины — это листовые узлы. Тогда гиперграф — это просто набор деревьев с общими, разделяемыми узлами (то есть заданный внутренний узел или лист может встречаться в нескольких разных деревьях). И наоборот, каждый набор деревьев можно понимать как этот обобщенный гиперграф. Поскольку деревья широко используются в компьютерной науке и многих других разделах математики, можно сказать, что гиперграфы также появляются естественным образом. Так, например, это обобщение возникает естественным образом как модель алгебры терминов ; ребра соответствуют терминам , а вершины соответствуют константам или переменным.

Для такого гиперграфа членство во множестве тогда обеспечивает упорядочение, но упорядочение не является ни частичным порядком , ни предпорядком , поскольку оно не транзитивно. Граф, соответствующий графу Леви этого обобщения, является направленным ациклическим графом . Рассмотрим, например, обобщенный гиперграф, множество вершин которого равно и чьи ребра равны и . Тогда, хотя и , неверно, что . Однако транзитивное замыкание членства во множестве для таких гиперграфов действительно индуцирует частичный порядок и «сглаживает» гиперграф в частично упорядоченное множество . ${\displaystyle V=\{a,b\}}$ ${\displaystyle e_{1}=\{a,b\}}$ ${\displaystyle e_{2}=\{a,e_{1}\}}$ ${\displaystyle b\in e_{1}}$ ${\displaystyle e_{1}\in e_{2}}$ ${\displaystyle b\in e_{2}}$

В качестве альтернативы, рёбрам может быть разрешено указывать на другие рёбра, независимо от требования, чтобы рёбра были упорядочены как направленные, ациклические графы. Это позволяет графам с рёбрами-петлями, которые вообще не должны содержать вершин. Например, рассмотрим обобщённый гиперграф, состоящий из двух рёбер и , и нулевых вершин, так что и . Поскольку этот цикл бесконечно рекурсивен, множества, которые являются рёбрами, нарушают аксиому основания . В частности, для таких гиперграфов не существует транзитивного замыкания членства во множестве. Хотя такие структуры могут показаться странными на первый взгляд, их можно легко понять, заметив, что эквивалентное обобщение их графа Леви больше не является двудольным , а представляет собой просто некоторый общий направленный граф . ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{1}=\{e_{2}\}}$ ${\displaystyle e_{2}=\{e_{1}\}}$

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

${\displaystyle \left[{\begin{matrix}0&1\\1&0\end{matrix}}\right].}$

Смотрите также

• BF-граф  – Тип ориентированного гиперграфа
• Комбинаторный дизайн  – Симметричное расположение конечных множеств
• Факторный граф  – двудольный граф, представляющий факторизацию функции.Pages displaying wikidata descriptions as a fallback
• Greedoid  – множество систем, используемых в жадной оптимизации
• Структура инцидентности  – абстрактная математическая система двух типов объектов и отношений между ними.
• Мультиграф  – граф с несколькими ребрами между двумя вершинами.
• Система P  – Вычислительная модель
• Умножение разреженной матрицы на вектор  – Процедура вычисления
• Сеть Петри  – Модель для описания распределенных системPages displaying short descriptions of redirect targets

Примечания

1. Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 26 (1). IEEE: 12. doi :10.1109/TVCG.2019.2933196. eISSN  1941-0506. ISSN  1077-2626. PMID  31398121. S2CID  199518871. Архивировано (PDF) из оригинала 26.01.2021 . Получено 08.09.2020 .
2. Оуврар, Ксавье (2020), «Гиперграфы: введение и обзор», arXiv : 2002.05014 [cs.DM].
3. Хаусслер, Дэвид ; Вельцль, Эмо (1987), «ε-сети и запросы симплексного диапазона», Дискретная и вычислительная геометрия , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR  0884223.
4. Pearl, Judea (1984). Эвристика: интеллектуальные стратегии поиска для решения компьютерных проблем. Addison-Wesley Publishing Company. стр. 25. ISBN 978-0-201-05594-8. Архивировано из оригинала 2023-02-04 . Получено 2021-06-12 .
5. Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006). Свидетели невыполнимости плотных случайных 3CNF-формул. 47-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS'06). IEEE. стр. 497–508. doi :10.1109/FOCS.2006.78. Архивировано из оригинала 27.01.2021 . Получено 20.01.2021 .
6. Beeri, C.; Fagin, R .; Maier, D.; Yannakakis, M. (1983). "О желательности ациклических схем баз данных" (PDF) . Journal of the ACM . 30 (3): 479–513. doi :10.1145/2402.322389. S2CID  2418740. Архивировано (PDF) из оригинала 21.04.2021 . Получено 03.01.2021 .
7. Хуан, Цзинь; Чжан, Руи; Ю, Джеффри Сюй (2015). «Масштабируемое обучение и обработка гиперграфов». Международная конференция IEEE по интеллектуальному анализу данных 2015 г. (PDF) . стр. 775–780. doi :10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. S2CID  5130573. Архивировано (PDF) из оригинала 2021-01-26 . Получено 2021-01-08 .
8. Бразилия, М; Захариасен, М (2015). «Деревья Штейнера в графах и гиперграфах». Оптимальные деревья взаимосвязей на плоскости . Алгоритмы и комбинаторика. Т. 29. Springer. С. 301–317. doi :10.1007/978-3-319-13915-9_5. ISBN 978-3-319-13915-9. Архивировано из оригинала 2021-01-29 . Получено 2021-01-20 .
9. Чжоу, Дэнъюн; Хуан, Цзяюань; Шолькопф, Бернхард (2006), «Обучение с помощью гиперграфов: кластеризация, классификация и встраивание», Достижения в области нейронных систем обработки информации , MIT Press, стр. 1601–8, ISBN 9780262256919, заархивировано из оригинала 2021-10-22 , извлечено 2021-07-24
10. Гошал, Гураб; Златич, Винко; Калдарелли, Гвидо; Ньюман, Марк Э.Дж. (2009), «Случайные гиперграфы и их приложения», Physical Review E , 79 (6): 066118, arXiv : 0903.0419 , Bibcode : 2009PhRvE..79f6118G, doi : 10.1103/PhysRevE.79.066118, PMID  19658575, S2CID  6391099
11. Тан, Шулун; Бу, Цзяцзюнь; Чэнь, Чунь; Сюй, Бин; Ван, Кан; Хэ, Сяофэй (октябрь 2011 г.), «Использование богатой информации социальных сетей для рекомендации музыки с помощью гиперграфовой модели», ACM Transactions on Multimedia Computing, Communications, and Applications , 7S (1), Статья 22, Bibcode : 2011smma.book..213T, doi : 10.1145/2037676.2037679, S2CID  432036
12. Лю, Циншань; Хуан, Ючи; Метаксас, Димитрис Н. (2013), «Гиперграф с выборкой для поиска изображений», Pattern Recognition , 44 (10–11): 2255–2262, doi :10.1016/j.patcog.2010.07.014
13. Патро, Роб; Кингсофорд, Карл (2013), «Прогнозирование взаимодействий белков с помощью экономного вывода истории сети», Биоинформатика , 29 (10–11): 237–246, doi :10.1093/bioinformatics/btt224, PMC 3694678 , PMID  23812989 
14. Гао, Туэ; Ван, Мэн; Чжа, Чжэн-Цзюнь; Шэнь, Цзяли; Ли, Сюэлун; У, Синьдун (2013), «Визуально-текстовое совместное обучение релевантности для поиска изображений в социальных сетях на основе тегов», IEEE Transactions on Image Processing , 22 (1): 363–376, Bibcode : 2013ITIP...22..363Y, doi : 10.1109/tip.2012.2202676, PMID  22692911, S2CID  7432373, архивировано из оригинала 23.09.2017 , извлечено 22.09.2017
15. Tian, ​​Ze; Hwang, TaeHyun; Kuang, Rui (2009), «Алгоритм обучения на основе гиперграфа для классификации экспрессии генов и данных arrayCGH с априорными знаниями», Bioinformatics , 25 (21): 2831–2838, doi : 10.1093/bioinformatics/btp467 , PMID  19648139
16. Голдштейн, А. (1982). «Направленная база данных гиперграфа: модель для местной телефонной линии». Bell System Technical Journal . 61 (9): 2529–54. doi :10.1002/j.1538-7305.1982.tb03439.x. S2CID  11290643.
17. Раншоус, Стивен; Джослин, Клифф; Крейлинг, Шон; Новак, Кэтлин; Саматова, Нагиза; Уэст, Кертис; Уинтерс, Сэмюэл (2017). Mining Exchange Pattern в направленном гиперграфе транзакций биткойнов (PDF) . Финансовая криптография и безопасность данных. Springer. doi :10.1007/978-3-319-70278-0_16. Архивировано (PDF) из оригинала 15.07.2021 . Получено 20.01.2021 .
18. Ausiello, Giorgio; Laura, Luigi (2017). «Направленные гиперграфы: Введение и фундаментальные алгоритмы — обзор». Теоретическая информатика . 658 : 293–306. doi : 10.1016/j.tcs.2016.03.016 .
19. Галло, Г.; Лонго, Г.; Паллоттино, С.; Нгуен, С. (1993). «Направленные гиперграфы и приложения». Дискретная прикладная математика . 42 (2–3): 177–201. doi : 10.1016/0166-218X(93)90045-P .
20. Сандер, Г. (2003), «Размещение направленных гиперграфов с ортогональными гиперребрами», Труды 11-го Международного симпозиума по рисованию графов (GD 2003) , Lecture Notes in Computer Science , т. 2912, Springer, стр. 381–6, ISBN 978-3-540-24595-7, архивировано из оригинала 2011-07-18 , извлечено 2010-05-17.
21. Эшбах, Томас; Гюнтер, Вольфганг; Беккер, Бернд (2006), «Рисование ортогонального гиперграфа для улучшения видимости» (PDF) , Журнал алгоритмов графов и приложений , 10 (2): 141–157, doi : 10.7155/jgaa.00122 , заархивировано (PDF) из оригинала 2011-07-18 , извлечено 2010-05-17.
22. Мякинен, Эркки (1990), «Как нарисовать гиперграф», Международный журнал компьютерной математики , 34 (3): 177–185, doi :10.1080/00207169008803875.
23. Берто, Франсуа; Идс, Питер (2001), «Рисование гиперграфов в стандарте подмножеств», Рисование графов , Lecture Notes in Computer Science, т. 1984, Springer-Verlag, стр. 45–76, doi : 10.1007/3-540-44541-2_15 , ISBN 978-3-540-41554-1.
24. Нахид Анджум, Арафат; Брессан, Стефан (2017), «Рисование гиперграфа с помощью силового размещения», Приложения к базам данных и экспертным системам , Конспект лекций по информатике, т. 10439, Springer International Publishing, стр. 387–394, doi :10.1007/978-3-319-64471-4_31, ISBN 978-3-319-64470-7.
25. Кауфманн, Майкл; ван Кревелд, Марк; Спекманн, Беттина (2009), «Чертежи подразделения гиперграфов», Рисование графика , Конспекты лекций по информатике, том. 5417, Springer-Verlag, стр. 396–407, номер документа : 10.1007/978-3-642-00219-9_39 , ISBN. 978-3-642-00218-2.
26. Джонсон, Дэвид С.; Поллак, ХО (2006), «Планарность гиперграфа и сложность рисования диаграмм Венна», Журнал теории графов , 11 (3): 309–325, doi :10.1002/jgt.3190110306.
27. Бучин, Кевин; ван Кревелд, Марк; Мейер, Хенк; Спекманн, Беттина; Вербек, Кевин (2010), «О плоских опорах для гиперграфов», Рисование графиков , Конспекты лекций по информатике, том. 5849, Springer-Verlag, стр. 345–356, doi : 10.1007/978-3-642-11805-0_33 , ISBN 978-3-642-11804-3.
28. "Виталий Волошин: Сайт по раскраске смешанных гиперграфов". spectrum.troy.edu . Архивировано из оригинала 2022-01-20 . Получено 2022-04-27 .
29. Фейгин, Рональд (1983-07-01). «Степени ацикличности для гиперграфов и схем реляционных баз данных». Журнал ACM . 30 (3): 514–550. doi : 10.1145/2402.322390 . ISSN  0004-5411.
30. Ловаш, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
31. Берге, Клод (1973). Графы и гиперграфы . Амстердам: Северная Голландия. ISBN 0-7204-2450-X.
32. Yu, CT; Özsoyoğlu, MZ (1979). «Алгоритм для членства в дереве распределенного запроса» (PDF) . Proc. IEEE COMPSAC : 306–312. doi :10.1109/CMPSAC.1979.762509. Архивировано (PDF) из оригинала 2018-09-02 . Получено 2018-09-02 .
33. Graham, MH (1979). «О всеобщем отношении». Технический отчет . Торонто, Онтарио, Канада: Университет Торонто.
34. Абитебул, С .; Халл, Р. Б.; Виану, В. (1995). Основы баз данных . Эддисон-Уэсли. ISBN 0-201-53771-0.
35. Тарьян, Р. Э .; Яннакакис, М. (1984). «Простые алгоритмы линейного времени для проверки хордальности графов, проверки ацикличности гиперграфов и выборочного сокращения ациклических гиперграфов». SIAM Journal on Computing . 13 (3): 566–579. doi :10.1137/0213035.
36. Фагин, Рональд (1983). «Степени ацикличности для гиперграфов и схем реляционных баз данных». Журнал ACM . 30 (3): 514–550. doi : 10.1145/2402.322390 . S2CID  597990.
37. Харари, Ф. (2018) [1969]. Теория графов. CRC Press. стр. 172. ISBN 978-0-429-96231-8. Архивировано из оригинала 2023-02-04 . Получено 2021-06-12 . Далее мы сформулируем теорему Элейн Добер, следствия которой описывают свойства линейно-симметричных графов. Обратите внимание на очевидное, но важное наблюдение, что каждый линейно-симметричный граф является линейно-регулярным.
38. Карипис, Г., Аггарвал, Р., Кумар, В. и Шекхар, С. (март 1999 г.), «Многоуровневое разбиение гиперграфа: приложения в области СБИС», IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 7 (1): 69–79, CiteSeerX 10.1.1.553.2367 , doi : 10.1109/92.748202. {{citation}}: CS1 maint: multiple names: authors list (link)
39. Хендриксон, Б., Колда, ТГ (2000), «Модели разбиения графов для параллельных вычислений», Параллельные вычисления (Представленная рукопись), 26 (12): 1519–1545, doi :10.1016/S0167-8191(00)00048-X, заархивировано из оригинала 26.01.2021 , извлечено 13.10.2018 .{{citation}}: CS1 maint: multiple names: authors list (link)
40. Catalyurek, UV; Aykanat, C. (1995). Модель гиперграфа для отображения повторных вычислений разреженных матрично-векторных произведений на мультикомпьютерах . Труды Международной конференции по высокопроизводительным вычислениям (HiPC'95).
41. Catalyurek, UV; Aykanat, C. (1999), «Разложение на основе гиперграфового разбиения для параллельного умножения векторов разреженных матриц», IEEE Transactions on Parallel and Distributed Systems , 10 (7): 673–693, CiteSeerX 10.1.1.67.2498 , doi : 10.1109/71.780863. 

Ссылки

• Берже, Клод (1984). Гиперграфы: комбинаторика конечных множеств. Elsevier. ISBN 978-0-08-088023-5.
• Берге, К.; Рэй-Чоудхури, Д. (2006). Семинар по гиперграфам: Университет штата Огайо, 1972. Конспект лекций по математике. Том 411. Springer. ISBN 978-3-540-37803-7.
• «Гиперграф», Энциклопедия математики , EMS Press , 2001 [1994]
• Бретто, Ален (2013). Теория гиперграфов: Введение. Springer. ISBN 978-3-319-00080-0.
• Волошин, Виталий И. (2002). Раскраска смешанных гиперграфов: теория, алгоритмы и приложения: теория, алгоритмы и приложения. Монографии Института Филдса. Том 17. Американское математическое общество. ISBN 978-0-8218-2812-0.
• Волошин, Виталий И. (2009). Введение в теорию графов и гиперграфов. Nova Science. ISBN 978-1-61470-112-5.
• В данной статье использованы материалы из hypergraph на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .

Внешние ссылки

• PAOHVis: система PAOHVis с открытым исходным кодом для визуализации динамических гиперграфов.