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

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

Определение

Учитывая граф G = ( V , E ), дробное паросочетание в G — это функция, которая присваивает каждому ребру e в E дробь f ( e ) из [0, 1], такую, что для каждой вершины v в V , сумма долей ребер, прилегающих к v, не превосходит 1: ^[1] $\forall v\in V:\sum _{e\ni v}f(e)\leq 1$ Паросочетание в традиционном смысле — это частный случай дробного паросочетания, в котором доля каждого ребра равна 0 или 1: f ( e ) = 1, если e входит в паросочетание, и f ( e ) = 0, если оно нет. По этой причине в контексте дробных паросочетаний обычные паросочетания иногда называют целочисленными .

Размер целочисленного паросочетания — это количество ребер в паросочетании и число сопоставлений. $\nu (G)$ графа G это наибольший размер паросочетания в G. — Аналогично, размер дробного паросочетания представляет собой сумму долей всех ребер. Число дробного соответствия графа G — это наибольший размер дробного соответствия в G . Его часто обозначают $\nu ^{*}(G)$ . ^[2] Поскольку сопоставление является частным случаем дробного сопоставления, для каждого графа G целое число совпадений G меньше или равно дробному числу совпадений G ; в символах: $\nu (G)\leq \nu ^{*}(G).$ График, на котором $\nu (G)=\nu ^{*}(G)$ называется стабильным графом . ^[3] Каждый двудольный граф стабилен; это означает, что в каждом двудольном графе дробное число совпадений является целым числом и равно целому числу совпадений.

На общем графике $\nu (G)>{\frac {2}{3}}\nu ^{*}(G).$ Дробное число совпадений может быть целым или полуцелым. ^[4]

Матричная презентация

Для двудольного графа G = ( X + Y , E ) дробное паросочетание может быть представлено в виде матрицы с | Х | строки и | Ю | столбцы. Значение записи в строке x и столбце y — это доля ребра ( x , y ).

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

Дробное паросочетание называется совершенным , если сумма весов, прилегающих к каждой вершине, равна ровно 1. Размер идеального паросочетания равен точно | В |/2.

В двудольном графе G = ( X + Y , E ) дробное паросочетание называется X-совершенным , если сумма весов, смежных с каждой вершиной X, равна ровно 1. Размер X -совершенного дробного паросочетания равен точно | Х |.

Для двудольного графа G = ( X + Y , E ) следующие условия эквивалентны:

G допускает X -совершенное интегральное паросочетание,
G допускает X -совершенное дробное паросочетание и
G удовлетворяет условию теоремы Холла о браке .

Из первого условия следует второе, поскольку целочисленное паросочетание является дробным паросочетанием. Из второго следует третье, поскольку для каждого подмножества W из X сумма весов вблизи вершин W равна | W |, поэтому прилегающие к ним ребра обязательно смежны хотя бы с | Вт | вершины Y . По теореме о браке Холла из последнего условия следует первое. ^[5]^{[ нужен лучший источник ]}

В общем графе приведенные выше условия не эквивалентны — наибольшее дробное паросочетание может быть больше, чем наибольшее целочисленное паросочетание. Например, 3-цикл допускает идеальное дробное паросочетание размера 3/2 (доля каждого ребра равна 1/2), но не допускает идеальное целочисленное паросочетание — наибольшее целочисленное паросочетание имеет размер 1.

Алгоритмические аспекты

Наибольшее дробное совпадение в графе можно легко найти с помощью линейного программирования или, альтернативно, с помощью алгоритма максимального потока . В двудольном графе можно преобразовать максимальное дробное паросочетание в максимальное целочисленное паросочетание того же размера. Это приводит к простому полиномиальному алгоритму поиска максимального паросочетания в двудольном графе. ^[6]

Если G — двудольный граф с | Х | = | Ю | = n и M — идеальное дробное паросочетание, то матричное представление M — это дважды стохастическая матрица — сумма элементов в каждой строке и каждом столбце равна 1. Алгоритм Биркгофа можно использовать для разложения матрицы в выпуклую сумму максимум н ²-2 n +2 матрицы перестановок. Это соответствует разложению M в выпуклую сумму не более n ²-2 n +2 идеальных совпадения.

Дробное сопоставление максимальной мощности

Дробное сопоставление максимальной мощности (т. е. максимальной суммы дробей) можно найти с помощью линейного программирования . Существует также алгоритм со строго полиномиальным временем: ^[7] используя дополняющие пути , которые выполняются во времени $O(|V||E|)$ .

Дробное сопоставление максимального веса

Предположим, что каждое ребро графа имеет вес. Дробное совпадение максимального веса в графе можно найти с помощью линейного программирования . В двудольном графе можно преобразовать дробное сопоставление максимального веса в целочисленное сопоставление максимального веса того же размера следующим образом: ^[8]

Пусть f — дробное паросочетание.
Пусть H — подграф G , содержащий только ребра e с нецелой дробью, 0< f ( e )<1.
Если H пусто, то мы закончили.
если у H есть цикл, то он должен быть четной длины (поскольку граф двудольный), поэтому мы можем построить новое дробное паросочетание f ₁ , перенеся малую дробь ε с четных ребер на нечетные, и новое дробное паросочетание f ₂ путем переноса ε с нечетных ребер на четные. Поскольку f является средним значением f ₁ и f ₂ , вес f является средним между весами f ₁ и f ₂ . Поскольку f имеет максимальный вес, все три паросочетания должны иметь одинаковый вес. Существует выбор ε , для которого хотя бы одна из f ₁ или f ₂ имеет меньше нецелых дробей. Продолжение таким же образом приводит к интегральному паросочетанию того же веса.
Предположим, что H не имеет цикла, и пусть P — самый длинный путь в H . Доля каждого ребра, примыкающего к первой или последней вершине в P, должна быть равна 0 (если она равна 1 — первое/последнее ребро в P нарушает условие дробного совмещения; если оно находится в (0,1) — то P не является самый длинный). Следовательно, мы можем построить новые дробные паросочетания f ₁ и f _2, перенося ε с нечетных ребер на четные или наоборот. Опять же, f ₁ и f ₂ должны иметь максимальный вес, и хотя бы один из них имеет меньше нецелых дробей.

Многогранник дробного соответствия

Учитывая граф G = ( V , E ), многогранник дробного паросочетания G паросочетания является выпуклым многогранником , который представляет все возможные дробные G . Это многогранник в R ^{| Е |} - | E |-мерное евклидово пространство. Каждая точка ( x ₁ ,..., x _|E| ) в многограннике представляет собой паросочетание, в котором доля каждого ребра e равна x _e . Многогранник определяется | Е | ограничения неотрицательности ( x _e ≥ 0 для всех e в E ) и | В | ограничения вершин (сумма x _e для всех ребер e, смежных с вершиной v , не превышает 1). В двудольном графе все вершины многогранника дробного совмещения являются целыми.

Ссылки

^ Ахарони, Рон; Кесслер, Офра (15 октября 1990 г.). «О возможном распространении теоремы Холла на двудольные гиперграфы» . Дискретная математика . 84 (3): 309–313. дои : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
^ Лю, Ян; Лю, Гуйчжэнь (2002). «Дробные числа совпадений графов». Сети . 40 (4): 228–231. дои : 10.1002/net.10047 . ISSN 1097-0037 . S2CID 43698695 .
^ Беккенбах, Изабель; Борндорфер, Ральф (01 октября 2018 г.). «Теорема Холла и Кенига в графах и гиперграфах» . Дискретная математика . 341 (10): 2753–2761. дои : 10.1016/j.disc.2018.06.013 . ISSN 0012-365X . S2CID 52067804 .
^ Фюреди, Золтан (1 июня 1981 г.). «Максимальная степень и дробные паросочетания в однородных гиперграфах». Комбинаторика . 1 (2): 155–162. дои : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .
^ «co.combinatorics - версия теоремы Холла о браке с дробным соответствием» . MathOverflow . Проверено 29 июня 2020 г.
^ Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 .
^ Буржолли, Жан-Мари; Пуллибланк, Уильям Р. (1 января 1989 г.). «Графы Кенига-Эгервари, 2-бикритические графы и дробные паросочетания» . Дискретная прикладная математика . 24 (1): 63–82. дои : 10.1016/0166-218X(92)90273-D . ISSN 0166-218X .
^ Вазирани, Умеш (2012). «Максимально взвешенные совпадения» (PDF) . Калифорнийский университет в Беркли .

См. также

Дробная окраска

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

[:0-2] Лю, Ян; Лю, Гуйчжэнь (2002). «Дробные числа совпадений графов». Сети . 40 (4): 228–231. дои : 10.1002/net.10047 . ISSN 1097-0037 . S2CID 43698695 .

[3] Беккенбах, Изабель; Борндорфер, Ральф (01 октября 2018 г.). «Теорема Холла и Кенига в графах и гиперграфах» . Дискретная математика . 341 (10): 2753–2761. дои : 10.1016/j.disc.2018.06.013 . ISSN 0012-365X . S2CID 52067804 .

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

[5] «co.combinatorics - версия теоремы Холла о браке с дробным соответствием» . MathOverflow . Проверено 29 июня 2020 г.

[:2-6] Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 .

[7] Буржолли, Жан-Мари; Пуллибланк, Уильям Р. (1 января 1989 г.). «Графы Кенига-Эгервари, 2-бикритические графы и дробные паросочетания» . Дискретная прикладная математика . 24 (1): 63–82. дои : 10.1016/0166-218X(92)90273-D . ISSN 0166-218X .

[8] Вазирани, Умеш (2012). «Максимально взвешенные совпадения» (PDF) . Калифорнийский университет в Беркли .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]