Гиперграф

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

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

Согласно одному определению, неориентированный гиперграф — это ориентированный гиперграф, имеющий симметричное множество ребер: If then . Для простоты обозначений можно удалить «дубликаты» гиперребра, поскольку модификатор «ненаправленный» точно сообщает нам о их существовании: «Если тогда где » означает неявно в . ${\displaystyle (X,E)}$ ${\displaystyle (D,C)\in E}$ ${\displaystyle (C,D)\in E}$ ${\displaystyle (D,C)\in E}$ ${\displaystyle (C,D){\vec {\in }}E}$ ${\displaystyle {\vec {\in }}}$

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

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

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

Совокупность гиперграфов — это категория , морфизмами которой являются гомоморфизмы гиперграфов .

Приложения

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

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

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

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

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

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

Гиперграфический рисунок

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

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

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

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

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

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

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

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

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

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

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

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

• Пустой – не имеет краев.
• Непростой (или множественный ) — имеет петли (гиперребра с одной вершиной) или повторяющиеся ребра, что означает, что может быть два или более ребер, содержащих один и тот же набор вершин.
• Простой – не имеет петель и повторяющихся краев.
• ${\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}$
• Сокращенный : ^[28] ни одно гиперребро не является строгим подмножеством другого гиперребра; эквивалентно, каждое гиперребро максимально для включения. Редукция гиперграфа — это уменьшенный гиперграф, полученный удалением каждого гиперребра, входящего в другое гиперребро .
• Замкнутость вниз - каждое подмножество ребер неориентированного гиперграфа также является гиперребром. Замкнутый вниз гиперграф обычно называют абстрактным симплициальным комплексом . Обычно оно не сокращается, если только все гиперребра не имеют мощности 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. ^{[29] : 468}

Расширением подгиперграфа называется гиперграф, в котором каждое гиперребро, частично содержащееся в подгиперграфе , полностью содержится в расширении . Формально ${\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 }$

Частичный гиперграф — это гиперграф, у которого удалены некоторые ребра. ^{[29] : 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}$

Для ориентированного гиперграфа головы и хвосты каждого гиперребра обозначаются и соответственно. ^[18] где ${\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 , а ( x1 _, e1 ₎ соединены с ребром тогда и только тогда, когда вершина x1 _{содержится} в ребре e. ₁ в Х. _

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

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

Параллель для матрицы смежности гиперграфа можно провести из матрицы смежности графа. В случае графа матрица смежности представляет собой квадратную матрицу, которая указывает, являются ли пары вершин смежными . Аналогичным образом мы можем определить матрицу смежности для гиперграфа в общем случае, где гиперребра имеют действительные веса с ${\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.}$

Циклы

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

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

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

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

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

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

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

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

Гиперграф изоморфен гиперграфу , записанному так, как будто существует биекция ${\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}}$

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

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

Перегородки

Теорема о разбиении Э. Даубера ^[36] утверждает, что для реберно-транзитивного гиперграфа существует разбиение ${\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)}$

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

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

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

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

Для такого гиперграфа членство во множестве обеспечивает упорядочение, но это упорядочение не является ни частичным порядком , ни предварительным порядком , поскольку оно не является транзитивным. Граф, соответствующий графу Леви этого обобщения, является ориентированным ациклическим графом . Рассмотрим, например, обобщенный гиперграф, набор вершин которого равен , а ребра — и . Тогда, хотя и , это неверно . Однако транзитивное замыкание членства в множестве для таких гиперграфов действительно вызывает частичный порядок и «сглаживает» гиперграф в частично упорядоченное множество . ${\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}}$

Альтернативно, ребрам может быть разрешено указывать на другие ребра, независимо от требования, чтобы ребра были упорядочены как ориентированные ациклические графы. Это позволяет создавать графы с петлями ребер, которые вообще не обязательно должны содержать вершины. Например, рассмотрим обобщенный гиперграф, состоящий из двух ребер и и нулевых вершин, так что и . Поскольку этот цикл бесконечно рекурсивен, множества, являющиеся ребрами, нарушают аксиому Foundation . В частности, для таких гиперграфов не существует транзитивного замыкания принадлежности множеству. Хотя на первый взгляд такие структуры могут показаться странными, их можно легко понять, заметив, что эквивалентное обобщение их графа Леви больше не является двудольным , а представляет собой просто некоторый общий ориентированный граф . ${\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-график
• Комбинаторный дизайн
• Факторный график
• Гридоид
• Структура заболеваемости
• Мультиграф
• П-система
• Умножение разреженной матрицы на вектор
• сеть Петри

Примечания

1. Вальдивия, Паола; Буоно, Паоло; Плезант, Кэтрин; Дюфурно, Николь; Фекете, Жан-Даниэль (2020). «Анализ динамических гиперграфов с помощью параллельной агрегированной визуализации упорядоченных гиперграфов» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . IEEE. 26 (1): 12. doi :10.1109/TVCG.2019.2933196. eISSN  1941-0506. ISSN  1077-2626. PMID  31398121. S2CID  199518871. Архивировано (PDF) из оригинала 26 января 2021 г. Проверено 8 сентября 2020 г.
2. Хаусслер, Дэвид ; Вельцль, Эмо (1987), «ε-сети и запросы симплексного диапазона», Дискретная и вычислительная геометрия , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR  0884223.
3. Перл, Иудея (1984). Эвристика: стратегии интеллектуального поиска для решения компьютерных задач. Издательство Аддисон-Уэсли. п. 25. ISBN 978-0-201-05594-8. Архивировано из оригинала 4 февраля 2023 г. Проверено 12 июня 2021 г.
4. Файги, Уриэль; Ким, Чон Хан; Офек, Эран (2006). Свидетели невыполнимости плотных случайных формул 3КНФ. 47-й ежегодный симпозиум IEEE по основам информатики (FOCS'06). IEEE. стр. 497–508. дои : 10.1109/FOCS.2006.78. Архивировано из оригинала 27 января 2021 г. Проверено 20 января 2021 г.
5. Бери, К.; Феджин, Р .; Майер, Д.; Яннакакис, М. (1983). «О желательности ациклических схем баз данных» (PDF) . Журнал АКМ . 30 (3): 479–513. дои : 10.1145/2402.322389. S2CID  2418740. Архивировано (PDF) из оригинала 21 апреля 2021 г. Проверено 03 января 2021 г.
6. Хуан, Цзинь; Чжан, Руй; Ю, Джеффри Сюй (2015). «Масштабируемое обучение и обработка гиперграфов». Международная конференция IEEE по интеллектуальному анализу данных 2015 г. (PDF) . стр. 775–780. дои : 10.1109/ICDM.2015.33. ISBN 978-1-4673-9504-5. S2CID  5130573. Архивировано (PDF) из оригинала 26 января 2021 г. Проверено 08 января 2021 г.
7. Бразилия, М; Захариасен, М (2015). «Деревья Штейнера в графах и гиперграфах». Оптимальные деревья связности на плоскости . Алгоритмы и комбинаторика. Том. 29. Спрингер. стр. 301–317. дои : 10.1007/978-3-319-13915-9_5. ISBN 978-3-319-13915-9. Архивировано из оригинала 29 января 2021 г. Проверено 20 января 2021 г.
8. Чжоу, Дэнъюн; Хуан, Цзяюань; Шолкопф, Бернхард (2006), «Обучение с помощью гиперграфов: кластеризация, классификация и внедрение», « Достижения в области нейронных систем обработки информации» , MIT Press, стр. 1601–8, ISBN 9780262256919, заархивировано из оригинала 22 октября 2021 г. , получено 24 июля 2021 г.
9. Гошал, Гураб; Златич, Винко; Кальдарелли, Гвидо; Ньюман, Марк Э.Дж. (2009), «Случайные гиперграфы и их приложения», Physical Review E , 79 (6): 066118, arXiv : 0903.0419 , Bibcode : 2009PhRvE..79f6118G, doi : 10.1103/PhysRevE.79.066118, PMID  196585 75, С2КИД  6391099
10. Тан, Шулун; Бу, Цзяцзюнь; Чен, Чун; Сюй, Бин; Ван, Джан; Он, Сяофэй (октябрь 2011 г.), «Использование обширной информации из социальных сетей для рекомендаций по музыке с помощью модели гиперграфа», Транзакции ACM в области мультимедийных вычислений, коммуникаций и приложений , 7S (1), статья 22, Бибкод : 2011smma.book..213T, doi : 10.1145/2037676.2037679, S2CID  432036
11. Лю, Циншань; Хуан, Ючи; Метаксас, Димитрис Н. (2013), «Гиперграф с выборкой для поиска изображений», Распознавание образов , 44 (10–11): 2255–2262, doi :10.1016/j.patcog.2010.07.014
12. Патро, Роб; Кингсофорд, Карл (2013), «Прогнозирование белковых взаимодействий с помощью экономного вывода истории сети», Bioinformatics , 29 (10–11): 237–246, doi : 10.1093/bioinformatics/btt224, PMC 3694678 , PMID  23812989 
13. Гао, Вт; Ван, Мэн; Чжа, Чжэн-Цзюнь; Шен, Цзяли; Ли, Сюэлун; Ву, Синдонг (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 сентября 2017 г. , получено 22 сентября 2017 г.
14. Тиан, Зе; Хван, Тэхён; Куанг, Руи (2009), «Алгоритм обучения на основе гиперграфа для классификации экспрессии генов и данных массива CGH с предварительным знанием», Bioinformatics , 25 (21): 2831–2838, doi : 10.1093/bioinformatics/btp467 , PMID  19648139
15. Гольдштейн, А. (1982). «База данных направленного гиперграфа: модель местной телефонной станции». Технический журнал Bell System . 61 (9): 2529–54. doi :10.1002/j.1538-7305.1982.tb03439.x. S2CID  11290643.{{cite journal}}: CS1 maint: date and year (link)
16. Раншоус, Стивен; Джослин, Клифф; Крейлинг, Шон; Новак, Кэтлин; Саматова, Нагиза; Уэст, Кертис; Уинтерс, Сэмюэл (2017). Анализ шаблонов обмена в гиперграфе, ориентированном на биткойн-транзакции (PDF) . Финансовая криптография и безопасность данных. Спрингер. дои : 10.1007/978-3-319-70278-0_16. Архивировано (PDF) из оригинала 15 июля 2021 г. Проверено 20 января 2021 г.
17. Аузиелло, Джорджио; Лаура, Луиджи (2017). «Направленные гиперграфы: Введение и фундаментальные алгоритмы - Обзор». Теоретическая информатика . 658 : 293–306. дои : 10.1016/j.tcs.2016.03.016 .
18. Галло, Г.; Лонго, Г.; Паллоттино, С.; Нгуен, С. (1993). «Направленные гиперграфы и приложения». Дискретная прикладная математика . 42 (2–3): 177–201. дои : 10.1016/0166-218X(93)90045-P .
19. Сандер, Г. (2003), «Расположение ориентированных гиперграфов с ортогональными гиперребрами», Proc. 11-й Международный симпозиум по рисованию графов (GD 2003) , Конспекты лекций по информатике , том. 2912, Springer, стр. 381–6, ISBN. 978-3-540-24595-7, заархивировано из оригинала 18 июля 2011 г. , получено 17 мая 2010 г..
20. Эшбах, Томас; Гюнтер, Вольфганг; Беккер, Бернд (2006), «Чертеж ортогонального гиперграфа для улучшения видимости» (PDF) , Journal of Graph Algorithms and Applications , 10 (2): 141–157, doi : 10.7155/jgaa.00122 , заархивировано (PDF) из оригинала 18 июля 2011 г. , получено 17 мая 2010 г..
21. Мякинен, Эркки (1990), «Как нарисовать гиперграф», Международный журнал компьютерной математики , 34 (3): 177–185, doi : 10.1080/00207169008803875.
22. Берто, Франсуа; Идс, Питер (2001), «Рисование гиперграфов в стандарте подмножества», Рисование графиков , Конспекты лекций по информатике, том. 1984, Springer-Verlag, стр. 45–76, номер документа : 10.1007/3-540-44541-2_15 , ISBN. 978-3-540-41554-1.
23. Нахид Анджум, Арафат; Брессан, Стефан (2017), «Рисование гиперграфа путем принудительного размещения», Приложения для баз данных и экспертных систем , Конспекты лекций по информатике, том. 10439, Springer International Publishing, стр. 387–394, номер номера : 10.1007/978-3-319-64471-4_31, ISBN. 978-3-319-64470-7.
24. Кауфманн, Майкл; ван Кревелд, Марк; Спекманн, Беттина (2009), «Чертежи подразделения гиперграфов», Рисование графика , Конспекты лекций по информатике, том. 5417, Springer-Verlag, стр. 396–407, номер документа : 10.1007/978-3-642-00219-9_39 , ISBN. 978-3-642-00218-2.
25. Джонсон, Дэвид С .; Поллак, Х.О. (2006), «Планарность гиперграфа и сложность рисования диаграмм Венна», Journal of Graph Theory , 11 (3): 309–325, doi :10.1002/jgt.3190110306.
26. Бучин, Кевин; ван Кревелд, Марк; Мейер, Хенк; Спекманн, Беттина; Вербек, Кевин (2010), «О плоских опорах для гиперграфов», Рисование графиков , Конспекты лекций по информатике, том. 5849, Springer-Verlag, стр. 345–356, doi : 10.1007/978-3-642-11805-0_33 , ISBN 978-3-642-11804-3.
27. "Виталий Волошин: Сайт смешанной раскраски гиперграфов" . Spectrum.troy.edu . Архивировано из оригинала 20 января 2022 г. Проверено 27 апреля 2022 г.
28. Феджин, Рональд (1 июля 1983). «Степени ацикличности гиперграфов и схем реляционных баз данных». Журнал АКМ . 30 (3): 514–550. дои : 10.1145/2402.322390 . ISSN  0004-5411.
29. Ловаш, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
30. Берже, Клод (1973). Графики и гиперграфы . Амстердам: Северная Голландия. ISBN 0-7204-2450-Х.
31. Ю, Коннектикут; Озсойоглу, МЗ (1979). «Алгоритм членства в дереве распределенного запроса» (PDF) . Учеб. IEEE КОМПСАК : 306–312. дои : 10.1109/CMPSAC.1979.762509. Архивировано (PDF) из оригинала 2 сентября 2018 г. Проверено 2 сентября 2018 г.
32. Грэм, Миннесота (1979). «О всеобщем отношении». Технический отчет . Торонто, Онтарио, Канада: Университет Торонто.
33. Абитебул, С .; Халл, РБ; Виану, В. (1995). Основы баз данных . Аддисон-Уэсли. ISBN 0-201-53771-0.
34. Тарьян, RE ; Яннакакис, М. (1984). «Простые алгоритмы с линейным временем для проверки хордльности графов, проверки ацикличности гиперграфов и выборочного сокращения ациклических гиперграфов». SIAM Journal по вычислительной технике . 13 (3): 566–579. дои : 10.1137/0213035.
35. Феджин, Рональд (1983). «Степени ацикличности гиперграфов и схем реляционных баз данных». Журнал АКМ . 30 (3): 514–550. дои : 10.1145/2402.322390 . S2CID  597990.
36. Харари, Ф. (2018) [1969]. Теория графов. ЦРК Пресс. п. 172. ИСБН 978-0-429-96231-8. Архивировано из оригинала 4 февраля 2023 г. Проверено 12 июня 2021 г. Далее мы сформулируем теорему Илэйн Даубер, следствия которой описывают свойства линейно-симметричных графов. Обратите внимание на очевидное, но важное наблюдение: любой линейно-симметричный граф является линейно-регулярным.
37. Карипис Г., Аггарвал Р., Кумар В. и Шекхар С. (март 1999 г.), «Многоуровневое разделение гиперграфов: приложения в области СБИС», Транзакции IEEE в системах очень большой интеграции (СБИС) , 7 (1): 69–79, CiteSeerX 10.1.1.553.2367 , doi : 10.1109/92.748202. {{citation}}: CS1 maint: multiple names: authors list (link)
38. Хендриксон, Б., Колда, Т.Г. (2000), «Модели разделения графов для параллельных вычислений», Parallel Computing (представленная рукопись), 26 (12): 1519–1545, doi : 10.1016/S0167-8191(00)00048- X, заархивировано из оригинала 26 января 2021 г. , получено 13 октября 2018 г.{{citation}}: CS1 maint: multiple names: authors list (link)
39. Каталюрек, УФ; Айканат, К. (1995). Модель гиперграфа для отображения повторяющихся вычислений разреженной матрицы и векторного произведения на мультикомпьютерах . Учеб. Международная конференция по высокопроизводительным вычислениям (HiPC'95).
40. Каталюрек, УФ; Айканат, К. (1999), «Разложение на основе гиперграфического разделения для параллельного умножения векторов с разреженной матрицей», Транзакции IEEE в параллельных и распределенных системах , 10 (7): 673–693, CiteSeerX 10.1.1.67.2498 , doi : 10.1109 /71.780863. 

Рекомендации

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

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

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