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

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

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

Гиперграф 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 как гиперграф H _U = ( U , E _U ) , где . Тогда H называется сбалансированным тогда и только тогда, когда H _U по существу 2-раскрашиваем для каждого подмножества U из V . Обратите внимание, что простой граф является двудольным тогда и только тогда, когда он 2-раскрашиваем тогда и только тогда, когда он сбалансирован.${\displaystyle E_{U}=\{e\cap U|e\in E\}}$

Цикл (или контур ) в гиперграфе — это циклическая чередующаяся последовательность различных вершин и гиперребер: ( v ₁ , e ₁ , v ₂ , e ₂ , ..., v _k , e _k , v _{k +1} = v ₁ ), где каждая вершина v _i содержится как в e _{i −1 ,} так и в e _i . Число k называется длиной цикла.

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

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

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

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

• В каждом сбалансированном гиперграфе минимальное вершинное покрытие имеет тот же размер, что и его максимальное паросочетание . Это обобщает теорему Кёнига-Эгервари о двудольных графах.
• В каждом сбалансированном гиперграфе степень (= максимальное число гиперребер, содержащих некоторую одну вершину) равна хроматическому индексу (= наименьшему числу цветов, необходимых для раскраски гиперребер таким образом, чтобы никакие два гиперребра с одинаковым цветом не имели общей вершины). ^[5] Это обобщает теорему Кёнига о двудольных графах.
• Каждый сбалансированный гиперграф удовлетворяет обобщению теоремы Холла о браке : ^[3] он допускает совершенное паросочетание тогда и только тогда для всех непересекающихся множеств вершин V ₁ , V ₂ , если для всех ребер e в E , то | V ₂ | ≥ | V ₁ |. См. теоремы типа Холла для гиперграфов .${\displaystyle |e\cap V_ {2}|\geq |e\cap V_ {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 полностью сбалансирован тогда и только тогда, когда каждый подгиперграф H является древовидным гиперграфом. ^[8]

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

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

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

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