Гиперграф

Пример неориентированного гиперграфа с и . Этот гиперграф имеет порядок 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 H}$${\ Displaystyle H = (X, E)}$${\ displaystyle X}$${\ displaystyle E}$${\ displaystyle X}$${\ displaystyle E}$${\ Displaystyle {\ mathcal {P}} (X) \ setminus \ {\ emptyset \}}$${\ Displaystyle {\ mathcal {P}} (X)}$${\ displaystyle X}$

Направленный гиперграф отличается тем, что его гиперребра - это не множества, а упорядоченная пара подмножеств , составляющих хвост и голову гиперребра.${\ displaystyle X}$

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

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

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

Набор гиперграфов - это категория с гомоморфизмами гиперграфов в качестве морфизмов .

Приложения [ править ]

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

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

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

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

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

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

Рисунок гиперграфа [ править ]

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

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

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

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

Раскраска гиперграфа [ править ]

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

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

Есть много обобщений классической раскраски гиперграфов. Один из них - это так называемая смешанная раскраска гиперграфов, когда допускаются одноцветные ребра. Некоторые смешанные гиперграфы невозможно раскрасить в любое количество цветов. Общий критерий неокрашиваемости неизвестен. Когда смешанный гиперграф можно раскрашивать, минимальное и максимальное количество используемых цветов называются нижним и верхним хроматическими числами соответственно. Подробнее см. Http://spectrum.troy.edu/voloshin/mh.html .

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

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

• Пустой - без краев.
• Непростой (или несколько ) - имеют петлю (гиперребру с одной вершиной) или повторяющиеся ребра, что означает , что может быть два или более ребер , содержащих один и тот же набор вершин.
• Простой - без петель и повторяющихся краев.
• ${\ displaystyle d}$-регулярно - каждая вершина имеет степень , т. е. содержится ровно в гиперребрах.${\ displaystyle d}$${\ displaystyle d}$
• 2-раскрашиваемый - его вершины можно разбить на два класса U и V таким образом, чтобы каждое гиперребро мощности не менее 2 содержало хотя бы одну вершину из обоих классов. Альтернативный термин является свойством В .
  • Два более сильных свойства - двудольные и сбалансированные .
• ${\ displaystyle k}$-равномерно - каждое гиперребро содержит ровно вершины.${\ displaystyle k}$
• ${\ displaystyle k}$-частный - вершины разбиты на части, и каждое гиперребро содержит ровно по одной вершине каждого типа.${\ displaystyle k}$
  • Любой -дольный гиперграф (для ) является как -равномерным, так и двудольным (и 2-раскрашиваемым).${\ displaystyle k}$${\ Displaystyle к \ geq 2}$${\ displaystyle k}$
• Замкнутый вниз - каждое подмножество ребер неориентированного гиперграфа также является гиперребром. Замкнутый вниз гиперграф обычно называют абстрактным симплициальным комплексом .
  • Абстрактный симплициальный комплекс с дополнительным свойством, называемым свойством увеличения, называется матроидом .

Связанные гиперграфы [ править ]

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

Пусть - гиперграф, состоящий из вершин${\ 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}\land e_{i}\subseteq X\land e_{i}\neq \emptyset \rbrace ,}$

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

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

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

Альтернативный термин является ограничение H на A . ^{[26] : 468}

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

Частичная Гиперграф является Гиперграфом с некоторыми удаленными краями. ^{[26] : 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}\land 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 и из Н , таким образом, что каждая компонента связности G « из G представляет собой множество соответствующего Н» .

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

Матрица заболеваемости [ править ]

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

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

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

Транспонирования из инцидентности матрицы определяет гиперграф называется двойным из , где является м - элементное множество и является п - элементное множество подмножеств . Ибо и тогда и только тогда, когда .${\displaystyle A^{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 a_{ij}=1}$

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

${\displaystyle a_{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 ₁ содержится в ребре e ₁ в H .

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

Циклы [ править ]

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

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

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

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

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

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

Изоморфизм, симметрия и равенство [ править ]

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

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

Симметрия [ править ]

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

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

Двойник равномерного гиперграфа регулярен, и наоборот.

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

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

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

Разделы [ править ]

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

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

Разделение графа (и, в частности, разделение гиперграфа) имеет множество приложений для проектирования микросхем ^[34] и параллельных вычислений. ^{[35] [36] [37]} Эффективные и масштабируемые алгоритмы разделения гиперграфов также важны для обработки крупномасштабных гиперграфов в задачах машинного обучения. ^[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}}$

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

См. Также [ править ]

Викискладе есть медиафайлы по теме гиперграфов .

• Комбинаторный дизайн
• Факторный график
• Жадоид
• Структура заболеваемости
• Мультиграф
• Система P
• Умножение разреженной матрицы на вектор

Заметки [ править ]

Ссылки [ править ]

• Клод Берже, "Гиперграфы: комбинаторика конечных множеств". Северная Голландия, 1989 г.
• Клод Бердж, Диджен Рэй-Чаудхури, "Семинар по гиперграфам, Университет штата Огайо, 1972 г.", Конспект лекций по математике 411 Springer-Verlag
• «Гиперграф» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Ален Бретто, "Теория гиперграфа: введение", Springer, 2013.
• Виталий Иванович Волошин. «Раскраска смешанных гиперграфов: теория, алгоритмы и приложения». Монографии Института Филдса, Американское математическое общество, 2002.
• Виталий Иванович Волошин. «Введение в теорию графов и гиперграфов». Nova Science Publishers, Inc. , 2009.
• Эта статья включает материал из гиперграфа на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .

Внешние ссылки [ править ]

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