Сбалансированный гиперграф - Balanced hypergraph

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

Сбалансированные гиперграфы были введены Berge[1] как естественное обобщение двудольных графов. Он дал два эквивалентных определения.

Определение по 2-красочности

Гиперграф ЧАС = (V, E) называется 2-цветный если его вершины могут быть двухцветными, так что ни одно гиперребро не будет одноцветным. Каждый двудольный граф грамм = (Икс+Y, E) 2-раскрашиваем: каждое ребро содержит ровно одну вершину Икс и одна вершина Y, так например Икс может быть окрашен в синий цвет и Y может быть окрашен в желтый цвет, а края не являются одноцветными.

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

Гиперграф называется сбалансированный если он, по сути, можно раскрашивать в 2 цвета и остается по существу 2-окрашиваемым при удалении любого количества вершин. Формально для каждого подмножества U из Vопределить ограничение из ЧАС к U как гиперграф ЧАСU = (U, EU) куда . потом ЧАС называется сбалансированным тогда и только тогда ЧАСU по существу 2-раскрашиваем для каждого подмножества U из V. Обратите внимание, что простой граф двудольный тогда и только тогда, когда он 2-раскрашиваем, если и только если он сбалансирован.

Определение нечетными циклами

А цикл (или схема) в гиперграфе - это циклическая чередующаяся последовательность различных вершин и гиперребер: (v1, е1, v2, е2, ..., vk, еk, vk+1=v1), где каждая вершина vя содержится в обоих ея−1 и ея. Номер k называется длина цикла.

Гиперграф - это сбалансированный если и только если каждый цикл нечетной длины C в ЧАС имеет ребро, содержащее не менее трех вершин C.[3]

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

Berge[1] доказал, что эти два определения эквивалентны; доказательство также доступно здесь.[2]:468–469

Характеристики

Некоторые теоремы о двудольных графах были обобщены на сбалансированные гиперграфы.[4][2]:468–470

  • В каждом сбалансированном гиперграфе минимум вершина-крышка имеет тот же размер, что и его максимальный соответствие. Это обобщает Теорема Кёнига-Эгервари на двудольных графах.
  • В каждом сбалансированном гиперграфе степень (= максимальное количество гиперребер, содержащих одну вершину) равно хроматический индекс (= наименьшее количество цветов, необходимое для раскраски гиперребер, так что никакие два гиперребра одного цвета не имеют общей вершины).[5] Это обобщает теорему Кёнига о двудольных графах.
  • Каждый сбалансированный гиперграф удовлетворяет обобщению Теорема холла о браке:[3] он допускает идеальное соответствие тогда и только тогда, когда для всех непересекающихся наборов вершин V1, V2, если для всех краев е в E, тогда |V2| ≥ |V1|, Видеть Теоремы холловского типа для гиперграфов.
  • Каждый сбалансированный гиперграф с максимальной степенью D, можно разбить на D реберно-непересекающиеся сопоставления.[1]:Глава 5[3]:Следствие 3.

А k-кратная трансверсаль сбалансированного гиперграфа может быть выражена как объединение k попарно непересекающиеся трансверсали, и такое разбиение может быть получено за полиномиальное время.[6]

Сравнение с другими представлениями о двудольности

Помимо баланса, существуют альтернативные обобщения двудольных графов. Гиперграф называется двудольный если его вершина установлена V можно разделить на два набора, Икс и Y, такое, что каждое гиперребро содержит ровно один элемент Икс (видеть двудольный гиперграф ). Очевидно, что любой двудольный граф 2-раскрашиваем.

Свойства двудольности и равновесия не подразумевают друг друга.

Баланс не подразумевает двуполость. Позволять ЧАС быть гиперграфом:[7]

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

он может быть 2-раскрашен и остается 2-раскрашиваемым после удаления из него любого количества вершин. Однако он не является двудольным, так как для того, чтобы иметь ровно одну зеленую вершину в каждом из первых двух гиперребер, мы должны иметь две зеленые вершины в последнем гиперребре.Двудольность не предполагает баланса. Например, пусть ЧАС - гиперграф с вершинами {1,2,3,4} и ребрами:

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

Он двудольный по перегородке Икс={1}, Y= {2,3,4}. Но не сбалансирован. Например, если удалить вершину 1, мы получим ограничение ЧАС к {2,3,4}, имеющей следующие гиперребра:

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

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

Другой способ увидеть это ЧАС не сбалансирован, так как содержит цикл нечетной длины C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), и без края C содержит все три вершины 2,3,4 C.

Трехсторонность не подразумевает баланса. Например, пусть ЧАС - трехчастный гиперграф с вершинами {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 в ЧАС длины не менее 3 (не обязательно нечетной длины) имеет ребро, содержащее не менее трех вершин C.[8]

Гиперграф H полностью сбалансирован тогда и только тогда, когда каждый подгиперграф H является древовидным гиперграфом.[8]

Нормальные гиперграфы

В Кониг недвижимость гиперграфа H состоит в том, что его минимум вершина-крышка имеет тот же размер, что и его максимальный соответствие. В Теорема Кёнига-Эгервари говорит, что все двудольные графы обладают свойством Кенига.

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

Если каждый частичный гиперграф H обладает свойством Konig (т.е.H обладает свойством Konig даже после удаления любого количества гиперребер, но не вершин), то H называется нормальный гиперграф.[9]

Таким образом, полностью сбалансированный означает сбалансированный, что подразумевает нормальный.

Рекомендации

  1. ^ а б c Берже, Клод (1970). "Sur уверен, что Hypergraphes généralisant les graphes bpartite". Комбинаторная теория и ее приложения. 1: 119–133.
  2. ^ а б c Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN  0-444-87916-1, МИСТЕР  0859549
  3. ^ а б c Конфорти, Микеле; Корнежоль, Жерар; Капур, Аджай; Вушкович, Кристина (1 сентября 1996 г.). «Совершенные сопоставления в сбалансированных гиперграфах». Комбинаторика. 16 (3): 325–329. Дои:10.1007 / BF01261318. ISSN  1439-6912. S2CID  206792822.
  4. ^ Берже, Клод; Вергнас, Мишель ЛАС (1970). "Sur Un теоремы Du Type König Pour Hypergraphes". Летопись Нью-Йоркской академии наук. 175 (1): 32–40. Дои:10.1111 / j.1749-6632.1970.tb56451.x. ISSN  1749-6632.
  5. ^ Ловас, Л. (1972-06-01). «Нормальные гиперграфы и гипотеза идеального графа». Дискретная математика. 2 (3): 253–267. Дои:10.1016 / 0012-365X (72) 90006-4. ISSN  0012-365X.
  6. ^ Дальхаус, Элиас; Кратохвил, Ян; Мануэль, Пол Д .; Миллер, Мирка (1997-11-27). «Трансверсальное разбиение в сбалансированных гиперграфах». Дискретная прикладная математика. 79 (1): 75–89. Дои:10.1016 / S0166-218X (97) 00034-6. ISSN  0166-218X.
  7. ^ "раскраска - Какое обобщение двудольных графов сильнее?". Обмен стеками математики. Получено 2020-06-27.
  8. ^ а б Лехель, Йено (1 ноября 1985 г.). «Характеристика полностью сбалансированных гиперграфов». Дискретная математика. 57 (1): 59–65. Дои:10.1016 / 0012-365X (85) 90156-6. ISSN  0012-365X.
  9. ^ Беккенбах, Изабель; Борндёрфер, Ральф (01.10.2018). «Теорема Холла и Кёнига в графах и гиперграфах». Дискретная математика. 341 (10): 2753–2761. Дои:10.1016 / j.disc.2018.06.013. ISSN  0012-365X.