Сопоставление в гиперграфах - Matching in hypergraphs

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

Определение

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

А соответствие в ЧАС это подмножество M из E, так что каждые два гиперребра е₁ и е₂ в M имеют пустое пересечение (не имеют общей вершины).

В совпадающий номер гиперграфа ЧАС это самый большой размер соответствия в ЧАС. Часто обозначается как ${ displaystyle nu (H)}$ .^[1]^:466 ^[3]

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

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

потом ЧАС допускает несколько совпадений размера 2, например:

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

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

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

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

График без петли это просто 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. размер дробного сопоставления - это сумма долей всех гиперребер.

В дробное совпадение числа гиперграфа ЧАС - наибольший размер дробного соответствия в ЧАС. Часто обозначается как ${ Displaystyle ню ^ {*} (Н)}$ .^[3]

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

совпадающий номер (ЧАС) ≤ дробное-совпадающее-число (ЧАС);

В символах:

${ Displaystyle Nu (H) Leq Nu ^ {*} (H).}$

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

Если каждое гиперребро в ЧАС содержит не более р вершины, то ${ Displaystyle nu ^ {*} (H) / nu (H) Leq r-1 + 1 / r}$ ${ Displaystyle Nu ^ {*} (H) / Nu (H) Leq r-1 + 1 / r}$ . В частности, в простом графе ${ Displaystyle Nu ^ {*} (H) / Nu (H) Leq 3/2}$ ${ Displaystyle Nu ^ {*} (H) / Nu (H) Leq 3/2}$ .^[5]
- Неравенство точное: пусть ЧАС_р быть р-униформа конечная проективная плоскость. потом ${ displaystyle nu (H_ {r}) = 1}$ так как каждые два гиперребра пересекаются, и ${ displaystyle nu ^ {*} (H_ {r}) = r-1 + 1 / r}$ дробным соответствием, которое присваивает вес 1 /р каждому гиперребру (это паросочетание, поскольку каждая вершина содержится в р гиперребер, а его размер составляет р-1+1/р так как есть р²-р+1 гиперребра). Следовательно, соотношение точно р-1+1/р.
Если р такова, что р-униформа конечная проективная плоскость не существует (например, р= 7), то имеет место более сильное неравенство: ${ Displaystyle Nu ^ {*} (H) / Nu (H) Leq R-1}$ .
Если ЧАС является р-частный (- вершины разбиты на р частей и каждое гиперребро содержит по вершине из каждой части), то ${ displaystyle nu ^ {*} (H) / nu (H) leq r-1.}$ ${ displaystyle nu ^ {*} (H) / nu (H) leq r-1.}$ В частности, в двудольном графе ${ Displaystyle nu ^ {*} (H) = nu (H)}$ ${ displaystyle nu ^ {*} (H) = nu (H)}$ . Это было доказано Андраш Дьярфас.^[4]
- Неравенство точное: пусть ЧАС_р- быть усеченная проективная плоскость порядка р-1. потом ${ Displaystyle ню (Н_ {г -}) = 1}$ так как каждые два гиперребра пересекаются, и ${ displaystyle nu ^ {*} (H_ {r -}) = r-1}$ дробным соответствием, которое присваивает вес 1 /р к каждому гиперребру (есть р²-р гиперребра).

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

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

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

Рассмотрим гиперграф ЧАС в котором каждое гиперребро содержит не более п вершины. Если ЧАС допускает совершенное дробное соответствие, то его дробное соответствие не менее | V | /п. Если каждое гиперребро в ЧАС содержит точно п вершин, то его дробное число совпадений точно равно | V | /п.^[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]

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

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

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

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

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

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

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

Подбор и покрытие

А вершинное покрытие в гиперграфе ЧАС = (V, E) является подмножеством Т из V, так что каждое гиперребро в E содержит хотя бы одну вершину Т (его еще называют поперечный или ударная установка, и эквивалентен установить обложку ). Это обобщение понятия крышка вершины в графике.

В номер вершинного покрытия гиперграфа ЧАС наименьший размер вершинного покрытия в ЧАС. Часто обозначается как ${ Displaystyle тау (Н)}$ ,^[1]^:466 для поперечной.

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

В дробное число вершинного покрытия гиперграфа ЧАС - наименьший размер дробного вершинного покрытия в ЧАС. Часто обозначается как ${ Displaystyle тау ^ {*} (Н)}$ .

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

дробное-вершинное-покрытие-число (ЧАС) ≤ номер-покрытия-вершины (ЧАС).

Двойственность линейного программирования следует, что для любого гиперграфа ЧАС:

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

Следовательно, для любого гиперграфа ЧАС:^[4]

${ Displaystyle Nu (H) Leq Nu ^ {*} (H) = tau ^ {*} (H) Leq tau (H)}$

Если размер каждого гиперребра в ЧАС самое большее р тогда объединение всех гиперребер в максимальном паросочетании является вершинным покрытием (если бы было непокрытое гиперребро, мы могли бы добавить его в паросочетание). Следовательно:

${ Displaystyle тау (ЧАС) Leq г CDOT Nu (Н)}$ .

Это неравенство жесткое: равенство выполняется, например, когда V содержит ${ Displaystyle г CDOT ню (Н) + г-1}$ вершины и E содержит все подмножества р вершины.

Однако в целом ${ Displaystyle тау ^ {*} (Н) <г CDOT Nu (Н)}$ , поскольку ${ Displaystyle ню ^ {*} (ЧАС) <г CDOT НЮ (Н)}$ ; увидеть Дробное соответствие над.

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

${ Displaystyle тау (ЧАС) Leq (г-1) ню (Н)}$ .

Доказаны некоторые частные случаи гипотезы; увидеть Гипотеза Райзера.

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

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

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

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

Простой граф двудольный тогда и только тогда, когда он не имеет циклов нечетной длины. Точно так же гиперграф сбалансирован тогда и только тогда, когда он не имеет нечетной длины. схемы. Цепь длины k в гиперграфе - знакопеременная последовательность (v₁, е₁, v₂, е₂, ..., v_k, е_k, v_k₊₁=v₁), где v_я - различные вершины, а е_я являются различными гиперребрами, и каждое гиперребро содержит вершину слева и вершину справа. Схема называется неуравновешенный если каждое гиперребро не содержит других вершин в схеме. Клод Берже доказал, что гиперграф сбалансирован тогда и только тогда, когда он не содержит несбалансированной схемы нечетной длины. Каждый сбалансированный гиперграф обладает свойством Кёнига.^[9]^[1]^:468–470

Следующие варианты эквивалентны:^[1]^:470–471

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

Подбор и упаковка

А вершинная упаковка в (простом) графе - это подмножество п его вершин, таких что никакие две вершины в п смежные.

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

Учитывая гиперграф ЧАС = (V , E), определим его граф пересечений Int (ЧАС) как простой граф, вершинами которого являются E и ребра которого являются парами (е₁,е₂) такие, что е₁,е₂ имеют общую вершину. Тогда каждое совпадение в ЧАС упаковка вершин в Int (ЧАС) и наоборот.
Учитывая график г = (V', E'), определим его звездный гиперграф St (г) как гиперграф, вершины которого E'и чьи гиперребры звезды вершин графа G (т.е. для каждой вершины v' в V', в St (г), который содержит все ребра из E'которые примыкают к v'). Тогда каждая упаковка вершин в G является паросочетанием в St (г) и наоборот.
В качестве альтернативы, учитывая график г = (V', E'), определим его кликовый гиперграф Cl (г) как гиперграф, вершинами которого являются клики из Г, и для каждой вершины v' в V', в Cl (г), содержащий все клики в г которые содержат v'. Опять же, каждая упаковка вершин в г паросочетание в Cl (г) и наоборот. Отметим, что Cl (г) не может быть построен из г за полиномиальное время, поэтому его нельзя использовать в качестве редукции для доказательства NP-сложности. Но у него есть некоторые теоретические применения.

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

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

использованная литература

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

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

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

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

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

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

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

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

[8] Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (ed.), «ГЛАВА 2 - Сбалансированные гиперграфы и некоторые приложения в теории графов», Обзор комбинаторной теории, Северная Голландия, стр. 15–23, ISBN 978-0-7204-2262-7, получено 2020-06-19

[9] Берже, Клод; Вергнас, Мишель ЛАС (1970). "Sur Un теоремы Du Type König Pour Hypergraphes". Летопись Нью-Йоркской академии наук. 175 (1): 32–40. Дои:10.1111 / j.1749-6632.1970.tb56451.x. ISSN 1749-6632.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]