Сбалансированный гиперграф
В теории графов — сбалансированный гиперграф это гиперграф , который имеет несколько свойств, аналогичных свойствам двудольного графа .
Сбалансированные гиперграфы были введены Берже. [1] как естественное обобщение двудольных графов. Он дал два эквивалентных определения.
Определение по 2-раскраске
[ редактировать ]Гиперграф H = ( V , E ) называется 2-раскрашиваемым , если его вершины могут быть 2-цветными, так что ни одно гиперребро не является одноцветным. Каждый двудольный граф G = ( X + Y , E ) раскрашивается в 2 цвета: каждое ребро содержит ровно одну вершину X и одну вершину Y , поэтому, например, X можно покрасить в синий цвет, а Y можно покрасить в желтый цвет, и ни одно ребро не будет одноцветным.
Гиперграф, в котором некоторые гиперребра являются одиночными (содержат только одну вершину), очевидно, не раскрашивается в 2 цвета; Чтобы избежать таких тривиальных препятствий на пути к 2-раскраске, принято рассматривать гиперграфы, которые по существу раскрашиваются в 2 цвета , т. е. они становятся раскрашиваемыми в 2 цвета после удаления всех одноэлементных гиперребер. [2] : 468
Гиперграф называется сбалансированным , если он по существу раскрашивается в 2 цвета и остается по существу раскрашиваемым в 2 цвета при удалении любого количества вершин. каждого подмножества U из V определите ограничение H U на U как гиперграф H , для = ( U , EU Формально ), где . Тогда H называется сбалансированным тогда и только тогда, когда H U по существу раскрашивается в 2 цвета для любого подмножества U из V . Обратите внимание, что простой граф является двудольным тогда и только тогда, когда он раскрашивается в 2 цвета тогда и только тогда, когда он сбалансирован.
Определение нечетными циклами
[ редактировать ]Цикл схема (или ) в гиперграфе — это циклическая чередующаяся последовательность различных вершин и гиперребер: ( v 1 , e 1 , v 2 , e 2 , ..., v k , e k , v k +1 = v 1 ), где каждая вершина v i содержится как в e i −1, так и в e i . Число k называется длиной цикла.
Гиперграф сбалансирован нечетной длины тогда и только тогда, когда каждый цикл C в H имеет ребро, содержащее не менее трех вершин из C . [3]
Обратите внимание, что в простом графе все ребра содержат только две вершины. Следовательно, простой граф сбалансирован тогда и только тогда, когда он вообще не содержит циклов нечетной длины, что справедливо тогда и только тогда, когда он двудольный.
Горы [1] доказал, что эти два определения эквивалентны; доказательство также доступно здесь. [2] : 468–469
Характеристики
[ редактировать ]Некоторые теоремы о двудольных графах были обобщены на сбалансированные гиперграфы. [4] [2] : 468–470
- В каждом сбалансированном гиперграфе минимальное вершинное покрытие имеет тот же размер, что и его максимальное соответствие . Это обобщает теорему Кенига-Эгервари о двудольных графах.
- В каждом сбалансированном гиперграфе степень (= максимальное количество гиперребер, содержащих одну вершину) равна хроматическому индексу (= наименьшему количеству цветов, необходимых для раскраски гиперребер так, чтобы никакие два гиперребра одного цвета не имели общей вершины) . [5] Это обобщает теорему Кенига о двудольных графах.
- Каждый сбалансированный гиперграф удовлетворяет обобщению теоремы Холла о браке : [3] оно допускает идеальное паросочетание тогда и только тогда, когда для всех непересекающихся множеств вершин V 1 , V 2 , если для всех ребер e в E , то | В 2 | ≥ | В 1 |. См. теоремы Холла для гиперграфов .
- Каждый сбалансированный гиперграф максимальной степени D можно разбить на D паросочетаний, не пересекающихся по ребрам. [1] : Глава 5 [3] : Следствие 3
k k -кратная трансверсаль сбалансированного гиперграфа может быть выражена как объединение попарно непересекающихся трансверсалей, и такое разбиение может быть получено за полиномиальное время. [6]
Сравнение с другими понятиями двудольности
[ редактировать ]Помимо баланса, существуют альтернативные обобщения двудольных графов. Гиперграф называется двудольным, если его множество вершин V можно разделить на два множества, X и Y , так что каждое гиперребро содержит ровно один элемент из X (см. двудольный гиперграф ). Очевидно, что любой двудольный граф раскрашивается в 2 цвета.
Свойства двучастности и сбалансированности не предполагают друг друга.
Баланс не подразумевает двусторонность . Пусть H — гиперграф: [7]
{ {1,2} , {3,4} , {1,2,3,4} }
он раскрашивается в 2 цвета и остается раскрашиваемым в 2 цвета при удалении из него любого количества вершин. Однако оно не двудольное, поскольку для того, чтобы в каждом из первых двух гиперребер было ровно по одной зеленой вершине, нам необходимо иметь две зеленые вершины в последнем гиперребре. Двусторонность не означает баланса . Например, пусть H — гиперграф с вершинами {1,2,3,4} и ребрами:
{ {1,2,3} , {1,2,4} , {1,3,4} }
Он двудольный по разбиению X = {1}, Y = {2,3,4}. Но не сбалансирован. Например, если удалить вершину 1, мы получим ограничение H на {2,3,4}, которое имеет следующие гиперребра:
{ {2,3} , {2,4} , {3,4} }
Он не раскрашивается в 2 цвета, поскольку в любой 2-раскраске есть как минимум две вершины одного цвета и, следовательно, хотя бы одно из гиперребер одноцветное.
Другой способ увидеть, что H не сбалансирован, состоит в том, что он содержит цикл нечетной длины C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), и ни одно ребро C не содержит все три вершины 2,3,4 из C .
Трехсторонность не подразумевает баланса . Например, пусть H — трехчастный гиперграф с вершинами {1,2},{3,4},{5,6} и ребрами:
{ {1,3,5}, {2,4,5}, {1,4,6} }
Он не сбалансирован, поскольку если мы удалим вершины 2,3,6, остаток составит:
{ {1,5}, {4,5}, {1,4} }
который не раскрашивается, поскольку это 3-цикл.
Другой способ увидеть, что он не сбалансирован, состоит в том, что он содержит цикл нечетной длины C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1), и ни одно ребро C не содержит все три вершины 1,4,5 из C .
Связанные свойства
[ редактировать ]Полностью сбалансированные гиперграфы
[ редактировать ]Гиперграф называется полностью сбалансированным , если каждый цикл C в H длины не менее 3 (не обязательно нечетной длины) имеет ребро, содержащее не менее трех вершин из C . [8]
Гиперграф H является вполне сбалансированным тогда и только тогда, когда каждый его подгиперграф является древовидным гиперграфом. [8]
Нормальные гиперграфы
[ редактировать ]Свойство Кенига гиперграфа H — это свойство того, что его минимальное вершинное покрытие имеет тот же размер, что и его максимальное сопоставление . Теорема Кенига -Эгервари утверждает, что все двудольные графы обладают свойством Кенига.
Сбалансированные гиперграфы — это в точности такие гиперграфы H, что каждый подгиперграф H частичный обладает свойством Кенига (т. е. H обладает свойством Кенига даже при удалении любого количества гиперребер и вершин).
Если каждый частичный гиперграф H обладает свойством Кенига (т. е. H обладает свойством Кенига даже при удалении любого количества гиперребер, но не вершин), то H называется нормальным гиперграфом . [9]
Таким образом, полностью сбалансированный подразумевает сбалансированный, что означает нормальный.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Берже, Клод (1970). «О некоторых гиперграфах, обобщающих двудольные графы». Комбинаторная теория и ее приложения . 1 :119–133.
- ^ Перейти обратно: а б с Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
- ^ Перейти обратно: а б с Конфорти, Микеле; Корнюжоль, Жерар; Капур, Аджай; Вушкович, Кристина (1 сентября 1996 г.). «Совершенные паросочетания в сбалансированных гиперграфах». Комбинаторика . 16 (3): 325–329. дои : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .
- ^ Берже, Клод; Верньяс, Мишель ЛАС (1970). «Теоремы о типах Кенига для гиперграфов». Анналы Нью-Йоркской академии наук . 175 (1): 32–40. дои : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .
- ^ Ловас, Л. (1 июня 1972 г.). «Нормальные гиперграфы и гипотеза идеального графа». Дискретная математика . 2 (3): 253–267. дои : 10.1016/0012-365X(72)90006-4 . ISSN 0012-365X .
- ^ Дальхаус, Элиас; Краточвил, Ян; Мануэль, Пол Д.; Миллер, Мирка (27 ноября 1997 г.). «Трансверсальное разбиение в сбалансированных гиперграфах». Дискретная прикладная математика . 79 (1): 75–89. дои : 10.1016/S0166-218X(97)00034-6 . ISSN 0166-218X .
- ^ «Раскраска. Какое обобщение двудольных графов сильнее?» . Математический обмен стеками . Проверено 27 июня 2020 г.
- ^ Перейти обратно: а б Лехель, Йено (1 ноября 1985 г.). «Характеристика полностью сбалансированных гиперграфов» . Дискретная математика . 57 (1): 59–65. дои : 10.1016/0012-365X(85)90156-6 . ISSN 0012-365X .
- ^ Беккенбах, Изабель; Борндорфер, Ральф (01 октября 2018 г.). «Теорема Холла и Кенига в графах и гиперграфах». Дискретная математика . 341 (10): 2753–2761. дои : 10.1016/j.disc.2018.06.013 . ISSN 0012-365X . S2CID 52067804 .