Сопоставление в гиперграфах

В теории графов паросочетанием в гиперграфе не называется набор гиперребер , в котором каждые два гиперребра пересекаются . Это расширение понятия сопоставления в графе . ^{[ 1 ]}^{: 466–470} ^{[ 2 ]}

Определение

Напомним, что H $—$ это пара $(V, E)$ , где $V$ — набор вершин гиперграф , а $E$ — набор подмножеств V $,$ называемых гиперребрами . Каждое гиперребро может содержать одну или несколько вершин.

Паросочетание — это в $H$ подмножество $M$ в $E$ такое, что каждые два гиперребра $e 1$ и $e 2$ в $M$ имеют пустое пересечение (не имеют общих вершин).

Число паросочетаний гиперграфа $H$ — это наибольший размер паросочетания в $H$ . Его часто обозначают $ν(H)$ . ^{[ 1 ]}^: 466 ^{[ 3 ]}

В качестве примера пусть $V$ будет набором ${1,2,3,4,5,6,7}.$ Рассмотрим 3-однородный гиперграф на $V$ (гиперграф, в котором каждое гиперребро содержит ровно 3 вершины). Пусть $H$ — 3-однородный гиперграф с 4 гиперребрами:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Тогда $H$ допускает несколько паросочетаний размера 2, например:

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

Однако в любом подмножестве из трех гиперребер по крайней мере два из них пересекаются, поэтому не существует паросочетания размера 3. Следовательно, число паросочетаний $H$ равно 2.

Пересекающийся гиперграф

Гиперграф $H = (V, E)$ называется пересекающимся , если каждые два гиперребра из $E$ имеют общую вершину. Гиперграф $H$ является пересекающимся тогда и только тогда, когда он не имеет совпадений с двумя или более гиперребрами, тогда и только тогда, когда $ν(H) = 1$ . ^{[ 4 ]}

Сопоставление на графике как частный случай

Граф без петель — это всего лишь 2-однородный гиперграф: каждое ребро можно рассматривать как набор из двух вершин, которые оно соединяет. Например, этот 2-однородный гиперграф представляет собой граф с 4 вершинами ${1,2,3,4}$ и 3 ребрами:

{ {1,3}, {1,4}, {2,4} }

Согласно приведенному выше определению, паросочетание в графе — это множество $M$ ребер, такое, что каждые два ребра в $M$ имеют пустое пересечение. Это эквивалентно тому, что никакие два ребра в $M$ не смежны с одной и той же вершиной; это и есть определение паросочетания в графе .

Дробное соответствие

Дробное паросочетание дробь из $[0,1]$ в гиперграфе — это функция, которая присваивает каждому гиперребру $так, что для каждой вершины v$ в $V$ сумма долей гиперребер, содержащих $v,$ не превосходит 1. Паросочетание — это специальное случай дробного паросочетания, в котором все дроби равны либо 0, либо 1. Размер дробного паросочетания представляет собой сумму дробей всех гиперребер.

Число дробного соответствия гиперграфа $H$ — это наибольший размер дробного соответствия в $H$ . Его часто обозначают $ν *(H)$ . ^{[ 3 ]}

Поскольку паросочетание является частным случаем дробного паросочетания, для каждого гиперграфа $H$ :

Число соответствия( $H$ ) ≤ дробное число соответствия( $H$ )

Символически этот принцип записан:

\nu (H)\leq \nu ^{*}(H)

В общем, дробное число совпадений может быть больше, чем число совпадений. Теорема Золтана Фюреди ^{[ 4 ]} обеспечивает верхние границы отношения дробного числа совпадений( $H$ совпадений ) / числа $( H$ ):

Если каждое гиперребро в $H$ содержит не более $r$ вершин, то

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$

В частности, на простом графике: ^{[ 5 ]}

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$

- Неравенство является точным: пусть $H r$ - однородная $r$ — конечная проективная плоскость . Тогда $ν (H r) = 1$ , поскольку любые два гиперребра пересекаются, и $ν *( H r ) = r – 1 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 1 / r ⁠$ дробным сопоставлением, которое присваивает вес $⁠ 1 / r ⁠$ каждому гиперребру (это паросочетание, поскольку каждая вершина содержится в $r$ гиперребра, а ее размер равен $r - 1 + ⁠ 1 / r ⁠$ поскольку существует $r 2 - r + 1$ гиперребро). Следовательно, соотношение равно $r - 1 + ⁠ 1 / r ⁠$ .
Если $r$ таково, что $r$ -однородная конечная проективная плоскость не существует (например, $r = 7$ ), то имеет место более сильное неравенство:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

Если $H$ r $-$ частично (вершины разбиты на $r$ частей и каждое гиперребро содержит вершину из каждой части), то:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

В частности, в двудольном графе $ν *(H) = ν (H)$ . Это доказал Андраш Дьярфас . ^{[ 4 ]}

- Неравенство является точным: пусть $H r-$ — усеченная проективная плоскость порядка $r - 1$ . Тогда $ν (H r -) = 1$ , поскольку любые два гиперребра пересекаются, и $ν *(H r -) = r - 1$ в результате дробного сопоставления, которое присваивает вес $⁠ 1 / r ⁠$ каждому гиперребру (существует $r 2 - r$ гиперребер).

Идеальное соответствие

Паросочетание $M$ называется совершенным , если каждая вершина $v$ из $V$ содержится ровно в одном гиперребре $M$ . Это естественное расширение понятия идеального паросочетания в графе.

Дробное паросочетание $M$ называется совершенным, если для каждой вершины $v$ из $V$ сумма долей гиперребер из $M,$ содержащих $v,$ равна ровно 1.

Рассмотрим гиперграф $H,$ в котором каждое гиперребро содержит не более $n$ вершин. Если $H$ допускает идеальное дробное паросочетание, то его число дробного паросочетания не менее $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}| В | ⁄ н$ . Если каждое гиперребро в $H$ содержит ровно $n$ вершин, то его дробное число совпадений равно точно $| V | ⁄ n$ . ^{[ 6 ]} ^{: сек.2} Это обобщение того факта, что в графе размер идеального паросочетания равен $| V | ⁄ 2$ .

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

Например, если $V = {1,2,3,a,b,c}$ и $E = { {1,a}, {2,a}, {1,b}, {2,b}, {3, c} },$ то $E$ сбалансировано с идеальным дробным сопоставлением ${ 1/2, 1/2, 1/2, 1/2, 1 }.$

Существуют различные достаточные условия существования совершенного паросочетания в гиперграфе:

Теоремы типа Холла для гиперграфов - представляют достаточные условия, аналогичные теореме о браке Холла, основанные на наборах соседей.
Идеальное паросочетание в гиперграфах высокой степени - представляет достаточные условия, аналогичные теореме Дирака о гамильтоновых циклах , основанные на степени вершин.
Киваш и Майкрофт разработали геометрическую теорию сопоставления гиперграфов. ^{[ 7 ]}

Сбалансированное семейство комплектов

Семейство множеств $E$ над основным множеством $V$ называется сбалансированным (относительно $V$ ), если гиперграф $H = (V, E)$ допускает совершенное дробное паросочетание. ^{[ 6 ]} ^{: сек.2}

Например, рассмотрим набор вершин $V = {1,2,3,a,b,c}$ и набор ребер $E = {1-a, 2-a, 1-b, 2-b, 3-c}.$ $E$ сбалансирован, поскольку существует идеальное дробное сопоставление с весами ${1/2, 1/2, 1/2, 1/2, 1}.$

Вычисление максимального соответствия

Задача нахождения паросочетания максимальной мощности в гиперграфе и вычисления таким образом $\nu (H)$ , является NP-трудным даже для 3-однородных гиперграфов (см. 3-мерное сопоставление ). Это контрастирует со случаем простых (2-однородных) графов, в которых вычисление сопоставления максимальной мощности может быть выполнено за полиномиальное время.

Соответствие и покрытие

Вершинное покрытие в гиперграфе $H = (V, E)$ — это подмножество $T$ в $V$ , такое, что каждое гиперребро в $E$ содержит хотя бы одну вершину $T$ (оно также называется трансверсальным или набором попаданий и эквивалентно комплект чехла ). Это обобщение понятия вершинного покрытия в графе.

Число вершинного покрытия гиперграфа $H$ — это наименьший размер вершинного покрытия в $H$ . Его часто обозначают $τ (H)$ , ^{[ 1 ]}^: 466 для поперечного.

Дробное вершинное покрытие — это функция, присваивающая вес каждой вершине в $V$ , такая, что для каждого гиперребра $e$ в $E$ сумма долей вершин в $e$ равна не менее 1. Вершинное покрытие — это частный случай дробной вершины. покрытие, в котором все веса равны либо 0, либо 1. Размер дробного вершинного покрытия равен сумме долей всех вершин.

Число дробного вершинного покрытия гиперграфа $H$ — это наименьший размер дробного вершинного покрытия в $H$ . Его часто обозначают $τ *(H)$ .

Поскольку вершинное покрытие является частным случаем дробного вершинного покрытия, для каждого гиперграфа $H$ :

дробное число вершинного покрытия ( $H$ ) ≤ число вершинного покрытия ( $H$ ).

Двойственность линейного программирования подразумевает, что для каждого гиперграфа $H$ :

дробное-число-соответствия ( $H$ ) = дробное-число-покрытия вершин ( $H$ ).

Следовательно, для каждого гиперграфа $H$ : ^{[ 4 ]}

\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)

Если размер каждого гиперребра в $H$ не превосходит $r$ , то объединение всех гиперребер в максимальном паросочетании является вершинным-покрытием (если бы существовало непокрытое гиперребро, мы могли бы добавить его в паросочетание). Поэтому:

\tau (H)\leq r\cdot \nu (H).

Это неравенство строго: равенство выполняется, например, когда $V$ содержит $r \cdot ν (H) + r - 1$ вершины, а $E$ содержит все подмножества из $r$ вершин.

Однако в общем случае $τ *(H) < r \cdot ν (H)$ , поскольку $ν * (H) < r \cdot ν (H)$ ; см . раздел «Дробное сопоставление» выше.

Гипотеза Райзера гласит, что в каждом $r$ -частичном $r$ -однородном гиперграфе:

\tau (H)\leq (r-1)\nu (H).

Некоторые частные случаи гипотезы доказаны; см . гипотезу Райзера .

собственность Кёнига

Гиперграф обладает свойством Кенига , если его максимальное число совпадений равно минимальному числу вершинного покрытия, а именно, если $ν (H) = τ (H)$ . Теорема Кенига-Эгервари показывает, что каждый двудольный граф обладает свойством Кенига. Чтобы распространить эту теорему на гиперграфы, нам нужно распространить на гиперграфы понятие двудольности. ^{[ 1 ]}^: 468

Естественным обобщением является следующее. Гиперграф называется 2-раскрашиваемым, если его вершины могут быть 2-цветными так, что каждое гиперребро (размером не менее 2) содержит хотя бы по одной вершине каждого цвета. Альтернативный термин — Свойство B. Простой граф является двудольным тогда и только тогда, когда он раскрашивается в 2 цвета. Однако существуют 2-раскрашиваемые гиперграфы без свойства Кенига. Например, рассмотрим гиперграф с $V = {1,2,3,4}$ со всеми тройками $E = { {1,2,3}, {1,2,4}, {1,3,4}, {2 ,3,4} }.$ Его можно раскрасить в 2 цвета, например, мы можем раскрасить ${1,2}$ в синий цвет, а ${3,4}$ — в белый. Однако его номер соответствия равен 1, а номер его вершинного покрытия — 2.

Более сильное обобщение состоит в следующем. Учитывая гиперграф $H = (V, E)$ и подмножество $V'$ из $V$ , ограничение H $V$ на $V'$ - это гиперграф, вершинами которого являются $V$ , и для каждого гиперребра $e$ в $E$ , которое пересекает $'$ , у него есть гиперребро $e '$ это пересечение $e$ и $V'$ . Гиперграф называется сбалансированным , если все его ограничения по существу раскрашиваются в 2 цвета . Это означает, что в ограничении мы игнорируем одноэлементные гиперребра. ^{[ 8 ]} Простой граф является двудольным тогда и только тогда, когда он сбалансирован.

Простой граф является двудольным тогда и только тогда, когда в нем нет циклов нечетной длины. Аналогично, гиперграф сбалансирован тогда и только тогда, когда в нем нет цепей нечетной длины . Схема длины $k$ гиперграфе — это чередующаяся последовательность $(v 1, e 1, v 2, e 2, \dots, v k, ek, k v в +1 = v 1)$ , где $v i$ — различные вершины и e $являются различными гиперребрами, и каждое гиперребро содержит i$ вершину слева и вершину справа. Схема называется несбалансированной , если каждое гиперребро не содержит других вершин схемы. Клод Берже доказал, что гиперграф сбалансирован тогда и только тогда, когда он не содержит несбалансированного контура нечетной длины. Каждый сбалансированный гиперграф обладает свойством Кенига. ^{[ 9 ]}^{[ 1 ]}^{: 468–470}

Следующие действия эквивалентны: ^{[ 1 ]}^{: 470–471}

Каждый частичный гиперграф $H$ (т. е. гиперграф, полученный из $H$ удалением некоторых гиперребер) обладает свойством Кенига.
Каждый частичный гиперграф $H$ обладает тем свойством, что его максимальная степень равна минимальному числу раскраски ребер .
$H$ обладает свойством Хелли , а граф пересечений $H$ (простой граф, в котором вершины — $E$ , а два элемента $E$ связаны тогда и только тогда, когда они пересекаются) является совершенным графом .

Соответствие и упаковка

Проблема упаковки множеств эквивалентна сопоставлению гиперграфов.

в Упаковка вершин (простом) графе — это такое подмножество $P$ его вершин, что никакие две вершины в $P$ не являются смежными.

Задача нахождения максимальной упаковки вершин в графе эквивалентна задаче нахождения максимального паросочетания в гиперграфе: ^{[ 1 ]}^: 467

гиперграфа $H = (V, E)$ определите его граф пересечений $Int(H)$ простой граф, вершины которого — $,$ а ребра — пары $(e1 Для, e2 такие),$ что $e1 как$ , $e2 E$ имеют вершину в общий. Тогда каждое паросочетание в $H$ является упаковкой вершин в $Int(H)$ и наоборот.
Для данного графа $G = (V', E')$ определите его звездный гиперграф $St(G)$ как гиперграф, вершины которого — $E'$ , а гиперребра — звезды вершин $G$ (т. е. для каждой вершины $v'$ в $V '$ существует гиперребро $, в St(G)$ , содержащее все ребра из $E'$ , смежные с $v'$ ). Тогда каждая упаковка вершин в $G$ является паросочетанием в $St(G)$ и наоборот.
Альтернативно, для данного графа $G = (V', E')$ определите его клик $Cl(G)$ как гиперграф, вершины которого являются кликами G $гиперграф$ , и для каждой вершины $v'$ в $V'$ существует гиперребро в $Cl (G),$ содержащий все клики в $G$ , содержащие $v'$ . Опять же, каждая упаковка вершин в $G$ является паросочетанием в $Cl(G)$ , и наоборот. Обратите внимание, что $Cl(G)$ не может быть построен из $G$ за полиномиальное время , поэтому его нельзя использовать в качестве сокращения для доказательства NP-трудности. Но у него есть некоторые теоретические применения.

См. также

Трехмерное сопоставление - частный случай сопоставления гиперграфа с 3-однородными гиперграфами.
Вершинное покрытие в гиперграфах
Двудольный гиперграф
Сопоставление радуги в гиперграфах
D-интервальный гиперграф — бесконечный гиперграф, в котором существует некоторая связь между паросочетанием и покрывающим числом.
Теорема Эрдеша–Ко–Радо о попарно непересекающихся ребрах в гиперграфах

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
^ Берже, Клод (1973). Графики и гиперграфы . Амстердам: Северная Голландия.
^ Перейти обратно: ^а ^б Ахарони, Рон; Кесслер, Офра (15 октября 1990 г.). «О возможном распространении теоремы Холла на двудольные гиперграфы» . Дискретная математика . 84 (3): 309–313. дои : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
^ Перейти обратно: ^а ^б ^с ^д Фюреди, Золтан (1 июня 1981 г.). «Максимальная степень и дробные паросочетания в однородных гиперграфах». Комбинаторика . 1 (2): 155–162. дои : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .
^ Ловас, Л. (1974). «Теоремы о минимаксе для гиперграфов». В Берже, Клод; Рэй-Чаудхури, Диджен (ред.). Семинар по гиперграфике . Конспект лекций по математике. Том. 411. Берлин, Гейдельберг: Шпрингер. стр. 111–126. дои : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7 .
^ Перейти обратно: ^а ^б Найман, Кэтрин; Су, Фрэнсис Эдвард; Зербиб, Шира (02 января 2020 г.). «Справедливое деление на несколько частей» . Дискретная прикладная математика . 283 : 115–122. arXiv : 1710.09477 . дои : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
^ Киваш, Питер; Майкрофт, Ричард (1 января 2015 г.). Геометрическая теория сопоставления гиперграфов . Мемуары Американского математического общества. Том. 233. Американское математическое общество. ISBN 978-1-4704-0965-4 .
^ Берге, КЛОД (1973-01-01), Шривастава, ЯГДИШ Н. (редактор), «ГЛАВА 2 – Сбалансированные гиперграфы и некоторые приложения к теории графов» , Обзор комбинаторной теории , Северная Голландия, стр. 15–23 , ISBN 978-0-7204-2262-7 , получено 19 июня 2020 г.
^ Берже, Клод; Верньяс, Мишель ЛАС (1970). «Теоремы о типе Кенига для гиперграфов». Анналы Нью-Йоркской академии наук . 175 (1): 32–40. Бибкод : 1970NYASA.175...32B . дои : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .

[lp-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549

[2] Берже, Клод (1973). Графики и гиперграфы . Амстердам: Северная Голландия.

[:1-3] Перейти обратно: ^а ^б Ахарони, Рон; Кесслер, Офра (15 октября 1990 г.). «О возможном распространении теоремы Холла на двудольные гиперграфы» . Дискретная математика . 84 (3): 309–313. дои : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .

[:2-4] Перейти обратно: ^а ^б ^с ^д Фюреди, Золтан (1 июня 1981 г.). «Максимальная степень и дробные паросочетания в однородных гиперграфах». Комбинаторика . 1 (2): 155–162. дои : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .

[5] Ловас, Л. (1974). «Теоремы о минимаксе для гиперграфов». В Берже, Клод; Рэй-Чаудхури, Диджен (ред.). Семинар по гиперграфике . Конспект лекций по математике. Том. 411. Берлин, Гейдельберг: Шпрингер. стр. 111–126. дои : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7 .

[:0-6] Перейти обратно: ^а ^б Найман, Кэтрин; Су, Фрэнсис Эдвард; Зербиб, Шира (02 января 2020 г.). «Справедливое деление на несколько частей» . Дискретная прикладная математика . 283 : 115–122. arXiv : 1710.09477 . дои : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .

[7] Киваш, Питер; Майкрофт, Ричард (1 января 2015 г.). Геометрическая теория сопоставления гиперграфов . Мемуары Американского математического общества. Том. 233. Американское математическое общество. ISBN 978-1-4704-0965-4 .

[8] Берге, КЛОД (1973-01-01), Шривастава, ЯГДИШ Н. (редактор), «ГЛАВА 2 – Сбалансированные гиперграфы и некоторые приложения к теории графов» , Обзор комбинаторной теории , Северная Голландия, стр. 15–23 , ISBN 978-0-7204-2262-7 , получено 19 июня 2020 г.

[9] Берже, Клод; Верньяс, Мишель ЛАС (1970). «Теоремы о типе Кенига для гиперграфов». Анналы Нью-Йоркской академии наук . 175 (1): 32–40. Бибкод : 1970NYASA.175...32B . дои : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]